ITPub博客

首页 > 移动开发 > IOS > iOS数据结构与算法-归并排序与快速排序

iOS数据结构与算法-归并排序与快速排序

IOS 作者:精神食粮 时间:2021-09-25 19:58:02 0 删除 编辑

嗨,这里是逻辑iOS技术号:一个让知识变得感性,让学习变得轻松!活跃的技术小站,希望给你的生活与技术带来意思不一样!关注公众号,回复“        面试题    ”,即可领取更多大厂面试题型哦~ 小逻辑相信我们的生活不止眼前的苟且,还有我们向往的诗和大厂高薪工作~




归并排序


顾名思义,归并排序就是利 用归并的思想实现排序方法. 它的原理是假设初始序列含有n个记录,则可以看成n个有序的⼦序列. 每个子序列的长度为1,然后两合并.

得到[n/2]个⻓度为2或1的有序子序列列, 再两归并. ......如此重复,直到得到一个长度为n 的有序序列为此. 这种排序方法称为2路归并排序

    //11.归并排序-对顺序表L进行归并排序 //③ 将有序的SR[i..mid]和SR[mid+1..n]归并为有序的TR[i..n] void Merge(int SR[],int TR[],int i,int m,int n) {    int j,k,l;    //1.将SR中记录由小到大地并入TR    for(j=m+1,k=i;i<=m && j<=n;k++)    {        if (SR[i]<SR[j])            TR[k]=SR[i++];        else            TR[k]=SR[j++];    }
       //2.将剩余的SR[i..mid]复制到TR    if(i<=m)    {        for(l=0;l<=m-i;l++)            TR[k+l]=SR[i+l];    }
       //3.将剩余的SR[j..mid]复制到TR    if(j<=n)    {        for(l=0;l<=n-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;
       } }
    (滑动显示更多)

    图片

    快速排序


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

    QSort 函数思路路:

     

    • 判断 low 是否⼩小于 high;

    • 求得枢轴 ,并且将数组枢轴左边的关键字都⽐它小, 右边的关键字都⽐比枢轴对应的关键字⼤;

    • 将数组一分为二 ,对低子表进行排序,对⾼⼦表进行排序;




      //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); }
      (滑动显示更多)


      来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/70005484/viewspace-2793697/,如需转载,请注明出处,否则将追究法律责任。

      请登录后发表评论 登录
      全部评论
      更多干货内容尽在“逻辑iOS技术号”

      注册时间:2021-08-18

      • 博文量
        16
      • 访问量
        4924