c語言數據結構排序算法的實現

這篇文章運用簡單易懂的例子給大家介紹c語言數據結構排序算法的實現，代碼非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

概述

排序有內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。

1.插入排序—直接插入排序(Straight Insertion Sort)

基本思想:

將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。

要點：設立哨兵，作為臨時存儲和判斷數組邊界之用。

如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。

算法的實現：

void print(int a[], int n ,int i){  
    cout<<i <<":";  
    for(int j= 0; j<8; j++){  
        cout<<a[j] <<" ";  
    }  
    cout<<endl;  
}  
  
  
void InsertSort(int a[], int n)  
{  
    for(int i= 1; i<n; i++){  
        if(a[i] < a[i-1]){               //若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入  
            int j= i-1;   
            int x = a[i];        //復制為哨兵，即存儲待排序元素  
            a[i] = a[i-1];           //先后移一個元素  
            while(x < a[j]){  //查找在有序表的插入位置  
                a[j+1] = a[j];  
                j--;         //元素后移  
            }  
            a[j+1] = x;      //插入到正確位置  
        }  
        print(a,n,i);           //打印每趟排序的結果  
    }  
      
}  
  
int main(){  
    int a[8] = {3,1,5,7,2,4,9,6};  
    InsertSort(a,8);  
    print(a,8,8);  
}

時間復雜度：O（n^2）.

其他的插入排序有二分插入排序，2-路插入排序。

