首頁 > 軟體

C語言實現各種排序演演算法範例程式碼(選擇,冒泡,插入,歸併,希爾,快排,堆排序,計數)

2021-10-14 16:03:46

前言

平時用慣了高階語言高階工具高階演演算法,難免對一些基礎演演算法感到生疏。但最基礎的排序演演算法中實則蘊含著相當豐富的優化思維,熟練運用可起到舉一反三之功效。

選擇排序

選擇排序幾乎是最無腦的一種排序演演算法,通過遍歷一次陣列,選出其中最大(小)的值放在新陣列的第一位;再從陣列中剩下的數裡選出最大(小)的,放到第二位,依次類推。

演演算法步驟

設陣列有n個元素,{ a 0 , a 1 , … , a n }

  1. 從陣列第i ii位開始便利,找到最大值,將之與陣列第i ii位交換位置。
  2. i ii從0迴圈到n。

由於每次遍歷需要計算O ( n ) 次,且需要便利n 次,故時間複雜度為O ( n 2 ) );由於只在交換的過程中需要額外的資料,所以空間複雜度為O ( n ) 。

C語言實現

//sort.c
void SelectionSort(double *p, int n);
int main(){
    double test[5] = {3,2,5,7,9};
    SelectionSort(test,5);
    for (int i = 0; i < 5; i++)
        printf("%fn", test[i]);
    return 0;
}

//交換陣列中i,j處的值
void mySwap(double *arr, int i, int j){
    double temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

//選擇排序
void SelectionSort(double *arr, int n){
    int pMax;
    double temp;
    for (int i = 0; i < n-1; i++){
        pMax = i;
        for (int j = i+1; j < n; j++)
            if (arr[j]>arr[pMax])
                pMax = j;
        mySwap(arr,pMax,i);
    }
}

驗證

>gcc sort.c
>a
9.000000
7.000000
5.000000
3.000000
2.000000

氣泡排序

氣泡排序也是一種無腦的排序方法,通過重複走訪要排序的陣列,比較相鄰的兩個元素,如果順序不符合要求則交換兩個數的位置,直到不需要交換為止。

演演算法步驟

設陣列有n個元素,{ a 0 , a 1 , … , a n }

  1. 比較相鄰的元素a i , a i + 1 ,如果a i > a i + 1  ,則交換二者。
  2. 由於每遍歷一次都可以將最大的元素排到最後面,所以下一次可以少便利一個元素。
  3. 重複遍歷陣列n次

由於每次遍歷需要計算O ( n ) 次,且需要遍歷n次,故時間複雜度為O ( n 2 ) ,空間複雜度為O ( n ) 。

C語言實現

//氣泡排序
void BubbleSort(double *arr, int n)
{
    n = n-1;
    double temp;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n-i; j++)
        if (arr[j]>arr[j+1])
            mySwap(arr,i,j);        /*前文定義的函數*/
}

插入排序

插入排序是演演算法導論中的第一個演演算法,說明已經不那麼無腦了。其基本思路是將陣列劃分位前後兩個部分,前面是有序陣列,後面是無序陣列。逐個掃描無序陣列,將每次掃描的數插入到有序陣列中。這樣有序陣列會越來越長,無序陣列越來越短,直到整個陣列都是有序的。

演演算法步驟

設陣列有n個元素,{ a 0 , a 1 , … , a n }

  1. 假設陣列中的第0個數已經有序
  2. 取出無序陣列的第0個元素,將其與有序陣列比較,插入到有序陣列中。

可見,插入排序的每次插入都有O ( n )的複雜度,而需要遍歷n nn次,所以時間複雜度仍為O ( n 2 ) 。

C語言實現

//插入排序
void InsertionSort(double *arr, int n){
    double temp;
    int j;
    for (int i = 1; i < n; i++){
        j = i-1;
        temp  = arr[i];
        while (temp<arr[j] && j>=0){
            arr[j+1] = arr[j];      //第j個元素後移
            j--;
        }
        arr[j+1] = temp;
    }
}

歸併排序

歸併排序是演演算法導論中介紹分治概念時提到的一種排序演演算法,其基本思路為將陣列拆分成子陣列,然後令子陣列有序,再令陣列之間有序,則可以使整個陣列有序。

演演算法步驟

設陣列有n個元素,{ a 0 , a 1 , … , a n }

  1. 如果陣列元素大於2,則將陣列分成左陣列和右陣列,如果陣列等於2,則將陣列轉成有序陣列
  2. 對左陣列和右陣列執行1操作。
  3. 合併左陣列和右陣列。

可以發現,對於長度為n nn的陣列,需要log 2 n次的拆分,每個拆分層級都有O ( n ) 的時間複雜度和O ( n ) 的空間複雜度,所以其時間複雜度和空間複雜度分別為O ( n log 2 n ) 和O(n)

C語言實現

首先考慮兩個有序陣列的合併問題

