C語言實(shí)現(xiàn)各種排序算法實(shí)例代碼(選擇,冒泡,插入,歸并,希爾,快排,堆排序,計(jì)數(shù))

更新時(shí)間：2021年10月14日 11:58:54 作者：微小冷

排序算法是算法之中相對(duì)基礎(chǔ)的,也是各門語言的必學(xué)的算法,這篇文章主要介紹了C語言實(shí)現(xiàn)各種排序算法(選擇,冒泡,插入,歸并,希爾,快排,堆排序,計(jì)數(shù))的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下

前言

平時(shí)用慣了高級(jí)語言高級(jí)工具高級(jí)算法，難免對(duì)一些基礎(chǔ)算法感到生疏。但最基礎(chǔ)的排序算法中實(shí)則蘊(yùn)含著相當(dāng)豐富的優(yōu)化思維，熟練運(yùn)用可起到舉一反三之功效。

選擇排序

選擇排序幾乎是最無腦的一種排序算法，通過遍歷一次數(shù)組，選出其中最大（?。┑闹捣旁谛聰?shù)組的第一位；再?gòu)臄?shù)組中剩下的數(shù)里選出最大（小）的，放到第二位，依次類推。

算法步驟

設(shè)數(shù)組有n個(gè)元素，{ a₀, a ₁, … , a_n}

從數(shù)組第i ii位開始便利，找到最大值，將之與數(shù)組第i ii位交換位置。
i ii從0循環(huán)到n。

由于每次遍歷需要計(jì)算O ( n ) 次，且需要便利n 次，故時(shí)間復(fù)雜度為O ( n ² ) )；由于只在交換的過程中需要額外的數(shù)據(jù)，所以空間復(fù)雜度為O ( n ) 。

C語言實(shí)現(xiàn)

//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("%f\n", test[i]);
    return 0;
}

//交換數(shù)組中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);
    }
}

驗(yàn)證

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

冒泡排序

冒泡排序也是一種無腦的排序方法，通過重復(fù)走訪要排序的數(shù)組，比較相鄰的兩個(gè)元素，如果順序不符合要求則交換兩個(gè)數(shù)的位置，直到不需要交換為止。

算法步驟

設(shè)數(shù)組有n個(gè)元素，{ a ₀ , a ₁ , … , a _n}

比較相鄰的元素a _i, a_i+ 1 ,如果a _i> a _i+ 1 ，則交換二者。
由于每遍歷一次都可以將最大的元素排到最后面，所以下一次可以少便利一個(gè)元素。
重復(fù)遍歷數(shù)組n次

由于每次遍歷需要計(jì)算O ( n ) 次，且需要遍歷n次，故時(shí)間復(fù)雜度為O ( n² ) ，空間復(fù)雜度為O ( n ) 。

C語言實(shí)現(xiàn)

//冒泡排序
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);        /*前文定義的函數(shù)*/
}

插入排序

插入排序是算法導(dǎo)論中的第一個(gè)算法，說明已經(jīng)不那么無腦了。其基本思路是將數(shù)組劃分位前后兩個(gè)部分，前面是有序數(shù)組，后面是無序數(shù)組。逐個(gè)掃描無序數(shù)組，將每次掃描的數(shù)插入到有序數(shù)組中。這樣有序數(shù)組會(huì)越來越長(zhǎng)，無序數(shù)組越來越短，直到整個(gè)數(shù)組都是有序的。

算法步驟

設(shè)數(shù)組有n個(gè)元素，{ a ₀ , a ₁ , … , a _n }

假設(shè)數(shù)組中的第0個(gè)數(shù)已經(jīng)有序
取出無序數(shù)組的第0個(gè)元素，將其與有序數(shù)組比較，插入到有序數(shù)組中。

可見，插入排序的每次插入都有O ( n )的復(fù)雜度，而需要遍歷n nn次，所以時(shí)間復(fù)雜度仍為O ( n ²) 。

C語言實(shí)現(xiàn)

//插入排序
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個(gè)元素后移
            j--;
        }
        arr[j+1] = temp;
    }
}

歸并排序

歸并排序是算法導(dǎo)論中介紹分治概念時(shí)提到的一種排序算法，其基本思路為將數(shù)組拆分成子數(shù)組，然后令子數(shù)組有序，再令數(shù)組之間有序，則可以使整個(gè)數(shù)組有序。

算法步驟

設(shè)數(shù)組有n個(gè)元素，{ a ₀ , a₁ , … , a _n}

如果數(shù)組元素大于2，則將數(shù)組分成左數(shù)組和右數(shù)組，如果數(shù)組等于2，則將數(shù)組轉(zhuǎn)成有序數(shù)組
對(duì)左數(shù)組和右數(shù)組執(zhí)行1操作。
合并左數(shù)組和右數(shù)組。

