陣列排序參考

實驗目的】
1. 熟練掌握各種排序的演算法思想、方法及穩定性；
2. 掌握快速排序、堆排序、歸併排序的方法實現；
3. 對已知一組資料，能寫出其具體的排序過程、演算法及完整程式，並上機調試；
4. 瞭解每一種排序的時間及空間複雜度。

第一節知識準備

一、基本概念和術語
1．排序(Sorting)是電腦程式設計中的一種重要操作，其功能是對一個資料元素集合或序列重新排列成一個按資料元素的某個資料項目有序的序列。
2．排序碼或關鍵碼：資料元素可以有多個資料項目，而作為排序依據的資料項目稱為“排序碼”，也即資料元素的關鍵碼。
表9-1是一個職工登記表，若以每個記錄的職工號為關鍵字，並作為排序碼，則所有7條記錄可簡記為：{（101，348），（102，374），（103，324），（104，305），（105，429），（106，284），（107，324）}

表9-1  職工資料表
職工號姓名基本工資出生日期車間號
101 王英 348 51/04/25 3
102 吳進 374 61/03/12 2
103 趙飛 324 53/06/28 4
104 劉曉 305 70/03/26 3
105 李平 429 59/12/20 1
106 盧明 284 75/01/05 5
107 李敏 324 64/10/01 1

若按基本工資為排序碼，並以遞增次序對記錄進行重排，則結果為：{（106，284），（104，305），（103，324），（107，324），（101，348），（102，374），（105，429）}
若以每個記錄的車間號碼為排序碼，並以遞減次序對記錄進行重排，則結果為：{（106，5），（103，4），（101，3），（104，3），（102，2），（105，1），（107，1）}。
一組記錄按排序碼的遞增或遞減次序排列得到的結果稱為有序表；而把排序前的表稱之為無序表。若有序表是按排序碼遞增的順序排列的，則稱為昇冪表或正序表；反之則稱之為降冪表或逆序表。
3．排序的穩定性：對於具有同一排序碼的多個記錄來說，若對任意的資料元素序列，使用某種排序方法按關鍵碼進行排序,具有相同關鍵碼的不同元素間的位置領先關係，排序前與排序後保持一致，稱此排序方法是穩定的。
4．排序的不穩定性：若對任意的資料元素序列，使用某種排序方法按關鍵碼進行排序,具有相同關鍵碼的不同元素間的位置領先關係，排序前與排序後不能保持一致的排序方法則稱為不穩定的。
5．內部排序：待排序列完全在記憶體中進行的排序過程，稱為內排序。
6．外部排序：排序過程需要不斷在記憶體和外存之間進行資料交換，這種排序過程叫外排序。
二、內部排序的分類
1. 插入排序
設有n個記錄,存放在陣列r中，重新安排記錄在陣列中的存放順序，使得按關鍵碼有序。即：r[1].key≤r[2].key≤……≤r[n].key。
按照插入一個元素到一個有序表中的方法不同，可以分為：直接插入排序、折半插入排序(2-路插入排序)及希爾排序(Shell’s Sort)。
（1）直接插入排序
是一種最簡單的排序方法，其基本操作是每次從無序表中取出一個元素，將之插入到已排好序的表中的適當位置，從而得到一個新的、記錄數增1的1有序表。
對n個記錄的表，可從第2個記錄開始直到第n個記錄，逐個向有序表中進行插入操作，從而得到n個記錄按關鍵碼有序的表。
設r[1] ，r[2]，……，r[j-1]為長為j-1的有序表，現要將r[j]插入這個有序表，形成長為j的新的有序表，演算法過程如下：
【演算法描述】
Step1:  r[0]=r[j]；       //設置r[0]為哨兵
i=j-1；          //從第j-1個記錄向前測試插入位置
Step2:  若r[0].key≥r[i].key，轉Step4。 //插入位置確定
Step3:  若r[0].key < r[i].key時，
r[i+1]=r[i]；i=i-1；轉Step2。    //調整待插入位置
Step4:  r[i+1]=r[0]；結束。                   //存放待插入記錄
【例題分析】向有序表中插入一個記錄的過程如下：
初始情況：設r[1],r[2],r[3],r[4]已經有序，現插入r[5]
      r[1]  r[2] r[3] r[4] r[5]
      2    10    18    25    9
j=5
r[0]=r[j]；i=j-1；                   //初始化，設置待插入位置
      2 10    18    25    □       //r[i+1]為待插入位置
i=4，r[0] < r[i]，r[i+1]=r[i]；i--； //調整待插入位置
      2 10    18    □    25
i=3，r[0] < r[i]，r[i+1]=r[i]；i--； //調整待插入位置
      2 10    □    18    25
i=2，r[0] < r[i]，r[i+1]=r[i]；i--； //調整待插入位置
         2 □    10    18    25
i=1，r[0] ≥r[i]，r[i+1]=r[0]；       //插入記錄
         2    9    10    18    25       //插入過程結束

（2）希爾排序：先將待排序記錄的序列按某個間隔長度分割成為若干個子序列分別進行直接插入排序，重複進行資料分割，每次分割的間隔長度逐步縮小，直到最後間隔長度為1時，對全體記錄進行一次直接插入排序，這時所有記錄按關鍵字有序，排序結束。具體排序過程如下：
① 選擇一個步長序列t1，t2，…，tk，其中ti<ti+1，tk=1；
② 按步長序列個數k，對序列進行k趟排序；
③ 每趟排序，根據對應的步長ti，將待排序列分割成若干長度為m的子序列，分別對各子系列進行直接插入排序。當步長因數為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。
【例題分析】待排序列為 39，80，76，41，13，29，50，78，30，11，100，7，41，86。
步長因數分別取5、3、1，則排序過程如下：
p=5 39  80  76  41  13  29  50  78  30  11  100 7  41  86
      └─────────┴─────────┘
         └─────────┴──────────┘
         └─────────┴──────────┘
               └─────────┴──────────┘
                     └─────────┘
子序列分別為{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}。
第一趟排序結果：
p=3 29 7  41  30  11  39  50  76  41  13  100  80  78  86
   └─────┴─────┴─────┴──────┘
         └─────┴─────┴─────┴──────┘
            └─────┴─────┴──────┘
子序列分別為{29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}。
第二趟排序結果：
p=1 13 7  39  29  11  41  30  76  41  50  86  80  78  100
此時，序列基本“有序”，對其進行直接插入排序，得到最終結果：
7  11  13  29  30  39  41  41  50  76  78  80  86  100
希爾排序的效率是非常高的，因為它有效地利用了直接插入排序的優點：開始分組的時候，每組的元素比較少，排序速度比較快；到後來，每組元素比較多時，元素已經基本有序了，這樣排序速度也比較快。
（3）2-路插入排序：
設在一個已排好序的序列中v[0]，v[1]，…，v[i-1]中，在插入v[i]時，利用折半查找法尋找v[i]的插入位置來完成的排序過程。
2. 交換排序：主要是通過兩兩比較待排記錄的關鍵碼，若發生與排序要求相逆，則交換之。根據交換記錄的不同，可分為：快速排序、冒泡排序。
（1）快速排序（Quick Sort）是通過比較關鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點)，將待排序列分成兩部分。其中，一部分所有記錄的關鍵碼大於等於支點記錄的關鍵碼，另一部分所有記錄的關鍵碼小於支點記錄的關鍵碼。我們將待排序列按關鍵碼以支點記錄分成兩部分的過程，稱為一次劃分。對各部分不斷劃分，直到整個序列按關鍵碼有序，整個排序結束。
此種排序方法是不穩定的，且其時間複雜度在平均狀況時為，最壞情況其時間複雜度為。
（2）冒泡排序(Bubble Sort)：通過相鄰元素之間的比較和交換使排序碼較大的元素逐漸移向序列的尾部移動，就象氣泡從水底浮向水面一樣，因此而得名。
冒泡排序的一趟冒泡過程：設1<j≤n，r[1],r[2],•••,r[j]為待排序列，通過兩兩比較、交換，重新安排存放順序，使得r[j]是序列中關鍵碼最大的記錄。
對n個待排序的表，第一趟冒泡得到一個關鍵碼最大的記錄r[n]，第二趟冒泡對n-1個待排序的表，再得到一個關鍵碼最大的記錄r[n-1]，如此重複，直到n個記錄按關鍵碼有序的表，整個排序結束。
【演算法描述】
Step1: j=n； //從n記錄的表開始
Step2: if (j<2) 排序結束；
Step3: i=1；    //一趟冒泡，設置從第1個記錄開始進行兩兩比較，
Step4: if (i≥j)
{一趟冒泡結束，j=j-1；冒泡表的記錄數-1，轉Step2；}
         else 轉Step5；
