数据结构深入剖析（7）

一、希尔排序（不稳定）
1、基本思想：将待排序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。
2、示例
例如：将n 个数据元素分成d 个子序列：
{ R[1]，R[1+d]，R[1+2d]，…，R[1+kd] }
{ R[2]，R[2+d]，R[2+2d]，…，R[2+kd] }
…
{ R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] }
其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。
3、实现
#include  
void printarray(int array[],int len)
{
    int i = 0;
    for(i = 0; i < len;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}
void ShellSort(int array[],int len)
{
    int i = 0;
    int j = 0;
    int k = -1;
    int temp = -1;
      int gap = len;
/*
    for(i = 1;i < len;i++){
        k = i;
        temp = array[k];

        for(j = i-1;(j >= 0)&& (array[j] > temp);j--){
            array[j+1] = array[j];
            k = j;
        }
    array[k] = temp;
    }
*/
    do{
        gap = gap / 3 + 1;//gap 最后收敛于1
        for(i = gap; i < len; i += gap){
            k = i;
            temp = array[k];
            for(j = i - gap; (j >= 0) && (array[j] > temp);j -= gap){
                array[j + gap] = array[j];
                k = j;
            }
            array[k] = temp;
        }
    }while(gap > 1);
}
int main()
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    printarray(array,len);
    ShellSort(array,len);
    printarray(array,len);
    return 0;
}
二、快速排序（不稳定）
1、基本思想
1）任取待排序序列中的某个数据元素作为基准，按照该元素的关键字大小将整个序列划分为左右两个子序列：
---左侧子序列中的所有元素都小于或等于基准元素
---右侧子序列中的所有元素都大于基准元素
---基准元素排在这两个子序列中间
2）分别对这两个子序列重复执行上述方法，直到所有的对象都排在相对于的位置上为止。
2、实现
#include
void printarray(int array[],int len)
{
    int i = 0;
    for(i = 0; i < len;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}
void swap(int array[],int i,int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
int partition(int array[],int low,int high)
{
    int pv = array[low];
    while(low < high){
        while((low < high) && (array[high] >= pv)){
        high--;
        }
        swap(array,low,high);
        while((low < high) && (array[low] <= pv)){
            low++;
        }
        swap(array,low,high);
    }
    return low;
}
void QSort(int array[],int low,int high)
{
    if(low < high){
        int pivot = partition(array,low,high);
        QSort(array,low,pivot-1);
        QSort(array,pivot+1,high);
    }
}
void QuickSort(int array[],int len)
{
    QSort(array,0,len-1);
}
int main()
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    printarray(array,len);
    QuickSort(array,len);
    printarray(array,len);
    return 0;
}
三、归并排序（稳定）
1、基本思想
将两个或两个以上的有序序列合并成一个新的有序序列：
有序序列V[1] …V[m]和V[m+1] …V[n]合并为V[1] …V[n]，这种归并方法称为2路归并。
将3个有序序列归并为一个新的有序序列，称为3路归并。
将多个有序序列归并为一个新的有序序列，称为多路归并。
2、实现
#include  
#include
void printarray(int array[],int len)
{
    int i = 0;
    for(i = 0; i < len;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}
Merge(int src[],int des[],int low,int mid,int high)
{
    int i = low;
    int j = mid + 1;
    int k = low;

    while((i <= mid) && (j <= high)){
        if(src[j] < src[i]){
            des[k++] = src[j++];
        }else{
            des[k++]= src[i++];
        }
    }
    while(i <= mid){
        des[k++]= src[i++];
    }
    while(j <= high){
        des[k++]= src[j++];
    }
}
void Msort(int src[],int des[],int low,int high,int max)
{
    if(low == high){
        des[low] = src[low];
    }else{
        int mid = (low + high) / 2;
        int* space = (int*)malloc(sizeof(int)*max);
        if(space != NULL){
            Msort(src,space,low,mid,max);
            Msort(src,space,mid+1,high,max);
            Merge(space,des,low,mid,high);
        }
        free(space);
    }
}
void MergeSort(int array[],int len)
{
    Msort(array,array,0,len - 1,len);
}
int main()
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    printarray(array,len);
    MergeSort(array,len);
    printarray(array,len);
    return 0;
}

四、总结
希尔排序，快速排序和归并排序将排序算法的时间复杂度提高到了O(n*logn)

希尔排序和快速排序的排序结果是不稳定的

归并排序的排序结果是稳定的