算法—排序篇2

1、归并排序(Merging Sort)

归并排序(Merging Sort)：就是利用归并的思想实现排序⽅法.。
它的原理：是假设初始序列含有n个记录,则可以看成n个有序的⼦序列，每个⼦序列的⻓度为1,然后两两合并，得到[n/2]个⻓度为2或1的有序⼦序列, 再两两归并. ......如此重复,直到得到⼀个⻓度为n 的有序列为止，这种排序⽅方法称为2路归并排序。核心便是先拆后合

归并排序

先拆后合

先拆后和

拆：Msort函数拆分原数组成单个

Msort函数演练

拆分 low != hight

拆分 low == hight

合：Merger函数合并排好序的数组

合并两个排好序的数组

归并

递归方式代码实现：

//11.归并排序-对顺序表L进行归并排序
//③ 将有序的SR[low..mid]和SR[mid+1..hight]归并为有序的TR[low..hight]
void Merge(int SR[],int TR[],int low,int mid,int hight) {
    int j,k,l;
    //1.将SR中记录由小到大地并入TR
    for(j = mid+1,k = low; low <= mid && j <= hight;k++) {
        if (SR[low] < SR[j]) {
            TR[k] = SR[low++];
        } else {
            TR[k] = SR[j++];
        }
    }
    
    //2.将剩余的SR[low..mid]复制到TR
    if(low <= mid) {
        for(l=0;l <= mid-low;l++){
            TR[k+l] = SR[low+l];
        }
    }
    
    //3.将剩余的SR[j..hight]复制到TR
    if(j <= hight) {
        for(l=0;l <= hight-j;l++)
            TR[k+l] = SR[j+l];
    }
}

//② 将SR[s...t] 归并排序为 TR1[s...t];
void MSort(int SR[],int TR1[],int low, int hight){
    int mid;
    int TR2[MAXSIZE+1];
    
    if(low == hight) {//递归结束
        TR1[low] = SR[low];
    } else {
        //1.将SR[low...hight] 平分成 SR[low...mid] 和 SR[mid+1,hight];
        mid = (low + hight)/2;
        //2. 递归将SR[low,mid]归并为有序的TR2[low,mid];
        MSort(SR, TR2, low, mid);
        //3. 递归将SR[mid+1,hight]归并为有序的TR2[mid+1,hight];
        MSort(SR, TR2, mid+1, hight);
        //4. 将TR2[low,mid] 与 TR2[mid+1,hight], 归并到TR1[low,hight]中
        Merge(TR2, TR1, low, mid, hight);
    }
}
//① 对顺序表L进行归并排序
void MergeSort(SqList *L){
   
    MSort(L->r,L->r,1,L->length);
}

非递归方式归并排序

//12.归并排序(非递归)-->对顺序表L进行非递归排序
//对SR数组中相邻长度为s的子序列进行两两归并到TR[]数组中;
void MergePass(int SR[],int TR[],int s,int length){
  
    int i = 1;
    int j;
    
    //①合并数组
    //s=1 循环结束位置:8 (9-2*1+1=8)
    //s=2 循环结束位置:6 (9-2*2+1=6)
    //s=4 循环结束位置:2 (9-2*4+1=2)
    //s=8 循环结束位置:-6(9-2*8+1=-6) s = 8时,不会进入到循环;
    while (i<= length-2*s+1) {
        //两两归并(合并相邻的2段数据)
        Merge(SR, TR, i, i+s-1, i+2*s-1);
        i = i+2*s;
        
        /*
         s = 1,i = 1,Merge(SR,TR,1,1,2);
         s = 1,i = 3,Merge(SR,TR,3,3,4);
         s = 1,i = 5,Merge(SR,TR,5,5,6);
         s = 1,i = 7,Merge(SR,TR,7,7,8);
         s = 1,i = 9,退出循环;
         */
        
        /*
         s = 2,i = 1,Merge(SR,TR,1,2,4);
         s = 2,i = 5,Merge(SR,TR,5,6,8);
         s = 2,i = 9,退出循环;
         */
        
        /*
         s = 4,i = 1,Merge(SR,TR,1,4,8);
         s = 4,i = 9,退出循环;
         */
    }
    
    //②如果i<length-s+1,表示有2个长度不等的子序列. 其中一个长度为length,另一个小于length
    // 1 < (9-8+1)(2)
    //s = 8时, 1 < (9-8+1)
    if(i < length-s+1){
        //Merge(SR,TR,1,8,9)
        Merge(SR, TR, i, i+s-1, length);
    }else{
        //③只剩下一个子序列;
        for (j = i; j <=length; j++) {
            TR[j] = SR[j];
        }
    }
}