可以發(fā)現(xiàn)，對(duì)于長(zhǎng)度為n nn的數(shù)組，需要log ₂n次的拆分，每個(gè)拆分層級(jí)都有O ( n ) 的時(shí)間復(fù)雜度和O ( n ) 的空間復(fù)雜度，所以其時(shí)間復(fù)雜度和空間復(fù)雜度分別為O ( n log ₂n ) 和O(n)

C語言實(shí)現(xiàn)

首先考慮兩個(gè)有序數(shù)組的合并問題

//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("%f\n", arr[i]);
    return 0;
}

//兩個(gè)有序數(shù)組的混合,arr為輸入數(shù)組
//nL、nR分別為左數(shù)組和右數(shù)組的長(zhǎng)度
void Merge(double *arr, int nL, int nR){
    nL = nL-1;                    //左側(cè)最后一個(gè)元素的索引
    int sInsert = 0;               //左側(cè)待插入起始值
    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，說明右側(cè)序列無需插入
    }
}

驗(yàn)證

> 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("%f\n", 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);
    //當(dāng)n==1時(shí)說明數(shù)組中只剩下一個(gè)元素，所以什么也不用做
}

驗(yàn)證

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

至此，排序算法終于有一點(diǎn)算法的味道了。

希爾排序

據(jù)說是第一個(gè)突破O ( n ²) 的排序算法，又稱為縮小增量排序，本質(zhì)上也是一種分治方案。

在歸并排序中，先將長(zhǎng)度為n的數(shù)組劃分為長(zhǎng)度為nL和nR的兩個(gè)數(shù)組，然后繼續(xù)劃分，直到每個(gè)數(shù)組的長(zhǎng)度不大于2，再對(duì)每個(gè)不大于2的數(shù)組進(jìn)行排序。這樣，每個(gè)子數(shù)組內(nèi)部有序而整體無序，然后將有序的數(shù)組進(jìn)行回溯重組，直到重新變成長(zhǎng)度為n的數(shù)組為止。

希爾排序的劃分策略則不然，這里在將數(shù)組劃分為nL和nR之后，對(duì)nR和nR進(jìn)行按位排序，使得nL和nR內(nèi)部無序，但整體有序。然后再將數(shù)組進(jìn)行細(xì)分，當(dāng)數(shù)組長(zhǎng)度變成1的時(shí)候，內(nèi)部也就談不上無序了，而所有長(zhǎng)度為1的數(shù)組整體有序，也就是說有這些子數(shù)組所組成的數(shù)組是有序的。

算法步驟

設(shè)數(shù)組有n nn個(gè)元素，{ a ₀ , a ₁ , … , a _n }

如果數(shù)組元素大于2，則將數(shù)組分成左數(shù)組和右數(shù)組，并對(duì)左數(shù)組和右數(shù)組的元素進(jìn)行一對(duì)一地排序。
對(duì)每一個(gè)數(shù)組進(jìn)行細(xì)分，然后將每個(gè)子數(shù)組進(jìn)行一對(duì)一地排序。

C語言實(shí)現(xiàn)

//希爾排序
void ShellSort(double *arr, int n){
    double temp;
    int j;
    for (int nSub = n/2; nSub >0; nSub/=2)      //nSub為子數(shù)組長(zhǎng)度
        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;
        }
}

快速排序

快速排序的分治策略與希爾排序類似，其核心思想都是從組內(nèi)無序而組間有序出發(fā)，當(dāng)子數(shù)組長(zhǎng)度縮減至1的時(shí)候，則整個(gè)數(shù)組便是有序的。

算法步驟

設(shè)數(shù)組有n nn個(gè)元素，{ a ₀ , a₁, … , a_n }

在數(shù)組中隨機(jī)選出一個(gè)基準(zhǔn)a_{m i d}
通過a _{m i d}將數(shù)組分成兩部分，其中左邊小于a _{m i d}，右邊大于a _{m i d}。
對(duì)左右子數(shù)組重復(fù)1、2操作，直到子數(shù)組長(zhǎng)度為1。

由于快速排序的過程中有一個(gè)隨機(jī)選擇，所以其時(shí)間復(fù)雜度可能會(huì)受到這個(gè)隨機(jī)選擇的影響，如果運(yùn)氣不好的話，快速排序可能會(huì)變成冒泡排序。當(dāng)然，一般來說運(yùn)氣不會(huì)那么差，快速排序的平均時(shí)間復(fù)雜度為O ( n log₂ n ) 。

C語言實(shí)現(xiàn)

//快速排序
void QuickSort(double *arr, int n){
    double pivot = arr[0];      //選取第0個(gè)點(diǎn)為基準(zhǔn)
    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);    //對(duì)i前的數(shù)組進(jìn)行快排
    
    i++;
    if (i<n-1)
        QuickSort(arr+i,n-i);//對(duì)i+1后的數(shù)組進(jìn)行快排
}

