c语言各种排序法详解.docVIP

c语言各种排序法详解 c语言各种排序法详解 PAGE标准文案 c语言各种排序法详解 一 ?插入排序 ?直接插入排序 基本思想：每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序。 图解： 代码实现： [cpp]?view plain?copy n]建成一个大根堆，此堆为初始的无序区 ② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key ③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 …… 直到无序区只有一个元素为止。 （2）大根堆排序算法的基本操作： ① 初始化操作：将R[1..n]构造为初始堆； ② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。 注意： ①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。 ②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止 代码实现： [cpp]?view plain?copy //堆排序?? void?HeapSort(int?r[?],?int?n)?? {?? ????? ??int?i;?? ??int?temp;?? ??for?(i=n/2;?i=0;?i--)????????????????//初始建堆，从最后一个非终端结点至根结点?? ?????Sift(r,?i,?n)?;??????? ???for?(i=n-1;?i0;?i--)????????????????//重复执行移走堆顶及重建堆的操作?? ???{?? ???????temp=r[i];?? ???????r[i]=r[0];?? ???????r[0]=temp;?? ??????Sift(r,?0,?i-1);?? ???}?? ???for(i=0;in;i++)?? ??????coutr[i]?;?? ???cout\n;?? }?? 四 归并排序 二路归并排序 基本思想：将若干个有序序列进行两两归并，直至所有待排序记录都在一个有序序列为止。 一路归并算法实现： [cpp]?view plain?copy //一次归并?? void?Merge(int?r[],?int?r1[],?int?s,?int?m,?int?t)?? {?? ?? ????int?i=s;?? ????int?j=m+1;?? ????int?k=s;?? ???????? ?????while?(i=m??j=t)?? ?????{????? ?????????if?(r[i]=r[j])??? ?????????????r1[k++]=r[i++];????????????//取r[i]和r[j]中较小者放入r1[k]?? ?????????else??? ?????????????r1[k++]=r[j++];??? ?????}?? ??????if?(i=m)??? ??????????while?(i=m)??????????????????//若第一个子序列没处理完，则进行收尾处理??????????? ??????????????r1[k++]=r[i++];??? ??????else???? ??????????while?(j=t)??????????????????//若第二个子序列没处理完，则进行收尾处理?????????? ????????????r1[k++]=r[j++];??? }?? [cpp]?view plain?copy //一趟归并?? void?MergePass(int?r[?],?int?r1[?],?int?n,?int?h)?? {?? ????int?i=0;?? ????int?k;?? ?? ???while?(i=n-2*h)?????????????????????//待归并记录至少有两个长度为h的子序列?? ???{?? ?????Merge(r,?r1,?i,?i+h-1,?i+2*h-1);?? ????????i+=2*h;?? ???}?? ???if?(