一、冒泡排序

1.原理

從數(shù)組的頭開始不斷比較相鄰兩個(gè)數(shù)的大小，不斷將較大的數(shù)右移，一個(gè)循環(huán)后，最大數(shù)移至最后一位，無(wú)序數(shù)組規(guī)模減一。不斷重復(fù)前面動(dòng)作，知道數(shù)組完全有序。

2.實(shí)現(xiàn)

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void bubble_sort(int* arr, int len)
{
    bool issort = false;
    while (!issort)
    {
        issort = true;//如果有序則直接退出
        for (int i = 1; i < len; i++)
        {
            if (arr[i-1] > arr[i])//不斷比較相鄰兩個(gè)數(shù)
            {
                swap(&arr[i - 1], &arr[i]);//將較大的數(shù)不斷往右移
                issort = false;//如果進(jìn)行了交換則無(wú)序
            }
        }
        len--;//無(wú)序規(guī)模減一
    }
}

3.算法分析

時(shí)間復(fù)雜度： 最好情況，當(dāng)數(shù)組完全有序，則只需要進(jìn)行一輪比較，時(shí)間復(fù)雜度為o(n)；最壞情況為完全無(wú)序，每次比較后都要將該數(shù)移至數(shù)組末尾，時(shí)間復(fù)雜度為o(n ^2)；平均時(shí)間復(fù)雜度為o(n ^2)。

空間復(fù)雜度： 冒泡排序?yàn)榫偷嘏判?空間復(fù)雜度為o(1)。

穩(wěn)定排序： 當(dāng)數(shù)字相同時(shí)不會(huì)改變相對(duì)次序。

二、選擇排序

1.原理

數(shù)組前面為無(wú)序，后面為有序。剛開始全是無(wú)序，從中選擇一個(gè)最大值與最后一個(gè)無(wú)序數(shù)字進(jìn)行交換，無(wú)序數(shù)組規(guī)模減一，有序數(shù)組規(guī)模加一。不斷循環(huán)前面操作，直到數(shù)組變?yōu)橛行驍?shù)組?；蛘咔懊鏋橛行驍?shù)組，后面為無(wú)序數(shù)組，不斷選擇最小值與無(wú)序數(shù)組的第一個(gè)數(shù)交換，前面的有序數(shù)組加一，后面的無(wú)序數(shù)組減一。

2.實(shí)現(xiàn)

void selection_sort(int* arr, int len)
{
    int max_index;
    while (len)
    {
        max_index = 0;
        for (int i = 1; i < len; i++)
        {
            if (arr[max_index] < arr[i])
            {
                max_index = i;//獲取最大值的索引
            }
        }
        swap(&arr[max_index], &arr[len - 1]);//將最大值與最后一個(gè)值交換
        len--;//無(wú)序規(guī)模減一
    }
}

3.算法分析

時(shí)間復(fù)雜度： 所有的復(fù)雜度為每次選擇最大值，不管數(shù)字的有序性，時(shí)間復(fù)雜度都為o(n)+o(n-1)+…+o(1)=o(n^2)。所以該算法平均復(fù)雜度、最好情況、最差情況都為o(n ^2)。

空間復(fù)雜度： 就地排序，空間復(fù)雜度為o(1)。

不穩(wěn)定性算法： 排序后相同元素的順序可能被打亂。例子：選擇最大進(jìn)行排序。3,1,2,2* 第一輪排序后 2*,1,2,3 2的相對(duì)順序發(fā)生了改變。選擇最小進(jìn)行排序，2*,2,3,1 第一輪排序后1,2,3,2*. 2的相對(duì)順序也被打亂。如果增加空間復(fù)雜度也能將選擇排序變成穩(wěn)定性排序。

三、插入排序

1.原理

數(shù)組前面為有序，后面為無(wú)序，將無(wú)序數(shù)組中的第一個(gè)數(shù)不斷插入有序數(shù)組中（具體實(shí)現(xiàn)為不斷比較相鄰兩數(shù)大小，前面一個(gè)數(shù)大于后一個(gè)數(shù)，則交換順序，較小的數(shù)不斷前移），有序規(guī)模增加一，無(wú)序規(guī)模減小一?；蛘?，數(shù)組前面為無(wú)序，后面為有序，通過(guò)將無(wú)序數(shù)組的最后一位數(shù)字插入有序數(shù)組中（具體實(shí)現(xiàn)為將無(wú)序數(shù)組的最后一位與相鄰的有序數(shù)組不斷比較，將無(wú)序數(shù)組不斷右移）。