void MergeSort2(SqList *L){
    int *TR = (int *)malloc(sizeof(int) * L->length);
    int k = 1;
    //k的拆分变换是 1,2,4,8;
    while (k < L->length) {
        //将SR数组按照s=2的长度进行拆分合并,结果存储到TR数组中;
        //注意:此时经过第一轮的归并排序的结果是存储到TR数组了;
        MergePass(L->r, TR, k, L->length);
        k = 2*k;
        //将刚刚归并排序后的TR数组,按照s = 2k的长度进行拆分合并. 结果存储到L->r数组中;
        //注意:因为上一轮的排序的结果是存储到TR数组,所以这次排序的数据应该是再次对TR数组排序;
        MergePass(TR, L->r, k, L->length);
        k = 2*k;
        
    }
}

时间复杂度:
一趟归并需要将 SR[1]~SR[n]中相邻⻓度为h 的有序列的进⾏两两⽐较.,并将结果存储在TR1[1]- TR2[n]. 这需要将待排序的所有记录扫描⼀遍, 因此耗费 O(n) 时间。而由于完全二叉树的深度可知, 整个归并排序需要进⾏ log2n 次。因此总的时间复杂度为 O(nlogn)。

空间复杂度: 由于递归排序在递归的过程中需要与原始记录序列同样数量的存储归并结果以及递归时深度为log2n 的栈空间; 因此空间复杂度为 O(n+log2n)。

递归与非递归对比：
1：递归需要进⾏切分; 切分的规则是从⼤到⼩；
2：⾮递归归并. 是按照从小大的⽅式进行拆分以及合并的；

2、快速排序

快速排序(Quick Sort)的基本思想: 通过⼀趟排序将待排序记录分割成独立的两部分; 其中⼀部分记录的关键字均比另⼀部分记录的关键字小,则可分别对两部分记录继续进行排序,以达到整个排序有序的⽬的。

结构演示

QSort 函数思路:

判断low 是否⼩小于 high;
求得枢轴,并且将数组枢轴左边的关键字都⽐它⼩, 右边的关键字都⽐枢轴对应的关键字大;
将数组⼀分为二,对低子表进⾏行行排序,对⾼子表进行排序；

Partition 函数的功能:

选取当中⼀个关键字作为枢轴;
将它放在⼀个合适的位置上,使得它的左边的值都它⼩,右边的值都⽐它大；

Partition 函数的思路:

选取第⼀个关键字作为枢轴;
只要(low < high) 就循环持续的将表的两端进⾏交替向中间扫描 (两端交替循环);
while 遍历从[low,high]的⾼端位置开始找,找到⽐枢轴⼩的关键字(⾼位调整循环)
- 如没有找到,则修改范围. 将high 递减;
- 如果找到进⾏交换到低端位置 swap(L,low,high);
while 遍历从[low,high]的低端位置开始找,找到⽐枢轴⼤的关键字(低位调整循环);
* 如果没有找到,则修改范围,将low 递增;
* 如果找到进⾏交换到⾼端位置 swap(L,low,high);

函数演示

演示2

//13.快速排序-对顺序表L进行快速排序
//③交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置
//此时在它之前(后)的记录均不大(小)于它
int Partition(SqList *L,int low,int high){
    int pivotkey;
    //pivokey 保存子表中第1个记录作为枢轴记录;
    pivotkey = L->r[low];
    //① 从表的两端交替地向中间扫描;
    while (low < high) {
        
        //② 比较,从高位开始,找到比pivokey更小的值的下标位置;
        while (low < high &&  L->r[high] >= pivotkey)
            high--;
        //③ 将比枢轴值小的记录交换到低端;
        swap(L, low, high);
        //④ 比较,从低位开始,找到比pivokey更大的值的下标位置;
        while (low < high && L->r[low] <= pivotkey)
            low++;
        //⑤ 将比枢轴值大的记录交换到高端;
        swap(L, low, high);
        
    }
    
    //返回枢轴pivokey 所在位置;
    return low;
}

//② 对顺序表L的子序列L->r[low,high]做快速排序;
void QSort(SqList *L,int low,int high){
    int pivot;
    
    if(low < high){
        //将L->r[low,high]一分为二,算出中枢轴值 pivot;
        pivot = Partition(L, low, high);
        printf("pivot = %d L->r[%d] = %d\n",pivot,pivot,L->r[pivot]);
        //对低子表递归排序;
        QSort(L, low, pivot-1);
        //对高子表递归排序
        QSort(L, pivot+1, high);
    }
    
}