2. 插入排序—希爾排序（Shell`s Sort）

希爾排序是1959 年由D.L.Shell 提出來的，相對直接排序有較大的改進。希爾排序又叫縮小增量排序

基本思想：

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

操作方法：

選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列個數k，對序列進行k 趟排序；每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

算法實現：

我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n為要排序數的個數

即：先將要排序的一組記錄按某個增量d（n/2,n為要排序數的個數）分成若干組子序列，每組中記錄的下標相差d.對每組中全部元素進行直接插入排序，然后再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序。繼續不斷縮小增量直至為1，最后使用直接插入排序完成排序。

void print(int a[], int n ,int i){ 
    cout<<i <<":"; 
    for(int j= 0; j<8; j++){ 
        cout<<a[j] <<" "; 
    } 
    cout<<endl; 
} 
/**
 * 直接插入排序的一般形式
 *
 * @param int dk 縮小增量，如果是直接插入排序，dk=1
 *
 */ 
   
void ShellInsertSort(int a[], int n, int dk) 
{ 
    for(int i= dk; i<n; ++i){ 
        if(a[i] < a[i-dk]){          //若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入 
            int j = i-dk;    
            int x = a[i];           //復制為哨兵，即存儲待排序元素 
            a[i] = a[i-dk];         //首先后移一個元素 
            while(x < a[j]){     //查找在有序表的插入位置 
                a[j+dk] = a[j]; 
                j -= dk;             //元素后移 
            } 
            a[j+dk] = x;            //插入到正確位置 
        } 
        print(a, n,i ); 
    } 
       
} 
   
/**
 * 先按增量d（n/2,n為要排序數的個數進行希爾排序
 *
 */ 
void shellSort(int a[], int n){ 
   
    int dk = n/2; 
    while( dk >= 1  ){ 
        ShellInsertSort(a, n, dk); 
        dk = dk/2; 
    } 
} 
int main(){ 
    int a[8] = {3,1,5,7,2,4,9,6}; 
    //ShellInsertSort(a,8,1); //直接插入排序 
    shellSort(a,8);           //希爾插入排序 
    print(a,8,8); 
}

希爾排序時效分析很難，關鍵碼的比較次數與記錄移動次數依賴于增量因子序列d的選取，特定情況下可以準確估算出關鍵碼的比較次數和記錄的移動次數。目前還沒有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數的，也有取質數的，但需要注意：增量因子中除1 外沒有公因子，且最后一個增量因子必須為1。希爾排序方法是一個不穩定的排序方法。

3. 選擇排序—簡單選擇排序（Simple Selection Sort）

基本思想：

在要排序的一組數中，選出最小（或者最大）的一個數與第1個位置的數交換；然后在剩下的數當中再找最小（或者最大）的與第2個位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最后一個數）比較為止。

操作方法：

第一趟，從n 個記錄中找出關鍵碼最小的記錄與第一個記錄交換；

第二趟，從第二個記錄開始的n-1 個記錄中再選出關鍵碼最小的記錄與第二個記錄交換；

以此類推.....

第i 趟，則從第i 個記錄開始的n-i+1 個記錄中選出關鍵碼最小的記錄與第i 個記錄交換，

直到整個序列按關鍵碼有序。

算法實現：

void print(int a[], int n ,int i){  
    cout<<"第"<<i+1 <<"趟 : ";  
    for(int j= 0; j<8; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
/** 
 * 數組的最小值 
 * 
 * @return int 數組的鍵值 
 */  
int SelectMinKey(int a[], int n, int i)  
{  
    int k = i;  
    for(int j=i+1 ;j< n; ++j) {  
        if(a[k] > a[j]) k = j;  
    }  
    return k;  
}  
  
/** 
 * 選擇排序 
 * 
 */  
void selectSort(int a[], int n){  
    int key, tmp;  
    for(int i = 0; i< n; ++i) {  
        key = SelectMinKey(a, n,i);           //選擇最小的元素  
        if(key != i){  
            tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素與第i位置元素互換  
        }  
        print(a,  n , i);  
    }  
}  
int main(){  
    int a[8] = {3,1,5,7,2,4,9,6};  
    cout<<"初始值：";  
    for(int j= 0; j<8; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl<<endl;  
    selectSort(a, 8);  
    print(a,8,8);  
}

簡單選擇排序的改進——二元選擇排序

簡單選擇排序，每趟循環只能確定一個元素排序后的定位。我們可以考慮改進為每趟循環確定兩個元素（當前趟最大和最小記錄）的位置,從而減少排序所需的循環次數。改進后對n個數據進行排序，最多只需進行[n/2]趟循環即可。具體實現如下：

void SelectSort(int r[],int n) {  
    int i ,j , min ,max, tmp;  
    for (i=1 ;i <= n/2;i++) {    
        // 做不超過n/2趟選擇排序   
        min = i; max = i ; //分別記錄最大和最小關鍵字記錄位置  
        for (j= i+1; j<= n-i; j++) {  
            if (r[j] > r[max]) {   
                max = j ; continue ;   
            }    
            if (r[j]< r[min]) {   
                min = j ;   
            }     
      }    
      //該交換操作還可分情況討論以提高效率  
      tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  
      tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;   
  
    }   
}

4. 選擇排序—堆排序（Heap Sort）

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。

基本思想：

堆的定義如下：具有n個元素的序列（k1,k2,...,kn),當且僅當滿足

時稱之為堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最小項（小頂堆）。
若以一維數組存儲一個堆，則堆對應一棵完全二叉樹，且所有非葉結點的值均不大于(或不小于)其子女的值，根結點（堆頂元素）的值是最小(或最大)的。如：

（a）大頂堆序列：（96, 83,27,38,11,09)

(b)  小頂堆序列：（12，36，24，85，47，30，53，91）

初始時把要排序的n個數的序列看作是一棵順序存儲的二叉樹（一維數組存儲二叉樹），調整它們的存儲序，使之成為一個堆，將堆頂元素輸出，得到n 個元素中最小(或最大)的元素，這時堆的根節點的數最小（或者最大）。然后對前面(n-1)個元素重新調整使之成為堆，輸出堆頂元素，得到n 個元素中次小(或次大)的元素。依此類推，直到只有兩個節點的堆，并對它們作交換，最后得到有n個節點的有序序列。稱這個過程為堆排序。

因此，實現堆排序需解決兩個問題：

1. 如何將n 個待排序的數建成堆；

2. 2. 輸出堆頂元素后，怎樣調整剩余n-1 個元素，使其成為一個新堆。

首先討論第二個問題：輸出堆頂元素后，對剩余n-1元素重新建成堆的調整過程。
調整小頂堆的方法：

1）設有m 個元素的堆，輸出堆頂元素后，剩下m-1 個元素。將堆底元素送入堆頂（（最后一個元素與堆頂進行交換），堆被破壞，其原因僅是根結點不滿足堆的性質。

2）將根結點與左、右子樹中較小元素的進行交換。

3）若與左子樹交換：如果左子樹堆被破壞，即左子樹的根結點不滿足堆的性質，則重復方法 （2）.

4）若與右子樹交換，如果右子樹堆被破壞，即右子樹的根結點不滿足堆的性質。則重復方法 （2）.

5）繼續對不滿足堆性質的子樹進行上述交換操作，直到葉子結點，堆被建成。

稱這個自根結點到葉子結點的調整過程為篩選。

再討論對n 個元素初始建堆的過程。

建堆方法：對初始序列建堆的過程，就是一個反復進行篩選的過程。

1）n 個結點的完全二叉樹，則最后一個結點是第個結點的子樹。

2）篩選從第個結點為根的子樹開始，該子樹成為堆。

3）之后向前依次對各結點為根的子樹進行篩選，使之成為堆，直到根結點。

算法的實現：

從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數組成。一是建堆的滲透函數，二是反復調用滲透函數實現排序的函數。

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
  
  
  
/** 
 * 已知H[s…m]除了H[s] 外均滿足堆的定義 
 * 調整H[s],使其成為大頂堆.即將對第s個結點為根的子樹篩選,  
 * 
 * @param H是待調整的堆數組 
 * @param s是待調整的數組元素的位置 
 * @param length是數組的長度 
 * 
 */  
void HeapAdjust(int H[],int s, int length)  
{  
    int tmp  = H[s];  
    int child = 2*s+1; //左孩子結點的位置。(i+1 為當前調整結點的右孩子結點的位置)  
    while (child < length) {  
        if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比當前待調整結點大的孩子結點)  
            ++child ;  
        }  
        if(H[s]<H[child]) {  // 如果較大的子結點大于父結點  
            H[s] = H[child]; // 那么把較大的子結點往上移動，替換它的父結點  
            s = child;       // 重新設置s ,即待調整的下一個結點的位置  
            child = 2*s+1;  
        }  else {            // 如果當前待調整結點大于它的左右孩子，則不需要調整，直接退出  
             break;  
        }  
        H[s] = tmp;         // 當前待調整的結點放到比其大的孩子結點位置上  
    }  
    print(H,length);  
}  
  
  
/** 
 * 初始堆進行調整 
 * 將H[0..length-1]建成堆 
 * 調整完之后第一個元素是序列的最小的元素 
 */  
void BuildingHeap(int H[], int length)  
{   
    //最后一個有孩子的節點的位置 i=  (length -1) / 2  
    for (int i = (length -1) / 2 ; i >= 0; --i)  
        HeapAdjust(H,i,length);  
}  
/** 
 * 堆排序算法 
 */  
void HeapSort(int H[],int length)  
{  
    //初始堆  
    BuildingHeap(H, length);  
    //從最后一個元素開始對序列進行調整  
    for (int i = length - 1; i > 0; --i)  
    {  
        //交換堆頂元素H[0]和堆中最后一個元素  
        int temp = H[i]; H[i] = H[0]; H[0] = temp;  
        //每次交換堆頂元素和堆中最后一個元素之后，都要對堆進行調整  
        HeapAdjust(H,0,i);  
  }  
}   
  
int main(){  
    int H[10] = {3,1,5,7,2,4,9,6,10,8};  
    cout<<"初始值：";  
    print(H,10);  
    HeapSort(H,10);  
    //selectSort(a, 8);  
    cout<<"結果：";  
    print(H,10);  
  
}

分析:

設樹深度為k，從根到葉的篩選，元素比較次數至多2(k-1)次，交換記錄至多k 次。所以，在建好堆后，排序過程中的篩選次數不超過下式：

而建堆時的比較次數不超過4n 次，因此堆排序最壞情況下，時間復雜度也為：O(nlogn )。

5. 交換排序—冒泡排序（Bubble Sort）

基本思想：

在要排序的一組數中，對當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換。

算法的實現：

void bubbleSort(int a[], int n){  
    for(int i =0 ; i< n-1; ++i) {  
        for(int j = 0; j < n-i-1; ++j) {  
            if(a[j] > a[j+1])  
            {  
                int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;  
            }  
        }  
    }  
}

冒泡排序算法的改進

對冒泡排序常見的改進方法是加入一標志性變量exchange，用于標志某一趟排序過程中是否有數據交換，如果進行某一趟排序時并沒有進行數據交換，則說明數據已經按要求排列好，可立即結束排序，避免不必要的比較過程。

6. 交換排序—快速排序（Quick Sort）

基本思想：

1）選擇一個基準元素,通常選擇第一個元素或者最后一個元素,

2）通過一趟排序講待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準元素值小。另一部分記錄的 元素值比基準值大。

3）此時基準元素在其排好序后的正確位置

4）然后分別對這兩部分記錄用同樣的方法繼續進行排序，直到整個序列有序。

算法的實現：

遞歸實現：

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
  
void swap(int *a, int *b)  
{  
    int tmp = *a;  
    *a = *b;  
    *b = tmp;  
}  
  
int partition(int a[], int low, int high)  
{  
    int privotKey = a[low];                             //基準元素  
    while(low < high){                                   //從表的兩端交替地向中間掃描  
        while(low < high  && a[high] >= privotKey) --high;  //從high 所指位置向前搜索，至多到low+1 位置。將比基準元素小的交換到低端  
        swap(&a[low], &a[high]);  
        while(low < high  && a[low] <= privotKey ) ++low;  
        swap(&a[low], &a[high]);  
    }  
    print(a,10);  
    return low;  
}  
  
  
void quickSort(int a[], int low, int high){  
    if(low < high){  
        int privotLoc = partition(a,  low,  high);  //將表一分為二  
        quickSort(a,  low,  privotLoc -1);          //遞歸對低子表遞歸排序  
        quickSort(a,   privotLoc + 1, high);        //遞歸對高子表遞歸排序  
    }  
}  
  
int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    cout<<"初始值：";  
    print(a,10);  
    quickSort(a,0,9);  
    cout<<"結果：";  
    print(a,10);  
  
}

分析：

快速排序是通常被認為在同數量級（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取基準記錄，即將排序區間的兩個端點與中點三個記錄關鍵碼居中的調整為支點記錄。快速排序是一個不穩定的排序方法。

7. 歸并排序（Merge Sort）

基本思想：

歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。

合并方法：

設r[i…n]由兩個有序子表r[i…m]和r[m+1…n]組成，兩個子表長度分別為n-i +1、n-m。

j=m+1；k=i；i=i; //置兩個子表的起始下標及輔助數組的起始下標若i>m 或j>n，轉⑷ //其中一個子表已合并完，比較選取結束//選取r[i]和r[j]較小的存入輔助數組rf
如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 轉⑵
否則，rf[k]=r[j]； j++； k++； 轉⑵//將尚未處理完的子表中元素存入rf
如果i<=m，將r[i…m]存入rf[k…n] //前一子表非空
如果j<=n ,  將r[j…n] 存入rf[k…n] //后一子表非空合并結束。

//將r[i…m]和r[m +1 …n]歸并到輔助數組rf[i…n]  
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
{  
    int j,k;  
    for(j=m+1,k=i; i<=m && j <=n ; ++k){  
        if(r[j] < r[i]) rf[k] = r[j++];  
        else rf[k] = r[i++];  
    }  
    while(i <= m)  rf[k++] = r[i++];  
    while(j <= n)  rf[k++] = r[j++];  
}

歸并的迭代算法

1 個元素的表總是有序的。所以對n 個元素的待排序列，每個元素可看成1 個有序子表。對子表兩兩合并生成n/2個子表，所得子表除最后一個子表長度可能為1 外，其余子表長度均為2。再進行兩兩合并，直到生成n 個元素按關鍵碼有序的表。

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
  
//將r[i…m]和r[m +1 …n]歸并到輔助數組rf[i…n]  
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
{  
    int j,k;  
    for(j=m+1,k=i; i<=m && j <=n ; ++k){  
        if(r[j] < r[i]) rf[k] = r[j++];  
        else rf[k] = r[i++];  
    }  
    while(i <= m)  rf[k++] = r[i++];  
    while(j <= n)  rf[k++] = r[j++];  
    print(rf,n+1);  
}  
  
void MergeSort(ElemType *r, ElemType *rf, int lenght)  
{   
    int len = 1;  
    ElemType *q = r ;  
    ElemType *tmp ;  
    while(len < lenght) {  
        int s = len;  
        len = 2 * s ;  
        int i = 0;  
        while(i+ len <lenght){  
            Merge(q, rf,  i, i+ s-1, i+ len-1 ); //對等長的兩個子表合并  
            i = i+ len;  
        }  
        if(i + s < lenght){  
            Merge(q, rf,  i, i+ s -1, lenght -1); //對不等長的兩個子表合并  
        }  
        tmp = q; q = rf; rf = tmp; //交換q,rf，以保證下一趟歸并時，仍從q 歸并到rf  
    }  
}  
  
  
int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    int b[10];  
    MergeSort(a, b, 10);  
    print(b,10);  
    cout<<"結果：";  
    print(a,10);  
  
}

兩路歸并的遞歸算法

void MSort(ElemType *r, ElemType *rf,int s, int t)  
{   
    ElemType *rf2;  
    if(s==t) r[s] = rf[s];  
    else  
    {   
        int m=(s+t)/2;          /*平分*p 表*/  
        MSort(r, rf2, s, m);        /*遞歸地將p[s…m]歸并為有序的p2[s…m]*/  
        MSort(r, rf2, m+1, t);      /*遞歸地將p[m+1…t]歸并為有序的p2[m+1…t]*/  
        Merge(rf2, rf, s, m+1,t);   /*將p2[s…m]和p2[m+1…t]歸并到p1[s…t]*/  
    }  
}  
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
{   /*對順序表*p 作歸并排序*/  
    MSort(r, rf,0, n-1);  
}

關于c語言數據結構排序算法的實現就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。