2.實(shí)現(xiàn)

void insert_sort(int arr[], int len)
{
    for (int i = 1; i < len; i++)//i前面為有序
    {
        for (int j = i - 1; j >= 0; j--)//j為有序數(shù)的末尾
        {
            bool issort = true;//當(dāng)數(shù)組有序時(shí)能夠提前退出
            if (arr[j] > arr[j + 1])//將無(wú)序數(shù)組的第一個(gè)數(shù)不斷與有序數(shù)組比較
            {
                swap(&arr[j], &arr[j + 1]);//將無(wú)序數(shù)字插入有序數(shù)組合適的位置
                issort = false;
            }
            if (issort) break;
        }
    }
}

3.算法分析

時(shí)間復(fù)雜度： 插入排序和冒泡排序類似，最好情況完全有序則時(shí)間復(fù)雜度為o(n)，最壞情況為完全無(wú)序時(shí)間復(fù)雜度為o(n^2)，平均復(fù)雜度為o(n ^2)。

空間復(fù)雜度： 就地排序不需要額外空間，空間復(fù)雜度為o(1)。

穩(wěn)定性排序： 和冒泡排序類似。

四、希爾排序

1.原理

每次選擇一個(gè)增量進(jìn)行分組，增量不斷減小到一（為插入排序），數(shù)組不斷變得有序，增量為一時(shí)變成完全有序。屬于插入排序的改進(jìn)，通過(guò)增量進(jìn)行分組，對(duì)每一組進(jìn)行插入排序，相比于插入排序的優(yōu)勢(shì)在于，shell排序能夠大尺度的移動(dòng)每一組的最小值，而插入排序得挨著進(jìn)行比較，所以shell排序效率更高。

增量為6：

每一組只有兩個(gè)數(shù)，分別比較兩個(gè)數(shù)的大小，如64,57交換順序變成57,64，所有的分組比較完后繼續(xù)縮減增量。

增量為3：

每一組有四個(gè)數(shù)，總共三組，分別為23,12,53,79；57,9,64,87；24,16,71,97；以增量開始（12開始）遍歷數(shù)組，遍歷到12則在第一組中對(duì)12進(jìn)行插入排序，交換23和12的順序；遍歷到9則在第二組對(duì)9進(jìn)行插入排序。。。。遍歷到64對(duì)一組中的9,57,64進(jìn)行插入排序。最后每一組都變得有序。整體有序性變大。

增量為1：

對(duì)之前排序過(guò)的數(shù)組進(jìn)行插入排序，通過(guò)前面的步驟數(shù)組有序性變大，最后進(jìn)行插入排序的效率就更高。

2.實(shí)現(xiàn)

void shell_sort(int* arr, int len)
{
    int gap = 0; //分組的跨度
    int i = 0;
    int j = 0;
    for (gap = len / 2; gap >= 1; gap /= 2) //分組增量
    {
        for (i = gap; i < len; i++) {  //遍歷每組
            for (j = i - gap; j >= 0; j -= gap)  //對(duì)組內(nèi)進(jìn)行插入排序
            {
                if (arr[j] > arr[j + gap])
                {
                    swap(&arr[j], &arr[j + gap]);
                }
            }
        }
    }
}

3.算法分析

時(shí)間復(fù)雜度：最好情況為完全有序o(n),最差情況為完全無(wú)序o(n^2)，平均復(fù)雜度為o(n ^1.3)。

空間復(fù)雜度：該算法為就地排序空間復(fù)雜度為o(1)。

穩(wěn)定性：shell排序在分組中可能將相同數(shù)字劃分成不同的分組，會(huì)改變相對(duì)順序，屬于不穩(wěn)定性排序算法。

總結(jié)

冒泡排序、選擇排序、插入排序、希爾排序的實(shí)現(xiàn)都是基于線性表進(jìn)行實(shí)現(xiàn)的（數(shù)組或者鏈表），實(shí)現(xiàn)邏輯都是通過(guò)比較數(shù)字的大小。算法的時(shí)間復(fù)雜度都比較大，但是屬于就地排序，不需要額外空間。幾種算法相比之下希爾排序更具有優(yōu)勢(shì)。

到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)經(jīng)典排序算法的示例代碼的文章就介紹到這了,更多相關(guān)C語(yǔ)言排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論