嗨，这里是逻辑iOS技术号：一个让知识变得感性，让学习变得轻松！活跃的技术小站，希望给你的生活与技术带来意思不一样！关注公众号，回复“ 面试题 ”，即可领取更多大厂面试题型哦~ 小逻辑相信我们的生活不止眼前的苟且，还有我们向往的诗和大厂高薪工作~
归并排序
//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中记录由小到大地并入TRfor(j=m+1,k=i;i<=m && j<=n;k++){if (SR[i]TR[k]=SR[i++];elseTR[k]=SR[j++];}//2.将剩余的SR[i..mid]复制到TRif(i<=m){for(l=0;l<=m-i;l++)TR[k+l]=SR[i+l];}//3.将剩余的SR[j..mid]复制到TRif(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// 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;}}
快速排序
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);}