c語言各種排序法詳解

一插入排序1.1直接插入排序基本思想：每次將一個待排序額記錄按其關鍵碼的大小插入到一個已經排好序的有序序列中，直到全部記錄排好序。圖解：代碼實現：[cpp]viewplaincopy//直接順序排序voidInsertSort(intr[],intn){for(inti=2;i<n;i++){r[0]=r[i];//設置哨兵for(intj=i-1;r[0]<r[j];j--)//尋找插入位置r[j+1]=r[j];//記錄后移r[j+1]=r[0];}for(intk=1;k<n;k++)cout<<r[k]<<"”；cout<<"\n";}1.2希爾排序基本思想是：先將整個待排序記錄序列分割成若干個子序列，在在序列內分別進行直接插入排序，待整個序列基本有序時，再對全體記錄進行一次直接插入排序。圖解：代碼實現：[cpp]viewplaincopy<spanstyle=font-size:14px;">//希爾排序voidShellSort(intr[],intn){inti;intd;intj;for(d=n/2;d>=1;d=d/2)//以增量為d進行直接插入排序{for(i=d+1;i<n;i++){11.r[0]=r[i];//暫存被插入記錄

for(j=i-d;j>0&&r[0]<r[j];j=j-d)r[j+d]=r[j];//記錄后移d個位置r[j+d]=r[0];}}for(i=1;i<n;i++)cout<<r[i]<<"";cout<<”\n”；}</span>交換排序兩兩比較相鄰記錄的關鍵碼,起泡排序是交換排序中最簡單的排序方法，其基本思想是:如果反序則交換，直到沒有反序的記錄為止。兩兩比較相鄰記錄的關鍵碼,圖解：代碼實現：[cpp]viewplaincopy<spanstyle="font-size:14px;">//起泡排序voidBubbleSort(intr[],intn){inttemp;intexchange;intbound;exchange=n-1;//第一趟起泡排序的范圍是r[0]到r[n-1]while(exchange)//僅當上一趟排序有記錄交換才進行本趟排序{bound=exchange;exchange=0;for(intj=0;j<bound;j++)//—趟起泡排序if(r[j]>r[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;//記錄每一次發(fā)生記錄交換的位置}}for(inti=0;i<n;i++)cout<<r[i]<<"";cout<<"\n";}</span>2.2快速排序基本思想:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。圖解：代碼實現：[cpp]viewplaincopy//快速排序一次劃分intParTiTion(intr[],intfirsT,intend){inti=firsT;//初始化intj=end;intTemp;while(i<j)TOC\o"1-5"\h\z{while(i<j&&r[i]<=r[j])j--；//右側掃描if(i<j){Temp=r[i];//將較小記錄交換到前面r[i]=r[j];r[j]=Temp;i++;}while(i<j&&r[i]<=r[j])i++;//左側掃描if(i<j){Temp=r[j];r[j]=r[i];r[i]=Temp;//將較大記錄交換到后面j--;}}returni;//i為軸值記錄的最終位置}//快速排序voidQuickSorT(intr[],intfirsT,intend){if(firsT<end){//遞歸結束intpivoT=ParTiTion(r,firsT,end);//一次劃分

QuickSort(rfirst,pivot-1);//遞歸地對左側子序列進行快速排序QuickSort(r,pivot+1,end);//遞歸地對右側子序列進行快速排序}}三選擇排序3?1簡單選擇排序基本思想:設所排序序列的記錄個數為n。取1,2,...,n-1,從所有n-i+1個記錄(Ri,Ri+1,...,Rn)中找出排序碼最小的記錄，與第i個記錄交換。執(zhí)行n-1趟后就完成了記錄序列的排序。圖解：代碼實現：[cpp]viewplaincopy//簡單選擇排序voidSelectSort(intr[],intn){inti;intj;intindex;inttemp;for(i=0;i<n-1;i++)//對n個記錄進行n-1趟簡單選擇排序{index=i;for(j=i+1;j<n;j++)//在無序區(qū)中選取最小記錄if(r[j]<r[index])index=j;if(index!=i)TOC\o"1-5"\h\z{temp=r[i];r[i]=r[index];r[index]=temp;}}for(i=0;i<n;i++)cout<<r[i]<<"”；cout<<"\n";}3.2堆排序堆的定義