堆排序

堆是算法導(dǎo)論中介紹的第一種數(shù)據(jù)結(jié)構(gòu)，本質(zhì)是一種二叉樹，最大堆要求子節(jié)點(diǎn)的值不大于父節(jié)點(diǎn)，最小堆反之。由于堆是一種帶有節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，所以結(jié)構(gòu)表示更加直觀。好在二叉樹父子節(jié)點(diǎn)的序號(hào)之間存在簡(jiǎn)單的遞推關(guān)系，所以在C語言中可以用數(shù)組表示堆，

根據(jù)上圖可知，若父節(jié)點(diǎn)的序號(hào)為n nn，則左子節(jié)點(diǎn)序號(hào)為2 n + 1 ,右子節(jié)點(diǎn)序號(hào)為2 n + 2 。

可以將上圖理解為一個(gè)排好序的最小堆，如果1位變成15，那么此時(shí)這個(gè)節(jié)點(diǎn)將違反最小堆的原則，經(jīng)過比對(duì)，應(yīng)該調(diào)換15和3的位置。調(diào)換之后，15仍然比7和8大，則再調(diào)換15和7的位置，則這個(gè)最小堆變?yōu)?/p>

從而繼續(xù)滿足最小堆的性質(zhì)，最大堆亦然，其C語言實(shí)現(xiàn)為

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

    while (left<n)
    {
        if (left+1<n)       //判斷右節(jié)點(diǎn)
            if (arr[left]<arr[left+1])
                left++;     //當(dāng)右節(jié)點(diǎn)大于左節(jié)點(diǎn)時(shí)，left表示右節(jié)點(diǎn)
        
        if (arr[m]>arr[left])
            break;          //如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)，則說明復(fù)合最大堆
        else{
            mySwap(arr,m,left);
            m = left;
            left = m*2+1;
        }
    }
}

堆的調(diào)整過程就是父節(jié)點(diǎn)與其左右兩個(gè)子節(jié)點(diǎn)比較的過程，也就是說通過這種方式得到的堆能夠滿足父子節(jié)點(diǎn)的大小關(guān)系，但兩個(gè)孫節(jié)點(diǎn)之間并不會(huì)被排序。但是，如果一個(gè)數(shù)組已經(jīng)滿足最大堆要求，那么只需讓所有的節(jié)點(diǎn)都在根節(jié)點(diǎn)處重新參與排序，那么最終得到的最大堆一定滿足任意節(jié)點(diǎn)間的有序關(guān)系。

//堆排序
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);        //調(diào)整最頂端的值 
    }   
}

計(jì)數(shù)排序

此前所有的排序算法均沒有考慮到數(shù)組的內(nèi)在分布，如果我們輸入的數(shù)據(jù)為某個(gè)區(qū)間內(nèi)的整數(shù)，那么我們只需建立這個(gè)區(qū)間內(nèi)的整數(shù)索引，然后將每個(gè)數(shù)歸類到這個(gè)索引之中即可。

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

例如，我們有一組均勻分布在[ 0 , 100 ] 之內(nèi)的數(shù)據(jù)，所謂基數(shù)排序，即先劃分出十個(gè)不同的桶[ 0 , 10 ) , [ 10 , 20 ) , … , [ 90 , 100 ) ，然后再對(duì)每個(gè)桶進(jìn)行單獨(dú)的排序。這樣劃分下去，那么基數(shù)排序的復(fù)雜度則為O ( 10 ∗ n ) 。

詞典中的排序方式也可以理解為一種基數(shù)排序，即首先看第一個(gè)字母的順序，然后第二個(gè)，依次類推。由于桶排序?qū)?shù)據(jù)做了假設(shè)，所以其最優(yōu)時(shí)間復(fù)雜度可以達(dá)到O ( n + k ),k為桶的數(shù)目。

例如，我們有一個(gè)由一百個(gè)由1和2組成的數(shù)組，那么我們只需建立一個(gè)索引1 : n 1 , 2 : n ₂，然后統(tǒng)計(jì)1和2分別出現(xiàn)的個(gè)數(shù)即可，其時(shí)間復(fù)雜度也將變成O ( n ) 。

在這里只做出最簡(jiǎn)單的計(jì)數(shù)排序。

/計(jì)數(shù)排序,輸入數(shù)組為整數(shù)
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;         //索引長(zhǎng)度
    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;          //此值為真實(shí)數(shù)據(jù)
        for (int j = n; j < n+arrSort[i]; j++)
            arrSort[j] = i+aMin;
        n += arrSort[i];
    }
}

總結(jié)

到此這篇關(guān)于C語言實(shí)現(xiàn)各種排序算法(選擇,冒泡,插入,歸并,希爾,快排,堆排序,計(jì)數(shù))的文章就介紹到這了,更多相關(guān)C語言實(shí)現(xiàn)各種排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: