C語言實現經典排序演演算法的範例程式碼

2022-08-08 22:02:27

一、氣泡排序

1.原理

從陣列的頭開始不斷比較相鄰兩個數的大小，不斷將較大的數右移，一個迴圈後，最大數移至最後一位，無序陣列規模減一。不斷重複前面動作，知道陣列完全有序。

2.實現

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])//不斷比較相鄰兩個數
            {
                swap(&arr[i - 1], &arr[i]);//將較大的數不斷往右移
                issort = false;//如果進行了交換則無序
            }
        }
        len--;//無序規模減一
    }
}

3.演演算法分析

時間複雜度：最好情況，當陣列完全有序，則只需要進行一輪比較，時間複雜度為o(n)；最壞情況為完全無序，每次比較後都要將該數移至陣列末尾，時間複雜度為o(n ^2)；平均時間複雜度為o(n ^2)。

空間複雜度：氣泡排序為就地排序,空間複雜度為o(1)。

穩定排序：當數位相同時不會改變相對次序。

二、選擇排序

1.原理

陣列前面為無序，後面為有序。剛開始全是無序，從中選擇一個最大值與最後一個無序數位進行交換，無序陣列規模減一，有序陣列規模加一。不斷迴圈前面操作，直到陣列變為有序陣列。或者前面為有序陣列，後面為無序陣列，不斷選擇最小值與無序陣列的第一個數交換，前面的有序陣列加一，後面的無序陣列減一。

2.實現

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]);//將最大值與最後一個值交換
        len--;//無序規模減一
    }
}

3.演演算法分析

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

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

不穩定性演演算法：排序後相同元素的順序可能被打亂。例子：選擇最大進行排序。3,1,2,2* 第一輪排序後 2*,1,2,3 2的相對順序發生了改變。選擇最小進行排序，2*,2,3,1 第一輪排序後1,2,3,2*. 2的相對順序也被打亂。如果增加空間複雜度也能將選擇排序變成穩定性排序。

三、插入排序

1.原理

陣列前面為有序，後面為無序，將無序陣列中的第一個數不斷插入有序陣列中（具體實現為不斷比較相鄰兩數大小，前面一個數大於後一個數，則交換順序，較小的數不斷前移），有序規模增加一，無序規模減小一。或者，陣列前面為無序，後面為有序，通過將無序陣列的最後一位數位插入有序陣列中（具體實現為將無序陣列的最後一位與相鄰的有序陣列不斷比較，將無序陣列不斷右移）。

2.實現

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

3.演演算法分析

時間複雜度：插入排序和氣泡排序類似，最好情況完全有序則時間複雜度為o(n)，最壞情況為完全無序時間複雜度為o(n^2)，平均複雜度為o(n ^2)。

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

穩定性排序：和氣泡排序類似。

四、希爾排序

1.原理

每次選擇一個增量進行分組，增量不斷減小到一（為插入排序），陣列不斷變得有序，增量為一時變成完全有序。屬於插入排序的改進，通過增量進行分組，對每一組進行插入排序，相比於插入排序的優勢在於，shell排序能夠大尺度的移動每一組的最小值，而插入排序得挨著進行比較，所以shell排序效率更高。

增量為6：

每一組只有兩個數，分別比較兩個數的大小，如64,57交換順序變成57,64，所有的分組比較完後繼續縮減增量。

增量為3：

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

增量為1：

對之前排序過的陣列進行插入排序，通過前面的步驟陣列有序性變大，最後進行插入排序的效率就更高。

2.實現

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)  //對組內進行插入排序
            {
                if (arr[j] > arr[j + gap])
                {
                    swap(&arr[j], &arr[j + gap]);
                }
            }
        }
    }
}