堆是具有下列性質的完全二叉樹：每個結點的值都小于或等于其左右孩子結點的值（小根堆）；或者每個結點的值都大于或等于其左右孩子結點的值（大根堆）。大根堆和小根堆：根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆，又稱最小堆。根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最大者,稱為大根堆，又稱最大堆。注意：①堆中任一子樹亦是堆。②以上討論的堆實際上是二叉堆（BinaryHeap），類似地可定義k叉堆。假設當前要篩選結點的編號為k,堆中最后一個結點的編號為m,并且結點k的左右子樹均是堆（即r[k+1]~r[m]滿足堆的條件），則篩選算法用偽代碼可描述為：具體的篩選代碼如下：[cpp]viewplaincopy//篩選法調整堆voidSift（intr[],intk,intm）TOC\o"1-5"\h\z{inti;intj;inttemp;i=k;j=2*i+1;//置i為要篩的結點，j為i的左孩子while（j<=m）//篩選還沒有進行到葉子{if（j<m&&r[j]<r[j+1]）j++;//比較i的左右孩子，j為較大者if（r[i]>r[j]）break;//根結點已經大于左右孩子中的較大者elseTOC\o"1-5"\h\z{temp=r[i];r[i]=r[j];r[j]=temp;//將根結點與結點j交換i=j;j=2*i+1;//被篩結點位于原來結點j的位置}}}堆排序堆排序的基本思想是：首先將待排序的記錄序列構造成一個堆，此時，選出了堆中所有記錄的最大者即堆頂記錄，然后將它從堆中移走（通常將堆頂記錄和堆中最后一個記錄交換）,并將剩余的記錄再調整成堆，這樣又找出了次大的記錄，以此類推，直到堆中只有一個記錄為止。（1）用大根堆排序的基本思想先將初始文件R[仁n]建成一個大根堆，此堆為初始的無序區(qū)再將關鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keysSR[n].key由于交換后新的根R[1]可能違反堆性質，故應將當前無序區(qū)R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關系R[1..n-2].keys<R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。直到無序區(qū)只有一個元素為止。（2）大根堆排序算法的基本操作：初始化操作：將R[1..n]構造為初始堆；每一趟排序的基本操作:將當前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換,然后將新的無序區(qū)調整為堆（亦稱重建堆）。只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴大至整個向量為止代碼實現：[cpp]viewplaincopy//堆排序voidHeapSort(intr[],intn){inti;inttemp;for(i=n/2;i>=0;i--)//初始建堆，從最后一個非終端結點至根結點Sift(r,i,n);for(i=n-1;i>0;i--)//重復執(zhí)行移走堆頂及重建堆的操作{temp=r[i];r[i]=r[0];r[0]=temp;Sift(r,0,i-1);}for(i=0;i<n;i++)cout<<r[i]<<"";cout<<"\n";}歸并排歸并排二路歸并排序基本思想：將若干個有序序列進行兩兩歸并，直至所有待排序記錄都在一個有序序列為止。一路歸并算法實現：[cpp]viewplaincopy//一次歸并voidMerge(intr[],intr1[],ints,intm,intt){inti=s;intj=m+1;intk=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中較小者放入r1[k]elser1[k++]=r[j++];}if(i<=m)while(i<=m)//若第一個子序列沒處理完，則進行收尾處理r1[k++]=r[i++];elsewhile(j<=t)//若第二個子序列沒處理完，則進行收尾處理r1[k++]=r[j++];TOC\o"1-5"\h\z}[cpp]viewplaincopy//一趟歸并voidMergePass(intr[],intr1[],intn,inth){inti=0;intk;while(i<=n-2*h)//待歸并記錄至少有兩個長度為h的子序列{Merge(r,r1,i,i+h-1,i+2*h-1);i+=2*h;}if(i<n-h)

Merge(r,r1,i,i+h-1,n);//待歸并序列中有一個長度小于helsefor(k=i;k<=n;k++)//待歸并序列中只剩一個子序列r1[k]=r[k];TOC\o"1-5"\h\z}〃歸并排序的非遞歸算法voidMergeSort1(intr[],intr1[],intn){inth=1;inti;while(h<n){MergePass(r,r1,n-1,h);//歸并h=2*h;MergePass(r1,r,n-1,h);h=2*h;}for(i=0;i<n;i++)cout<<r[i]<<"”；cout<<"\n";}下面看看二路歸并排序的遞歸實現[cpp]viewplaincopy//歸并排序的遞