Step5: for (i=1;i<=j-n;i+)
if (r[i].key>r[i+1].key) 將r[i]與r[i+1]互換；
Step6: 迴圈結束，轉Step4；
   冒泡排序其時間複雜度為：在最壞情況下為O(n2)，最好情況下為O（n）。
思考：若所要求排序的序列是以其鏈式存貯結構，其演算法如何描述呢？
3. 選擇排序：從欲排序的n個資料中，以線性查找的方式找出最小的元素和第一個元素交換，再從剩下的（n-1）個資料中，找出最小的元素和第二個元素交換，以此類推，直到所有的元素均已排序完成。分為簡單選擇排序和堆排序。
（1）簡單選擇排序
操作方法：第一趟，從n個記錄中找出關鍵碼最小的記錄與第一個記錄交換；第二趟，從第二個記錄開始的n-1個記錄中再選出關鍵碼最小的記錄與第二個記錄交換；如此重複，第i趟，則從第i個記錄開始的n-i+1個記錄中選出關鍵碼最小的記錄與第i個記錄交換，直到整個序列按關鍵碼有序。
（2）堆排序(Heap Sort)
設有n個元素的序列 k1，k2，…，kn，當且僅當滿足下述關係之一時，稱之為堆。

對於上述條件中第①種情況的堆稱之為大根堆，相應地第②種情況稱之為小根堆。見圖9-1的圖示。
若以一維陣列存儲一個堆，則堆對應一棵完全二叉樹，且所有非葉結點的值均不大於(或不小於)其子女的值，根結點的值是最小(或最大)的。

圖9-1  大根堆和小根堆圖示

設有n個元素，將其按關鍵碼排序。首先將這n個元素按關鍵碼建成堆，將堆頂元素輸出，得到n個元素中關鍵碼最小(或最大)的元素。然後，再對剩下的n-1個元素建成堆，輸出堆頂元素，得到n個元素中關鍵碼次小(或次大)的元素。如此反復，便得到一個按關鍵碼有序的序列。稱這個過程為堆排序。
因此，實現堆排序需解決兩個問題：
①如何將n個元素的序列按關鍵碼建成堆；② 輸出堆頂元素後，怎樣調整剩餘n-1個元素，使其按關鍵碼成為一個新堆。
首先，討論輸出堆頂元素後，對剩餘元素重新建成堆的調整過程。
調整方法：設有m個元素的堆，輸出堆頂元素後，剩下m-1個元素。將堆底元素送入堆頂，堆被破壞，其原因僅是根結點不滿足堆的性質。將根結點與左、右子女中較小(或小大)的進行交換。若與左子女交換，則左子樹堆被破壞，且僅左子樹的根結點不滿足堆的性質；若與右子女交換，則右子樹堆被破壞，且僅右子樹的根結點不滿足堆的性質。繼續對不滿足堆性質的子樹進行上述交換操作，直到葉子結點，堆被建成。稱這個自根結點到葉子結點的調整過程為篩選。
【例題分析】

