【正文】 表示R[low]是葉子，調(diào)整結(jié)束；否則先令large指向R[low]的左孩子 if(largehigh amp。amp。 R[large].keyR[large+1].key) large++。 //若R[low]的右孩子存在且關鍵字大于左兄弟，則令large指向它 //現(xiàn)在R[large]是調(diào)整結(jié)點R[low]的左右孩子結(jié)點中關鍵字較大者 if(=R[large].key) //temp始終對應R[low] break。 //當前調(diào)整結(jié)點不小于其孩子結(jié)點的關鍵字，結(jié)束調(diào)整 R[low]=R[large]。 //相當于交換了R[low]和R[large] low=large。 //令low指向新的調(diào)整結(jié)點，相當于temp已篩下到large的位置 } R[low]=temp。 //將被調(diào)整結(jié)點放入最終位置上}//==========構(gòu)造大根堆==========void BuildHeap(SeqList R){ //將初始文件R[1..n]構(gòu)造為堆 int i。 for(i=n/2。i0。i) Heapify(R,i,n)。 //將R[i..n]調(diào)整為大根堆}//==========堆排序===========void HeapSort(SeqList R){ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元 int i。 BuildHeap(R)。 //將R[1..n]構(gòu)造為初始大根堆 for(i=n。i1。i){ //對當前無序區(qū)R[1..i]進行堆排序，共做n1趟。 R[0]=R[1]。 R[1]=R[i]。R[i]=R[0]。 //將堆頂和堆中最后一個記錄交換 Heapify(R,1,i1)。 //將R[1..i1]重新調(diào)整為堆，僅有R[1]可能違反堆性質(zhì)。 }} 二路歸并排序的基本思想：假設初始序列n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到[n/2]個長度為2或1的有序子序列；再兩兩歸并，……，如此重復，直到一個長度為n的有序序列為止。//=====將兩個有序的子序列R[low..m]和R[m+1..high]歸并成有序的序列R[low..high]==void Merge(SeqList R,int low,int m,int high){ int i=low,j=m+1,p=0。 //置初始值 RecType *R1。 //R1為局部量 R1=(RecType *)malloc((highlow+1)*sizeof(RecType))。 //申請空間 while(i=m amp。amp。 j=high) //兩個子序列非空時取其小者輸出到R1[p]上 R1[p++]=(R[i].key=R[j].key)? R[i++]:R[j++]。 while(i=m) //若第一個子序列非空，則復制剩余記錄到R1 R1[p++]=R[i++]。 while(j=high) //若第二個子序列非空，則復制剩余記錄到R1中 R1[p++]=R[j++]。 for(p=0,i=low。i=high。p++,i++) R[i]=R1[p]。 //歸并完成后將結(jié)果復制回R[low..high]}//=========對R[1..n]做一趟歸并排序========void MergePass(SeqList R,int length){ int i。 for(i=1。i+2*length1=n。i=i+2*length) Merge(R,i,i+length1,i+2*length1)。 //歸并長度為length的兩個相鄰的子序列 if(i+length1n) //尚有一個子序列，其中后一個長度小于length Merge(R,i,i+length1,n)。 //歸并最后兩個子序列 //注意：若i≤n且i+length1≥n時，則剩余一個子序列輪空，無須歸并}//========== 自底向上對R[1..n]做二路歸并排序===============void MergeSort(SeqList R){ int length。 for(length=1。lengthn。length*=2) //做[lgn]趟排序 MergePass(R,length)。 //有序長度≥n時終止}//==========輸入順序表========void input_int(SeqList R){ int i。 printf(Please input num(int):)。 scanf(%d,amp。n)。 printf(Plase input %d integer:,n)。 for(i=1。i=n。i++) scanf(%d,amp。R[i].key)。}//==========輸出順序表========void output_int(SeqList R){ int i。 for(i=1。i=n。i++) printf(%4d,R[i].key)。}//==========主函數(shù)======void main(){ int i。 SeqList R。 input_int(R)。 printf(\t******** Select **********\n)。 printf(\t1: Insert Sort\n)。 printf(\t2: Bubble Sort\n)。 printf(\t3: Quick Sort\n)。 printf(\t4: Straight Selection Sort\n)。 printf(\t5: Heap Sort\n)。 printf(\t6: Merge Sort\n)。 printf(\t7: Exit\n)。 printf(\t***************************\n)。 scanf(%d,amp。i)。 //輸入整數(shù)17，選擇排序方式 switch (i){ case 1: InsertSort(R)。 break。 //值為1，直接插入排序 case 2: BubbleSort(R)。 break。 //值為2，冒泡法排序 case 3: QuickSort(R,1,n)。 break。 //值為3，快速排序 case 4: SelectSort(R)。 break。 //值為4，直接選擇排序 case 5: HeapSort(R)。 break。 //值為5，堆排序 case 6: MergeSort(R)。 break。 //值為6，歸并排序 case 7: exit(0)。 //值為7，結(jié)束程序 } printf(Sort reult:)。 output_int(R)。}運行結(jié)果：直接插入排序：冒泡法排序：快速排序：直接選擇排序：堆排序：歸并排序：實驗心得：關于排序的數(shù)據(jù)結(jié)構(gòu)實驗。感覺各種排序方法都有各自的特點。直接插入排序是根據(jù)前面一個數(shù)的位置和后面一個相比較直接排 而冒泡法則要經(jīng)過n*(n1)次每次確定一個數(shù)的位置 但是這種方法有點復雜 要循環(huán)n次，而快速排序則是從中間到兩邊 任選一個數(shù)出來把小的排前面 大的排后面 然后重復以上過程 這樣可以有效地節(jié)約時間 每一步都為下一步節(jié)約了時間。而直接選擇排序有兩個序列 也是每一步都為下一步節(jié)約了世界 堆排序巧妙地利用了樹中雙親與孩子的關系 歸并排序則是發(fā)散的 通過遞歸成2的n次方排，通過這幾種排序方法 我更加了解了排序 也知道了許多數(shù)據(jù)結(jié)構(gòu)。42