chap 8排序动态演示排序网站Comparison Sorting Visualization8.1 插入排序算法思想每次将一个待排序的记录插入到前面已经排好序的子序列中直到所有序列插入完成。①直接插入排序代码//直接插入排序voidInsertSort(intA[],intn){inti,j,temp;for(i1;in;i){if(A[i]A[i-1]){tempA[i];for(ji-1;j0A[j]temp;j--)A[j1]A[j];A[j1]temp;}}}例子当13待排序时从后往前依次比较当 前数 比13大的时候A[j] temp)前数后移一个位置( A[j 1] A[j] )当前数不大于13/遍历完 时循环停止在当前数的后一个位置插入13注带哨兵版本//A[0]空出来用于存当前待存元素voidInsertSort(intA[],intn){inti,j;for(i2;in;i){A[0]A[i];if(A[0]A[i-1]){for(ji-1;A[j]A[0];j--)A[j1]A[j];//往后挪一位A[j1]A[0];}}}②折半插入排序待排序记录前面的序列已经有序在查找元素的时候采用折半查找的方法。与折半查找不太相同的是为了保证排序的稳定性当找到和待排记录相等的元素时继续序列右半部分找。代码当low high时折半查找停止将[ low , n - 1]中的元素全部右移voidInsertSort(intA[],intn){inti,j,mid,low,high;for(inti2;in;i){A[0]A[i];if(A[i]A[i-1]){low1,highi-1;while(lowhigh){mid(highlow)/2;if(A[mid]A[0])lowmid1;//等于待排元素的时候向区间的右端查询elsehighmid-1;}for(ji-1;jlow;j--)A[j1]A[j];A[high1]A[0];}}}③希尔排序算法思想先追求表中元素部分有序再逐渐逼近全局有序​ 先将待排序表分割成若干形如 L[ i, i d, i 2d, i 3d, …]这样的特殊子表对各个子表分别进行插入排序。再缩小增量d,重复上述过程直至d 1.例子​ 当d 4时i 1, i 4 5 为一组49和76为一组i 2 i 4 6为一组38和13为一组 i 3, i 4 7为一组65和27为一组 i 4i 4 876和49为一组。​ 当d 2时i 1 357为一组 i 2 4 6 8为一组​ 当d 1时i 1, 2, 3, 4, 5, 6, 7, 8为一组代码voidShellSort(intA[],intn){intd,i,j;//d循环步长; i循环各个不同的子序列; j循环子序列里面的元素间隔步长dfor(dn/2;d1;d/2){for(i1d;in;i){if(A[i]A[i-d]){A[0]A[i];//A[0]不是哨兵暂存此刻待排元素for(ji-d;j0A[0]A[j];j-d)A[jd]A[j];A[jd]A[0];}}}}稳定性直接插入排序稳定希尔排序不稳定。8.2 交换排序①冒泡排序算法思想从后往前两两比较相邻元素若为逆序则交换他们当某一趟没有元素交换的时候说明元素已经有序代码voidBubbleSort(intA[],intn){for(inti0;in-1;i){booltagfalse;for(intjn-1;ji;j--){if(A[j-1]A[j])swap(A[j-1],A[j]);tagtrue;}if(tagfalse)return;}}intswap(inta,intb){inttempa;ab;btemp;}性能复杂度最好最坏平均时间复杂度O(n)O(n^2)O(n^2)比较次数n - 1n(n-1)/2/交换次数03*n(n - 1)/2/一次交换需要移动三次元素稳定性稳定适用于链表和顺序表②快速排序***算法思想每次选择一个枢轴一般为首元素一趟排序划分为左右两个子表使得左子表中的元素都小于枢轴右子表中的元素都大于等于枢轴代码(很重要:voidQuickSort(intA[],intlow,inthigh){if(lowhigh){intpivotposPartition(A,low,high);QuickSort(A,low,pivotpos-1);QuickSort(A,pivotpos1,high);}}intPartition(intA[],intlow,inthigh){intpivotA[low];while(lowhigh){while(lowhighA[high]pivot)high--;A[low]A[high];while(lowhighA[low]pivot)low;A[high]A[low];}A[low]pivot;returnlow;}性能复杂度最坏最优平均时间复杂度O(n^2)O(n*logn)接近O(n * log n)空间复杂度O(n)O(logn)O(log n)稳定性不稳定适用于顺序表8.3 选择排序算法思想每一趟在后面的n - i 1个待排序列元素中选取关键字最小的元素 作为有序子序列的第i个元素①简单选择排序算法思想假设排序表为L[1…n],第i趟排序从L[i…n]中选出关键字最小的元素并与L(i)交换。​ 每一趟可以确定一个元素的最终位置​ 经过n- 1趟整个序列有序voidSelectSort(intA[],intn){for(inti0;in;i){intmini;for(intji1;jn;j){if(A[j]A[min])minj;}if(min!i)swap(A[i],A[min]);}}性能复杂度时间复杂度O(n^2)空间复杂度O(1)稳定性不稳定适用于链式存储和线性存储的顺序表②堆排序***2.1大跟堆建立算法思想根大于左右子树建立的过程让小元素下坠//建立大根堆voidBuildMaxHeap(intA[],intlen){for(intilen/2;i0;i--){HeadAdjust(A,i,len);}}//将以k为根的子树调整为大根堆voidHeadAdjust(intA[],intk,intlen){A[0]A[k];for(inti2*k;ilen;i*2){if(ilenA[i]A[i1])i;if(A[0]A[i])break;else{A[k]A[i];ki;}}A[k]A[0];}例如将53作为根调整大根堆。A[0] A[k] 53i 2, A[i] A[i 1], i 353 87, A[k] 87, k 3一次for循环调整完第二次for循环k 3, i 6, 65 78, i 7A[0] 53 78, A[k] 78, k 7下一次循环i不满足len,退出for循环然后把A[0] 53放入k的位置。2.2堆排序算法思想每一趟将堆顶元素加入有序子序列与堆的最后一个元素互换再将待排序序列再次调整为大根堆大根堆排序最后得到的是一个递增的序列每次找出最大的堆顶但是给他换到最下面去了//建立大根堆voidBuildMaxHeap(intA[],intlen){for(intilen/2;i0;i--){HeadAdjust(A,i,len);}}//将以k为根的子树调整为大根堆voidHeadAdjust(intA[],intk,intlen){A[0]A[k];for(inti2*k;ilen;i*2){if(ilenA[i]A[i1])i;if(A[0]A[i])break;else{A[k]A[i];ki;}}A[k]A[0];}//堆排序的完整逻辑voidHeapSort(intA[],intlen){BuildMaxHeap(A,len){for(intilen;i1;i--){swap(A[i],A[1]);HeadAdjust(A,1,i-1);}}}性能时间复杂度建堆O(n) 排序O(n*logn) O(n * logn)空间复杂度O(1)稳定性不稳定适用于线性存储线性表易考点1下坠一次若有两个孩子需要对比两次关键字 若有一个孩子需要对比一次2插入插入元素放到表尾根据大/小根堆的要求不断上升直至无法上升 O(log n)3删除删除元素的位置用表尾元素然后根据大/小根堆的要求不断下降 O(log n)4大根堆得到的是递增序列 小根堆得到的是递减序列8.4 归并排序核心操作把数组中的两个有序的组序列合并成一个int*B(int*)malloc(n*sizeof(int))//B辅助数组voidMerge(intA[],intlow,intmid,inthigh){inti,j k;for(klow;khigh;k)B[k]A[k];//复制A数组中的元素到Bfor(ilow,jmid1,ki;imidjhigh;k){if(B[i]B[j])A[k]B[i];elseA[k]B[j]}while(imid)A[k]B[i];//剩余的元素while(jhigh)A[k]B[j];}voifMergerSort(intA[],intlow,inthigh){if(lowhigh){intmid(highlow)/2;MergerSort(A,low,mid-1);MergerSort(A,mid1,high);}}性能复杂度时间复杂度O(n*logn); 空间复杂度O(n)稳定性稳定适用于顺序表和链表8.5 基数排序不依赖元素之间的比较而基于关键字各位的大小进行排序最低位优先法LSD按关键字权值递增依次进行排序关键字有d个分量各位取值0~r-1分配O(n) 收集O®性能时间复杂度O(d(nr))空间复杂度O®稳定的适用于顺序表和链表*8.6计数排序不依赖于比较的算法对每个待排元素x, C数组先统计各个元素出现的次数 再遍历一次使得C[i]中存储的是 i的元素然后就可以定位元素的位置。元素取值[0, k)voidCountSort(intA[],intB[],intn,intk){inti,C[k];for(i0;in;i)C[i]0;for(i0;in;i)C[A[i]];for(i1;in;i)C[i]C[i-1];for(in-1;i0;i--){//从后往前确保稳定C[A[i]]--;//本身--B[C[A[i]]A[i];//C[A[i]]代表次序A[i]元素本身}}性能复杂度时间复杂度 O(n k)空间复杂度 O(n k)稳定的适用于顺序表对比