圖9-2自堆頂到葉子的調整過程
再討論對n個元素初始建堆的過程。
建堆方法：對初始序列建堆的過程，就是一個反復進行篩選的過程。n個結點的完全
子樹成為堆，之後向前依次對各結點為根的子樹進行篩選，使之成為堆，直到根結點。
  所以堆排序是對n個元素的序列進行排序，先將其建成堆，以根結點與第n個結點交換；調整前n-1個結點成為堆，再以根結點與第n-1個結點交換；重複上述操作，直到整個序列有序。

【例題分析】

4.歸併排序：是將兩個或兩個以上的有序表組合成一個新的表。
所謂二路歸併排序是指將兩個有序表合併成一個有序表。
設r[u…t]由兩個有序子表r[u…v-1]和r[v…t]組成，兩個子表長度分別為v-u,t-v+1。合併方法為：
Step1: i=u；j=v；k=u；    //置兩個子表的起始下標及輔助陣列的起始下標
Step2:若i>v 或 j>t，轉Step4;  //其中一個子表已合併完，比較選取結束
Step3:  //選取r[i]和r[j]關鍵碼較小的存入輔助陣列rf
如果r[i].key<r[j].key，rf[k]=r[i]； i++； k++；轉Step2;
否則，rf[k]=r[j]； j++； k++；轉Step2;
Step4: //將尚未處理完的子表中元素存入rf
如果i<v，將r[i…v-1]存入rf[k…t]    //前一子表非空
如果j<=t，將r[i…v]存入rf[k…t]    //後一子表非空
Step5:合併結束。

三、內部排序演算法小結
1．從時間複雜度，直接插入排序、選擇排序、氣泡排序其為O（n2）；堆排序、快速排序、歸併排序的時間複雜度為O（nlog2n）；當然對每種排序法，還要分其最好的情況和最壞情況以及平均的情況。
2．就空間複雜度而言，歸併排序的空間複雜度為O（n）；快速排序的空間複雜度為O（log2n）；而其他排序的空間複雜度為O（1）。
3．就穩定性而言，直接插入排序、冒泡排序、歸併排序為穩定排序；而選擇排序、快速排序和堆排序為非穩定的排序。

第二節雙向排序實驗

【問題描述】
試設計一個程式來修改冒泡排序過程以實現雙向排序。
冒泡排序是對每兩個相鄰的記錄的關鍵字進行比較，雙向冒泡程式是每一趟通過每兩個相鄰的關鍵字進行比較，產生最小和最大的元素，並放在其相應位置上。
【資料描述】
#define maxsize 50;
struct node
{ElemType  key;

};
struct  node  sqlist[maxsize];
【演算法描述】
void  doublebubble(struct node  r[])
{ int i=1,j,b=1;
struct node  t;
while  (b)
{ b=0;
for (j=n-i+1;j>=i+1;j--)
if (r[j].key<r[j-1].key)
{ b=1;  t=r[j];
r[j]=r[j-1];
r[j-1]=t;
}
for (j=i+1;j<=n+i-1;i++)
if (r[j].key>r[j+1].key)
{ b=1;  t=r[j];
r[j+1]=r[j];
r[j+1]=t;
}
i++;
}
}