//sort.c

void myMerge(double *arr, int nL, int nR);
int main(){
    int n = 6;
    double arr[6] = {2,4,5,1,3,7};
    Merge(arr,3,3);

    for (int i = 0; i < n; i++)
        printf("%fn", arr[i]);
    return 0;
}

//兩個有序陣列的混合,arr為輸入陣列
//nL、nR分別為左陣列和右陣列的長度
void Merge(double *arr, int nL, int nR){
    nL = nL-1;                    //左側最後一個元素的索引
    int sInsert = 0;               //左側待插入起始值
    double temp;
    for (int i = 1; i <= nR; i++)
    {
        while (arr[nL+i]>arr[sInsert])
            sInsert++;
        if (sInsert<nL+i){
            temp = arr[nL+i];
            for (int j = nL+i; j > sInsert; j--)
                arr[j]=arr[j-1];
            arr[sInsert] = temp; 
        }
        else
            break;    //如果sInsert==nL+i,說明右側序列無需插入
    }
}

驗證

> gcc sort.c
> a
1.000000
2.000000
3.000000
4.000000
5.000000
7.000000

然後考慮歸併排序的遞迴過程

void MergeSort(double *arr, int n);
void myMerge(double *arr, int nL, int nR);

int main(){
    int n = 6;
    double arr[6] = {5,2,4,7,1,3};
    MergeSort(arr,n);

    for (int i = 0; i < n; i++)
        printf("%fn", arr[i]);
    return 0;
}

void MergeSort(double *arr, int n){
    if (n>2)
    {
        int nL = n/2;
        int nR = n-nL;
        MergeSort(arr,nL);
        MergeSort(arr+nL,nR);
        Merge(arr,nL,nR);
    }
    else if(n==2)
        Merge(arr,1,1);
    //當n==1時說明陣列中只剩下一個元素,所以什麼也不用做
}

驗證

> gcc sort.c
> a
1.000000
2.000000
3.000000
4.000000
5.000000
7.000000

至此,排序演演算法終於有一點演演算法的味道了。

希爾排序

據說是第一個突破O ( n 2 ) 的排序演演算法,又稱為縮小增量排序,本質上也是一種分治方案。

在歸併排序中,先將長度為n的陣列劃分為長度為nL和nR的兩個陣列,然後繼續劃分,直到每個陣列的長度不大於2,再對每個不大於2的陣列進行排序。這樣,每個子陣列內部有序而整體無序,然後將有序的陣列進行回溯重組,直到重新變成長度為n的陣列為止。

希爾排序的劃分策略則不然,這裡在將陣列劃分為nL和nR之後,對nR和nR進行按位元排序,使得nL和nR內部無序,但整體有序。然後再將陣列進行細分,當陣列長度變成1的時候,內部也就談不上無序了,而所有長度為1的陣列整體有序,也就是說有這些子陣列所組成的陣列是有序的。

演演算法步驟

設陣列有n nn個元素,{ a 0 , a 1 , … , a n }

  1. 如果陣列元素大於2,則將陣列分成左陣列和右陣列,並對左陣列和右陣列的元素進行一對一地排序。
  2. 對每一個陣列進行細分,然後將每個子陣列進行一對一地排序。

C語言實現

//希爾排序
void ShellSort(double *arr, int n){
    double temp;
    int j;
    for (int nSub = n/2; nSub >0; nSub/=2)      //nSub為子陣列長度
        for (int i = nSub; i < n; i++)
        {
            temp = arr[i];
            for (j = i-nSub; j >= 0&& temp<arr[j]; j -= nSub)
                arr[j+nSub] = arr[j];
            arr[j+nSub] = temp;
        }
}

快速排序

快速排序的分治策略與希爾排序類似,其核心思想都是從組內無序而組間有序出發,當子陣列長度縮減至1的時候,則整個陣列便是有序的。

演演算法步驟

設陣列有n nn個元素,{ a 0 , a 1 , … , a n }

  1. 在陣列中隨機選出一個基準a m i d
  2. 通過a m i d將陣列分成兩部分,其中左邊小於a m i d ,右邊大於a m i d
  3. 對左右子陣列重複1、2操作,直到子陣列長度為1。

由於快速排序的過程中有一個隨機選擇,所以其時間複雜度可能會受到這個隨機選擇的影響,如果運氣不好的話,快速排序可能會變成氣泡排序。當然,一般來說運氣不會那麼差,快速排序的平均時間複雜度為O ( n log 2 n ) 。

C語言實現

//快速排序
void QuickSort(double *arr, int n){
    double pivot = arr[0];      //選取第0個點為基準
    int i = 1;
    int j = n-1;
    while (i<j){
        if (arr[i]<pivot)
            i++;
        else{
            mySwap(arr,i,j);
            j--;
        }
    }
    if (arr[i]>pivot)
        i--;
    mySwap(arr,i,0);
    if (i>1)
        QuickSort(arr,i);    //對i前的陣列進行快排
    
    i++;
    if (i<n-1)
        QuickSort(arr+i,n-i);//對i+1後的陣列進行快排
}

