现在的位置: 首页 > 综合 > 正文

常见排序算法

2013年06月22日 ⁄ 综合 ⁄ 共 4801字 ⁄ 字号 评论关闭

 冒泡排序,插入排序,shell排序,快速排序,堆排序等。
现在把代码帖出来,大家瞅瞅。

// Sort.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#define MAX 10

void GetRandom(int a[],int n)
{
    for (int i=0; i<n; i++)
    {
        a=rand()%(2*n);
    }
}

void Print(int a[], int n)
{
    for(int i=0; i<n; i++)
        printf("%d,",a);
    printf("/n");
}

void InsertSort(int a[], int n)
{
    int i;

    for(i=1;i<n;i++)//从第2个元素开始把后面的元素插入到前面0~i的有序区中
    {
        if (a<a)//不要忘了判断!!!
        {
            int key = a;
            int j;

            for(j=i-1; j>=0&&a[j]>key; j--)//将大于a的元素后移
            {
                a[j+1]=a[j];
            }
            a[j+1]=key;//不要写成a[j]!!!
        }
    }
}

void ShellSort(int a[], int n)
{
    int d;
    
    for (d=n/2; d>=1; d/=2)//间距从n/2一直除2到1
    {
        //间距为d的元素为一组,组内插入排序
        //这一段就是把InsertSort中的1换成d
        for(int i=d; i<n; i++)
        {
            if (a<a)
            {
                int key=a;
                int j;

                for(j=i-d; j>=0&&a[j]>key; j-=d)
                {
                    a[j+d]=a[j];
                }
                a[j+d]=key;
            }
        }
    }
}

void BubbleSort(int a[], int n)
{
    for(int i=n-1; i>0; i--)
    {
        int flagExchange=0;//每一趟是否发生交换

        for(int j=0; j<i; j++)
        {
            if (a[j]>a[j+1])
            {
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                flagExchange=1;
            }
        }

        if (!flagExchange)//如果某一趟已经没有发生交换,直接推出
        {
            break;
        }
    }
}

int Partition(int a[], int low, int high)
{
    int key=a[low];

    while(low<high)
    {
        for(;low<high&&a[high]>=key;high--);//千万不要忘了=号!!!
        a[low]=a[high];
        for(;low<high&&a[low]<=key;low++);//千万不要忘了=号!!!
        a[high]=a[low];
    }
    
    a[low]=key;
    
    return low;
}

void _QuickSort(int a[], int low, int high)
{
    if(low<high)//if条件千万不能掉!!!
    {
        int mid = Partition(a,low,high);
        _QuickSort(a,low,mid-1);
        _QuickSort(a,mid+1,high);
    }
}

void QuickSort(int a[], int n)
{
    _QuickSort(a,0,n-1);
}

void SelectSort(int a[], int n)
{
    for(int i=0; i<n-1; i++)
    {
        int k=i;//每一趟最小值的索引
        for(int j=i+1; j<n; j++)
        {
            if (a[j]<a[k])
            {
                k=j;
            }
        }

        if (k!=i)
        {
            int temp=a[k];
            a[k]=a;
            a=temp;
        }
    }
}

//a[0]不用,最小的在a[1],小顶堆
void InsertHeap(int a[],int *heapsize, int newVal)
{
    (*heapsize)++;

    int i;
    for(i=*heapsize; i/2>0&&a>newVal; i/=2)
    {
        a=a;
    }
    a=newVal;

    Print(a,*heapsize+1);
}

//删除a[1],小顶堆
int DeleteHeapHead(int a[], int *heapsize)
{
    int min=a[1];
    int last=a[*heapsize];
    (*heapsize)--;

    int i;
    int m;

    for(i=1; 2*i<(*heapsize); i=m)
    {
        m=2*i;

        //m为最小子数的索引
        if (m!=*heapsize && a[m+1]<a[m])
            m++;

        if (a[m]>last)
        {
            break;
        }
        else
        {
            a=a[m];
        }
    }

    a=last;

    Print(a,*heapsize+1);

    return min;
}

//小顶堆
void HeapSort(int a[], int n)
{
    int* heap=new int[n+1];
    int heapsize=0;

    for( int i=0; i<n+1; i++)
    {
        heap=0;
    }

    for(int i=0; i<n; i++)
    {
        InsertHeap(heap,&heapsize,a);
    }

    for(int i=0; i<n; i++)
    {
        a=DeleteHeapHead(heap,&heapsize);
    }

    delete[] heap;
}

//从a[0]开始,大顶堆(把它当成从1开始的想,写出来后,[]内的都减1就可以了。)
void InsertHeap2(int a[], int *heapsize, int newVal)
{
    (*heapsize)++;

    int i;
    for(i=*heapsize; i/2>0&&a<newVal; i/=2)
    {
        a=a;
    }
    a=newVal;

    Print(a,*heapsize);
}

//删除最小的a[0],大顶堆
void DeleteHeapHead2(int a[], int *heapsize)
{
    int max=a[0];
    int last=a[*heapsize-1];
    (*heapsize)--;

    int i;
    int m;

    for(i=1; 2*i<(*heapsize); i=m)
    {
        m=2*i;

        //m为最小子数的索引
        if (m!=*heapsize && a[m]>a[m-1])
            m++;

        if (a[m-1]<last)
        {
            break;
        }
        else
        {
            a=a[m-1];
        }
    }

    a=last;
    a[*heapsize]=max;

    Print(a,MAX);
}

//大顶堆
void HeapSort2(int a[], int n)
{
    int heapsize=0;

    for(int i=0; i<n; i++)
    {
        InsertHeap2(a,&heapsize,a);
    }

    for(int i=0; i<n; i++)
    {
        DeleteHeapHead2(a,&heapsize);
    }
}

void MergeSort(int a[], int n)
{

}

int _tmain(int argc, _TCHAR* argv[])
{
    int a[MAX];

    printf("test of InsertSort/n");
    GetRandom(a,MAX);
    Print(a,MAX);
    InsertSort(a,MAX);
    Print(a,MAX);

    printf("test of ShellSort/n");
    GetRandom(a,MAX);
    Print(a,MAX);
    ShellSort(a,MAX);
    Print(a,MAX);

    printf("test of BubbleSort/n");
    GetRandom(a,MAX);
    Print(a,MAX);
    BubbleSort(a,MAX);
    Print(a,MAX);

    printf("test of QuickSort/n");
    GetRandom(a,MAX);
    Print(a,MAX);
    QuickSort(a,MAX);
    Print(a,MAX);

    printf("test of SelectSort/n");
    GetRandom(a,MAX);
    Print(a,MAX);
    SelectSort(a,MAX);
    Print(a,MAX);

    printf("test of HeapSort/n");
    GetRandom(a,MAX);
    Print(a,MAX);
    HeapSort(a,MAX);
    Print(a,MAX);

    printf("test of HeapSort2/n");
    GetRandom(a,MAX);
    Print(a,MAX);
    HeapSort2(a,MAX);
    Print(a,MAX);

    return 0;
}

【上篇】
【下篇】

抱歉!评论已关闭.