【C語言根源程式】
#define maxsize 20
struct node
{int key;
}sqlist[maxsize];
void  doublebubble(struct node r[],int n)
{  int i=0,j=n-1,l,b=1;
struct  node  t;
while  (b)
{ b=0;
for (l=j;l>i;l--)
if (r[l].key<r[l-1].key) /*找出最小值元素*/
{ b=1;  t=r[l];
r[l]=r[l-1];
r[l-1]=t;
}
i++;
for (l=i;l<j;l++)
if (r[l].key>r[l+1].key) /*找出最大值元素*/
{ b=1;  t=r[l+1];
r[l+1]=r[l];
r[l]=t;
}
j--;
}
}
main( )  /*主函數*/
{int i,n,temp;
struct node  r[20];
printf("input the numbers of the table:\n");
scanf("%d",&n);  /*輸入待排序的元素個數*/
for (i=0 ;i<n; i++)
{scanf("%d", &temp);    /*輸入待排序的元素的關鍵碼（其他資料項目略）*/
r[i].key=temp;
}
doublebubble(r,n);
for (i=0 ;i<n; i++)
printf("%5d",r[i].key);
printf("\n");
}
【實驗題】
1．試對上述演算法進行改進，以使每一趟的冒泡過程都輸出相應的結果。
2．改進冒泡排序，試編制一個程式，對一個待排序的資料集合進行奇偶轉換排序；
（說明：奇偶排序是指第一趟對所有奇數的i，將a[i]和a[i+1]進行比較，第二趟是對所有偶數的i，將a[I]和進行比較a[i+1]，每次比較時，若a[i]>a[i+1]，則將二者交換，重複上述二趟過程的交換進行，直到整個陣列有序。）

第三節 2-路插入排序實驗

【問題描述】
寫出插入排序中的2-路插入排序演算法。
它是在折半插入排序的基礎之上，為減少排序過程中的移動記錄的次數而改進而來的。
若待排序的n個資料在一個陣列r[]中，額外需要n個資料的輔助空間為d[]，其方法為：
step1：d[1]=r[1]//將d[1]看成在排好序的序列中處於中間位置的記錄。
Step2：將r[2…n]中的每個記錄依次插入到d[1]之前或之後的有序序列中。有兩種情況：
(1)若r[i]的關鍵碼小於d[1]的關鍵碼，則將r[i]插入到d[1]之前的有序表中；
(2)反之則將r[i]插入到d[1]之後的有序表中。
Step3：在演算法在實現時，把d[]陣列看成一個迴圈向量，並設兩個指標first和final分別指示排序過程中得到的有序序列中的第一個記錄和最後一個記錄在d[]中的位置。
Step4：在把r[i]插入到d[1]之前或之後的有序表中時，同樣要能快速的找出其應該插入的位置，這裏就使用折半查找方法來快速定位。
【例題分析】
設待排序序列r[4]={20,5,15,30}，按上述方法，有：
step1：d[1]=r[1]=20。則陣列D中資料變為：
且first=1，final=1；
Step2：將r[2]=5的值插入到D中合適的位置。由於r[2]=5的值小於d[1]=20。調用search_bin函數，求出其在d[1]之前的有序表的位置為1，又由於此時first=1，根據演算法，它應放在d[4]中。此時first=4，而final=1；
Step 3：將r[3]=15插入到D陣列中的合適位置。由於r[3]=15小於d[1]=20的值，調用search_bin函數，求出應在D[1]之後的有序表中的位置為4，根據演算法，它放於d[4]中，此時，應將元素5前移至d[3]中，first=3，而final=1；
Step4：將r[4]=30插入到D陣列中的合適位置。由於r[4]=30大於d[1]=20的值，調用search_bin函數，求出應在D[1]之後的有序表中的位置為2，根據演算法，它放於d[2]中，此時，指針變化為：first=3，final=2；
Step5：最後輸出已排好的序列。由於D陣列是一個迴圈陣列，所以輸出時，從陣列D的下標從first開始到final結束。所以輸出的序列為：5、15、20、30。
【資料描述】
#define  maxsize 20