堆排序

堆是演演算法導論中介紹的第一種資料結構,本質是一種二元樹,最大堆要求子節點的值不大於父節點,最小堆反之。由於堆是一種帶有節點的資料結構,所以結構表示更加直觀。好在二元樹父子節點的序號之間存在簡單的遞推關係,所以在C語言中可以用陣列表示堆,

根據上圖可知,若父節點的序號為n nn,則左子節點序號為2 n + 1 ,右子節點序號為2 n + 2 。

可以將上圖理解為一個排好序的最小堆,如果1位變成15,那麼此時這個節點將違反最小堆的原則,經過比對,應該調換15和3的位置。調換之後,15仍然比7和8大,則再調換15和7的位置,則這個最小堆變為

 

從而繼續滿足最小堆的性質,最大堆亦然,其C語言實現為

//如果堆中節點號為m的點不滿足要求,則調整這個點
//此為最大堆
void adjustHeap(double *arr, int m, int n){
    int left = m*2+1;       //左節點

    while (left<n)
    {
        if (left+1<n)       //判斷右節點
            if (arr[left]<arr[left+1])
                left++;     //當右節點大於左節點時,left表示右節點
        
        if (arr[m]>arr[left])
            break;          //如果父節點大於子節點,則說明覆合最大堆
        else{
            mySwap(arr,m,left);
            m = left;
            left = m*2+1;
        }
    }
}

堆的調整過程就是父節點與其左右兩個子節點比較的過程,也就是說通過這種方式得到的堆能夠滿足父子節點的大小關係,但兩個孫節點之間並不會被排序。但是,如果一個陣列已經滿足最大堆要求,那麼只需讓所有的節點都在根節點處重新參與排序,那麼最終得到的最大堆一定滿足任意節點間的有序關係。

//堆排序
void HeapSort(double *arr, int n){
    for (int i = n/2; i >= 0; i--)
        adjustHeap(arr,i,n);        //初始化堆
    for (int i = n-1; i > 0 ; i--){
        mySwap(arr,0,i);            //將待排序元素放到最頂端
        adjustHeap(arr,0,i);        //調整最頂端的值 
    }   
}

計數排序

此前所有的排序演演算法均沒有考慮到陣列的內在分佈,如果我們輸入的資料為某個區間內的整數,那麼我們只需建立這個區間內的整數索引,然後將每個數歸類到這個索引之中即可。

這便是桶排序的思路,所謂桶排序即通過將已知資料劃分為有序的幾個部分,放入不同的桶中,這個分部過程即桶排序。除了計數排序,基數排序是一種更廣泛的桶排序形式,其劃分方式可以為資料的位數,把這個桶定義為資料最高位的值。

例如,我們有一組均勻分佈在[ 0 , 100 ] 之內的資料,所謂基數排序,即先劃分出十個不同的桶[ 0 , 10 ) , [ 10 , 20 ) , … , [ 90 , 100 ) ,然後再對每個桶進行單獨的排序。這樣劃分下去,那麼基數排序的複雜度則為O ( 10 ∗ n ) 。

詞典中的排序方式也可以理解為一種基數排序,即首先看第一個字母的順序,然後第二個,依次類推。由於桶排序對資料做了假設,所以其最優時間複雜度可以達到O ( n + k ),k為桶的數目。

例如,我們有一個由一百個由1和2組成的陣列,那麼我們只需建立一個索引1 : n 1 , 2 : n 2 ,然後統計1和2分別出現的個數即可,其時間複雜度也將變成O ( n ) 。

在這裡只做出最簡單的計數排序。

/計數排序,輸入陣列為整數
void CountingSort(int *arr,int n){
    int aMax = arr[0];
    int aMin = arr[0];
    for (int i = 0; i < n; i++) //查詢最大值和最小值
        if (arr[i]>aMax)
            aMax = arr[i];
        else if (arr[i]<aMin)
            aMin = arr[i];
    
    int m = aMax-aMin+1;         //索引長度
    int *arrSort = (int*)malloc(sizeof(int)*m);
    for (int i = 0; i < m; i++)
        arrSort[i]=0;           //初始化索引
    
    for (int i = 0; i < n; i++) //排序
        arrSort[arr[i]-aMin] += 1;
    
    n = 0;
    for (int i = 0; i < m; i++)
    {
        aMax = i+aMin;          //此值為真實資料
        for (int j = n; j < n+arrSort[i]; j++)
            arrSort[j] = i+aMin;
        n += arrSort[i];
    }
}

總結

到此這篇關於C語言實現各種排序演演算法(選擇,冒泡,插入,歸併,希爾,快排,堆排序,計數)的文章就介紹到這了,更多相關C語言實現各種排序演演算法內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com