//① 调用快速排序(为了保证一致的调用风格)
void QucikSort(SqList *L){
    QSort(L, 1, L->length);
}

优化版快速排序

//14 快速排序-优化
int Partition2(SqList *L,int low,int high){
   
    int pivotkey;
    
    /**1.优化选择枢轴**/
    //① 计算数组中间的元素的下标值;
    int m = low + (high - low)/2;
    //② 将数组中的L->r[low] 是整个序列中左中右3个关键字的中间值;
    //交换左端与右端的数据,保证左端较小;[9,1,5,8,3,7,4,6,2]
    if(L->r[low]>L->r[high])
        swap(L, low, high);
    //交换中间与右端的数据,保证中间较小; [2,1,5,8,3,7,4,6,9];
    if(L->r[m]>L->r[high])
        swap(L, high, m);
    //交换中间与左端,保证左端较小;[2,1,5,8,3,7,4,6,9]
    if(L->r[m]>L->r[low])
        swap(L, m, low);
    //交换后的序列:3,1,5,8,2,7,4,6,9
    //此时low = 3; 那么此时一定比选择 9,2更合适;
    
    
    /**2.优化不必要的交换**/
    //pivokey 保存子表中第1个记录作为枢轴记录;
    pivotkey = L->r[low];
    //将枢轴关键字备份到L->r[0];
    L->r[0] = pivotkey;
    
    //① 从表的两端交替地向中间扫描;
    while (low < high) {
        //② 比较,从高位开始,找到比pivokey更小的值的下标位置;
        while (low < high &&  L->r[high] >= pivotkey)
            high--;
        
        //③ 将比枢轴值小的记录交换到低端;
        //swap(L, low, high);
        //③ 采用替换的方式将比枢轴值小的记录替换到低端
        L->r[low] = L->r[high];
        
        //④ 比较,从低位开始,找到比pivokey更大的值的下标位置;
        while (low < high && L->r[low] <= pivotkey)
            low++;
        
        //⑤ 将比枢轴值大的记录交换到高端;
        //swap(L, low, high);
        //⑤ 采样替换的方式将比枢轴值大的记录替换到高端
        L->r[high] = L->r[low];
    }
    //将枢轴数值替换会L->r[low]
    L->r[low] = L->r[0];
    
    //返回枢轴pivokey 所在位置;
    return low;
}

//② 对顺序表L的子序列L->r[low,high]做快速排序;
#define MAX_LENGTH_INSERT_SORT 7 //数组长度的阀值
void QSort2(SqList *L,int low,int high){
    int pivot;
    //if(low < high){
    //当high-low 大于常数阀值是用快速排序;
    if((high-low)>MAX_LENGTH_INSERT_SORT){
        //将L->r[low,high]一分为二,算出中枢轴值 pivot;
        pivot = Partition(L, low, high);
        printf("pivot = %d L->r[%d] = %d\n",pivot,pivot,L->r[pivot]);
        //对低子表递归排序;
        QSort(L, low, pivot-1);
        //对高子表递归排序
        QSort(L, pivot+1, high);
    }else{
        //当high-low小于常数阀值是用直接插入排序
        InsertSort(L);
    }
}

//① 快速排序优化
void QuickSort2(SqList *L)
{
    QSort2(L,1,L->length);
}

最好的情况: Partition 函数时间复杂度分析

T ( n ) ≤ 2T( n/2 ) + n , T(1) = 0;
T ( n ) ≤ 2(2T( n/4 ) + n/2) + n = 4T (n/4) + 2n; T ( n ) ≤ 4(2T( n/8 ) + n/4) + 2n = 8T (n/8) + 3n; ......
T ( n ) ≤ nT(1) + log2n ✖ n = O(nlogn);

最好的情况下时间复杂度为: O(nlogn);

最坏的情况: Partition 函数时间复杂度分析

排序的序列列刚好是逆向和正序. 那么递归树需要递归n-1次,且在第i 次划分需要经过n-i次关键字⽐较才找到比第i个记录, 也就枢轴的位置. 那么比较的次数 : (n-1)+(n-2)+(n-3)...+1 = (n(n-1))/2 ;

最终的最坏情况下的时间复杂度为 O(n^2)

排序总结

排序分类

时间复杂度对比表

我的知识？？

路漫漫其修远兮，吾将上下而求索！！！
任重而道远.....加油！！！