typedef  int  ElemType
struct node
{ElemType  key;
……//其他資料項目
}node  r[maxsize];
【演算法描述】
int search_bin(struct node d[] , int low ,int high , keytype x)
//折半查找，找出應插入的位置mid
{ int  mid;
while (low<=high)
{mid= ( low+high) / 2;
if  （x<d[mid].key） high=mid-1; //判斷並同時修改指針
else  low =mid+1;
}
return mid;  //返回應插入的位置
}
【C語言根源程式】
#include <stdio.h>
#include <math.h>
#define  maxsize 20
typedef  int  ElemType
struct node
{ElemType  key;
   … /*其他資料項目
   } r[maxsize];
int search_bin(struct node d[] , int  low , int high ,  int x)
/*折半查找，找出應插入的位置mid */
{ int  mid;
while (low<=high)
{ mid= ( low+high) / 2;
if  (x<d[mid].key)  high=mid-1; /*判斷並同時修改指針*/
else  low =mid+1;
}
return mid+1; /*返回應插入的位置*/
}
main( )
{int i,j,k,m,first=1,final=1;
printf("input the number of the array.\n");
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",r[i].key);
printf("the souce array is :\n");
for (i=1;i<=n;i++)
printf("%5d",r[i].key);
d[1].key=r[1].key;
for (i=2 ; i<=n ; i++)
{ if  （r[i].key<d[1].key ）
if (first==1)  {d[n]=r[i]; first=n;}
else
{  m=search_bin(d, first , n , r[i].key);  /*找到要插入的位置*/
   for (k=first-1 ;k<=m-1;k++)
      d[k].key=d[k+1].key ; /*向前移動元素，空出位置*/
d[m]=r[i];
first--;
}
else
{m=search_bin(d , 1 , final , r[i].key);
for (k=m ; k<=final ; k++)
      d[k].key=d[k-1].key ; /*向後移動元素，空出位置*/
d[m]=r[i];
final=final+1;
}
while  (first!=final) /*輸出所排序的結果*/
  { if (first=n)  first=(first+1) %n;
/*因為最後所排序的結果在d[]陣列中，且d[]陣列是迴圈有序的*/
printf(“%5d”,d[first].key) ;  /*一個迴圈陣列*/
first++;
}
printf("%5d",r[final].key);
  }
【測試資料】可由讀者指定。
【實驗題】
對上述2路排序演算法進行修改，使每次從r陣列中取出一個待排序資料插入到d陣列的有序表中後，給出兩個指標first、final的變化情況。

第四節堆排序實驗

【問題描述】用堆排序法設計一個排序程式。
【演算法描述】
1. 將待排序的資料存入二叉樹陣列中；
2. 將二叉樹轉成最大堆；
3. 堆的最大值和陣列最後一個元素交換；
4. 其餘元素進行堆重建，並列印目前排序結果；
5. 重複3、4步，直到所有值均已排序完成；
6. 列印出陣列的最終排序結果。
例：Step1: 將欲排序的8個資料元素“70，90，20，80，10，40，60，30”放入陣列中；
70 90 20 80 10 40 60 30
其二叉樹的表示為：

Step2: 將此二叉樹建成最大堆（n=8，從第n/2=4個節點開始調整，順序是4，3，2，1）
(1)考慮n4

(2)考慮n3

(3)考慮n2

(4)考慮n1

(5)考慮n2

(6) 考慮n4

(7)建成的最大堆

其相對應的陣列結構排列：

90 80 60 70 10 40 20 30

Step3: 取出樹根結點的值，將剩下的值再排成堆。（取出的定義是將根的值與最後一個結點值交換）
將n1與n8交換後的結果：

將n1~n7按Step 2 的規則又構建成如下所示的堆：

Step4: 重複Step3的步驟，將n1和n7交換，再將n1~n6建成堆，結果如下圖所示：

Step5: 重複Step3的步驟，將n1和n6交換，再將n1~n5建成堆，結果如下圖所示：

Step6: 重複Step3的步驟，將n1和n5交換，再將n1~n4建成堆，結果如下圖所示：

Step7: 重複Step3的步驟，將n1和n4交換，再將n1~n3建成堆，結果如下圖所示：

Step8: 重複Step3的步驟，將n1和n3交換，再將n1~n2建成堆，結果如下圖所示：

Step9: 將n1和n2交換，最後再形成堆，結果如下圖所示：

其對應的陣列結構排列為：
10 20 30 40 60 70 80 90

從上面關於堆的建立以及堆的排序流程可看出：堆排序是不穩定的排序。每次結點在做交換時，需要一個額外的暫存空間，所以空間複雜度為O（1），時間複雜度為。
【C根源程式】
void createheap(int  *heap, int root, int index) /*建立堆*/
{int  i ,  j;
int temp;
int finish;
j=2*root;
temp=heap[root];
finish=0;
while (j<=index &&finish= =0)
{
if (j<index)
if (heap[j]<heap[j+1])
j++;
if (temp>=heap[j])
finish=1; /*堆已建立完成*/
else
{heap[j/2]=heap[j]; /*父結點=目前結點*/
j=j*2;
}
}
heap[j/2]=temp; /*父結點=root值*/
}
void heapsort(int *heap,int index) /*進行堆排序*/
{ int i , j , temp;
for (i=(index/2) ; i>=1 ; i--) /*將二叉樹轉成heap*/
createheap(heap,i,index);
for (i=index-1 ; i>=1 ; i--) /*開始堆排序*/
{ temp=heap[i+1]; /*heap的root值和最後一個值交換*/
  heap[i+1]=heap[1];
  heap[1]=temp;
  createheap(heap , 1 , i ); /*對其餘元素重建堆*/
  printf("sorting process: "); /*列印堆的處理過程*/
  for (j=1;j<=index;j++)
   printf("%5d",heap[j]);
  printf("\n");
}
}
void  main()
{ int  list[20];
int node;
int i , j, index;
printf("please input the number to sort:\n");
list[0]=0;
index=1;
scanf("%d",&node);
while (node!=0) /*輸入資料，當輸入的數為0時，退出*/
{ list[index]=node;
index=index+1;
scanf("%d",&node);
}
index--;
printf("the source elements: ");
for (i=1 ;i<=index ; i++)
printf("%5d",list[i]);
printf("\n\n");
heapsort(list,index); /*進行堆排序*/
printf("\nsorting result is : ");
for (j=1 ; j<=index ; j++) /*列印最後結果*/
printf("%5d",list[j]);
printf("\n");
}

【測試資料】
輸入： 10 –5 50 70 35 25 0
輸出： -5 10 25 35 50 70
【實驗題】
1. 根據上述描述的堆排序演算法，試進行修改和完善，使之能對一個給定待排序的序列，採用堆排序法作昇冪排列時的每一趟的結果。
2. 編制程式：（1）讓機器隨機產生2000個整數，放入一個陣列中；（2）對此2000個亂數序列分別用冒泡排序、快速排序、希爾排序和堆排序方法進行排序，並比較它們的運行時間。

第五節思考題
1．有一種簡單的排序演算法，叫做計數排序(count sorting)。這種排序演算法對一個待排序的表(用陣列表示)進行排序，並將排序結果存放到另一個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同。計數排序演算法針對表中的每個記錄，掃描待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小。假設針對某一個記錄，統計出的計數值為c,那麼，這個記錄在新的有序表中的合適的存放位置即為c。
（1）給出適用於計數排序的資料表定義；
（2）使用C語言編寫實現計數排序的演算法；
（3）對於有n個記錄的表，關鍵碼比較次數是多少？
（4）與簡單選擇排序相比較，這種方法是否更好？為什麼？
（摘自清華大學2000年碩士生入學考試，《資料結構與程式設計》試題）

Chapter Nine Implementations of Internal Sort Algorithms

Objectives
1. To better understand ideologies, techniques and stability of all kinds of sort algorithms.
2. To understand the implementation of quick sort, heap sort and merger sort.
3. To be able to write specific sort procedure, algorithms and integrity program when given a set of data, and to be able to debug the program.
4. To familiar with time complexity of each kind of sort.

收藏分享評分

回復引用

訂閱 TOP

返回列表