各种排序算法的实现

一.基本概念

1.稳定排序与不稳定排序:

对于A,B两个键值相等的对象，且在排序前，A在B之前，如果排序后A肯定还在B之前，则为稳定排序，如果B可能在A之前，为不稳定排序。

2.内排序和外排序：

内排序是指在排序期间数据对象全部存放在内存的排序

外排序是指在排序期间数据对象太多，不能同时存放在内存，必须依照排序过程的要求，不断在内外存之间移动的排序。

二.各种排序算法的实现

1.插入排序

基本思想：插入第i个对象时前i-1个对象已经排好了，将第i个对象插入前i-1个对象的合适地方，使得前i个对象有序。是稳定排序，比较次数和移动次数复杂度都为O(n^2)

void insertSort(int* disorder, int size){
    int temp = 0,i = 0;
    for(int j = 1; j < size; j++){
        temp=disorder[j];
        i = j;
        while(i > 0 && temp < disorder[i-1]){
            disorder[i] = disorder[i-1];
            i--;
        }
        disorder[i] = temp;

    }
}

2.希尔排序

基本思想：将数列以gap作为间隔分成子序列，分别对子序列进行插入排序，再逐步缩小间隔进行插入排序。shell提出gap取floor(n/2),gap=floor(gap/2).这是一种不稳定的排序。

void shellSort(int* disorder, int size){
    int gap = size / 2;
    int temp = 0, i = 0;
    while(gap > 0){
        for(int g = 0; g < gap; g++){
            for(int j = g + gap; j < size;){
                temp = disorder[j];
                i = j;
                while(i>gap-1 && temp<disorder[i-gap]){
                    disorder[i] = disorder[i-gap];
                    i=i-gap;
                }
                disorder[i]=temp;
                j=j+gap;
            }
        }
        gap=gap/2;
    }
}

3.起泡排序

基本思想：依次比较key(n)和key(n-1),直到key(2)和key(1)，这样会使最小的对象被起泡到第一个，依次进行起泡，完成排序。是稳定排序，比较次数和移动次数复杂度都为O(n^2)

void bubbleSort(int* disorder, int size){
    int temp=0,modified=0;
    for(int j=1;j<size;j++){
        modified=0;
        for(int i=size-1;i>j-1;i--){
            if(disorder[i]<disorder[i-1]){
                temp = disorder[i];
                disorder[i] = disorder[i-1];
                disorder[i-1]=temp;
                modified++;
            }
        }
        if(modified==0){
            break;
        }
    }
}

4.快速排序

基本思想：任取一个对象作为基准，按照关键码的大小，将排序队列分为左右两个子序列，小于该对象的都放在左序列，大于该对象的都放在右序列，然后分别对两个子序列重复上述方法，直到所有对象有序排列。是不稳定排序，比较次数和移动次数复杂度都为O(n*logn)

void quickSort1(int* disorder, int start, int end){
    if(start>=end){
        return;
    }
    int middle=disorder[start];
    int temp=0;
    int pivotpos=start+1,i=start+1;
    for(;i<=end;i++){
        if(disorder[i]<middle){
            if(i!=pivotpos){
                temp=disorder[i];
                disorder[i]=disorder[pivotpos];
                disorder[pivotpos]=temp;
            }
            pivotpos++;
        }
    }
    disorder[start]=disorder[pivotpos-1];
    disorder[pivotpos-1]=middle;
    quickSort1(disorder,start,pivotpos-2);
    quickSort1(disorder,pivotpos,end);
}
void quickSort(int* disorder, int size){
    quickSort1(disorder,0,size-1);
}

5.选择排序

基本思想：每一趟在后面n-i个待排序对象中选出关键码最小的对象，作为有序对象集的第i个对象。不稳定的排序，比较次数为O(n^2),移动次数为O(n)

void selectSort(int* disorder, int size){
    int temp=0,small;
    for(int j=0;j<size-1;j++){
        temp=disorder[size-1];
        small=size-1;
        for(int i=size-2;i>j-1;i--){
            if(disorder[i]<temp){
                temp=disorder[i];
                small=i;
            }
        }
        disorder[small]=disorder[j];
        disorder[j]=temp;
    }
}

6.锦标赛排序

基本思想：利用胜者树来进行选择排序。稳定的排序，比较次数为O(n*logn).

锦标赛排序虽然节省时间，但是对空间有较大浪费，不推荐

7.堆排序

基本思想：利用最大堆，将得到的最大元素依次调整到最后。不稳定的排序，时间复杂度为O(n*logn).

void filterDown(int* disorder, int pos, int size)
{
    int temp = disorder[pos];
    int iPos = pos;
    int iChildPos;
    while(2*iPos+1 < size){
        iChildPos = 2*iPos+1;
        if(iChildPos+1<size && disorder[iChildPos+1] > disorder[iChildPos]){
            iChildPos++;
        }
        if(temp<disorder[iChildPos]){
            disorder[iPos] = disorder[iChildPos];
            iPos = iChildPos;
        }
        else{
            break;
        }
    }
    disorder[iPos] = temp;

}
void heapSort(int* disorder, int size)
{
    for(int i=size/2-1; i>=0; i--){
        filterDown(disorder, i, size);
    }
    int temp;
    for(int i=size-1; i>0; i--){
        temp = disorder[i];
        disorder[i] = disorder[0];
        disorder[0] = temp;
        filterDown(disorder, 0, i);
    }
}

8.归并排序

基本思想：先两两排序，再逐步进行归并。稳定的排序，时间复杂度为O(n*logn).

void merge(int* source,int*dest, int gap, int size){
    int pos1,pos2,end1,end2,destpos=0;
    for(int i=0;i<size;i+=2*gap){
        pos1=i;
        end1=i+gap>size?size:i+gap;
        pos2=i+gap;
        end2=i+2*gap>size?size:i+2*gap;
        while(pos1<end1&&pos2<end2){
            if(source[pos1]<source[pos2]){
                dest[destpos]=source[pos1];
                pos1++;
            }
            else{
                dest[destpos]=source[pos2];
                pos2++;
            }
            destpos++;
        }
        while(pos1<end1){
            dest[destpos++]=source[pos1++];
        }
        while(pos2<end2){
            dest[destpos++]=source[pos2++];
        }

    }
}
void mergeSort(int* disorder, int size){
    int gap=1;
    int* temparr= new int[size];
    while(gap<size){
        merge(disorder, temparr,gap,size);
        gap*=2;
        merge(temparr,disorder,gap,size);
        gap*=2;
    }
    delete[] temparr;
}

9.基数排序

基本思想：利用分配和收集的方法进行排序，比如已知数字不超过100，可以按照十位数先进行分配，再分别进行排序后将数字收集起来。

三.排序结果的检验

对于排序算法，可以用下列的方法来生成一系列的随机数进行排序，并用isSorted函数来检验是否正确的排序了。

bool isSorted(int* disorder, int size){
    for(int i=0;i<size-1;i++){
        if(disorder[i]>disorder[i+1]) return false;
    }
    return true;
}
int _tmain(int argc, _TCHAR* argv[])
{
    const int size=200;
    const int maxnum = 10000;
    int* disorder=new int[size];
    srand((unsigned) time(NULL)); 
    for(int i=0;i<size;i++){
        disorder[i]=rand()%maxnum;    
    }
    mergeSort(disorder,size);
    for(int i=0;i<size;i++){
        cout<<disorder[i]<<endl;
    }
    cout<<isSorted(disorder,size)<<endl;
    return 0;
}