程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 七種常見經典排序算法總結（C++實現）

七種常見經典排序算法總結（C++實現）

編輯：關於C語言

排序算法是非常常見也非常基礎的算法，以至於大部分情況下它們都被集成到了語言的輔助庫中。排序算法雖然已經可以很方便的使用，但是理解排序算法可以幫助我們找到解題的方向。

1. 冒泡排序 (Bubble Sort)

冒泡排序是最簡單粗暴的排序方法之一。它的原理很簡單，每次從左到右兩兩比較，把大的交換到後面，每次可以確保將前M個元素的最大值移動到最右邊。

步驟

從左開始比較相鄰的兩個元素x和y，如果 x > y 就交換兩者
執行比較和交換，直到到達數組的最後一個元素
重復執行1和2，直到執行n次，也就是n個最大元素都排到了最後

void bubble_sort(vector<int> &nums)
{
    for (int i = 0; i < nums.size() - 1; i++) { // times
        for (int j = 0; j < nums.size() - i - 1; j++) { // position
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

交換的那一步可以不借助temp，方法是

nums[j] += nums[j + 1];
nums[j + 1] = num[j] - nums[j + 1];
nums[j] -= num[j + 1];

復雜度分析

由於我們要重復執行n次冒泡，每次冒泡要執行n次比較（實際是1到n的等差數列，也就是(a1 + an) * n / 2），也就是 O(n^2)。空間復雜度是O(n)。

2. 插入排序（Insertion Sort）

插入排序的原理是從左到右，把選出的一個數和前面的數進行比較，找到最適合它的位置放入，使前面部分有序。

步驟

從左開始，選出當前位置的數x，和它之前的數y比較，如果x < y則交換兩者
對x之前的數都執行1步驟，直到前面的數字都有序
選擇有序部分後一個數字，插入到前面有序部分，直到沒有數字可選擇

void insert_sort(vector<int> &nums)
{
    for (int i = 1; i < nums.size(); i++) { // position
        for (int j = i; j > 0; j--) {
            if (nums[j] < nums[j - 1]) {
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }
        }
    }
}

復雜度分析

因為要選擇n次，而且插入時最壞要比較n次，所以時間復雜度同樣是O(n^2)。空間復雜度是O(n)。

3. 選擇排序（Selection Sort）

選擇排序的原理是，每次都從亂序數組中找到最大（最小）值，放到當前亂序數組頭部，最終使數組有序。

步驟

從左開始，選擇後面元素中最小值，和最左元素交換
從當前已交換位置往後執行，直到最後一個元素

void selection_sort(vector<int> &nums)
{
    for (int i = 0; i < nums.size(); i++) { // position
        int min = i;
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }

        int temp = nums[i];
        nums[i] = nums[min];
        nums[min] = temp;
    }
}

復雜度分析

每次要找一遍最小值，最壞情況下找n次，這樣的過程要執行n次，所以時間復雜度還是O(n^2)。空間復雜度是O(n)。

4. 希爾排序（Shell Sort）

希爾排序從名字上看不出來特點，因為它是以發明者命名的。它的另一個名字是“遞減增量排序算法“。這個算法可以看作是插入排序的優化版，因為插入排序需要一位一位比較，然後放置到正確位置。為了提升比較的跨度，希爾排序將數組按照一定步長分成幾個子數組進行排序，通過逐漸減短步長來完成最終排序。

例子

例如 [10, 80, 70, 100, 90, 30, 20]
如果我們按照一次減一半的步長來算，這個數組第一次排序時以3為步長，子數組是：

10 80 70
90 30 20
100

這裡其實按照列劃分的4個子數組，排序後結果為

10 30 20
90 80 70
100

也就是 [10, 30 20 90 80 70 100]

然後再以1為步長生成子數組

10
30
20
..

這個時候就是一縱列了，也就是說最後一定是以一個數組來排序的。

步驟

計算當前步長，按步長劃分子數組
子數組內插入排序
步長除以2後繼續12兩步，直到步長最後變成1

void shell_sort(vector<int> &nums)
{
    for (int gap = nums.size() >> 1; gap > 0; gap >>= 1) { // times
        for (int i = gap; i < nums.size(); i++) { // position
            int temp = nums[i];

            int j = i - gap;
            for (; j >= 0 && nums[j] > temp; j -= gap) {
                nums[j + gap] = nums[j];
            }

            nums[j + gap] = temp;
        }
    }
}

復雜度分析

希爾排序的時間復雜度受步長的影響，具體分析在維基百科。

5. 歸並排序（Merge Sort）

歸並排序是采用分治法（Divide and Conquer）的一個典型例子。這個排序的特點是把一個數組打散成小數組，然後再把小數組拼湊再排序，直到最終數組有序。

步驟

把當前數組分化成n個單位為1的子數組，然後兩兩比較合並成單位為2的n/2個子數組
繼續進行這個過程，按照2的倍數進行子數組的比較合並，直到最終數組有序

void merge_array(vector<int> &nums, int b, int m, int e, vector<int> &temp)
{
    int lb = b, rb = m, tb = b;
    while (lb != m && rb != e)
        if (nums[lb] < nums[rb])
            temp[tb++] = nums[lb++];
        else
            temp[tb++] = nums[rb++];

    while (lb < m)
        temp[tb++] = nums[lb++];
    
    while (rb < e)
        temp[tb++] = nums[rb++];

    for (int i = b;i < e; i++)
        nums[i] = temp[i];
}

void merge_sort(vector<int> &nums, int b, int e, vector<int> &temp)
{
    int m = (b + e) / 2;
    if (m != b) {
        merge_sort(nums, b, m, temp);
        merge_sort(nums, m, e, temp);
        merge_array(nums, b, m, e, temp);
    }
}

這個實現中加了一個temp，是和原數組一樣大的一個空間，用來臨時存放排序後的子數組的。

復雜度分析

在merge_array過程中，實際的操作是當前兩個子數組的長度，即2m。又因為打散數組是二分的，最終循環執行數是logn。所以這個算法最終時間復雜度是O(nlogn)，空間復雜度是O(n)。

6. 快速排序（Quick Sort）

快速排序也是利用分治法實現的一個排序算法。快速排序和歸並排序不同，它不是一半一半的分子數組，而是選擇一個基准數，把比這個數小的挪到左邊，把比這個數大的移到右邊。然後不斷對左右兩部分也執行相同步驟，直到整個數組有序。

步驟

用一個基准數將數組分成兩個子數組
將大於基准數的移到右邊，小於的移到左邊
遞歸的對子數組重復執行1，2，直到整個數組有序

void quick_sort(vector<int> &nums, int b, int e, vector<int> &temp)
{
    int m = (b + e) / 2;
    if (m != b) {
        int lb = b, rb = e - 1;

        for (int i = b; i < e; i++) {
            if (i == m)
                continue;
            if (nums[i] < nums[m])
                temp[lb++] = nums[i];
            else
                temp[rb--] = nums[i];
        }
        temp[lb] = nums[m];
        
        for (int i = b; i < e; i++)
            nums[i] = temp[i];
        
        quick_sort(nums, b, lb, temp);
        quick_sort(nums, lb + 1, e, temp);
    }
}

解法2: 不需要輔助空間

void quick_sort(vector<int> &nums, int b, int e)
{
    if (b < e - 1) {
        int lb = b, rb = e - 1;
        while (lb < rb) {
            while (nums[rb] >= nums[b] && lb < rb)
                rb--;
            while (nums[lb] <= nums[b] && lb < rb)
                lb++;
            swap(nums[lb], nums[rb]);
        }
        swap(nums[b], nums[lb]);
        quick_sort(nums, b, lb);
        quick_sort(nums, lb + 1, e);
    }
}

復雜度分析

快速排序也是一個不穩定排序，時間復雜度看維基百科。空間復雜度是O(n)。

7. 堆排序（Heap Sort）

堆排序經常用於求一個數組中最大k個元素時。因為堆實際上是一個完全二叉樹，所以用它可以用一維數組來表示。因為最大堆的第一位總為當前堆中最大值，所以每次將最大值移除後，調整堆即可獲得下一個最大值，通過一遍一遍執行這個過程就可以得到前k大元素，或者使堆有序。

在了解算法之前，首先了解在一維數組中節點的下標：

i節點的父節點 parent(i) = floor((i-1)/2)
i節點的左子節點 left(i) = 2i + 1
i節點的右子節點 right(i) = 2i + 2

步驟

構造最大堆（Build Max Heap）：首先將當前元素放入最大堆下一個位置，然後將此元素依次和它的父節點比較，如果大於父節點就和父節點交換，直到比較到根節點。重復執行到最後一個元素。
最大堆調整（Max Heapify）：調整最大堆即將根節點移除後重新整理堆。整理方法為將根節點和最後一個節點交換，然後把堆看做n-1長度，將當前根節點逐步移動到其應該在的位置。
堆排序（HeapSort）：重復執行2，直到所有根節點都已移除。

void heap_sort(vector<int> &nums)
{
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; i--) { // build max heap
        max_heapify(nums, i, nums.size() - 1);
    }
    
    for (int i = n - 1; i > 0; i--) { // heap sort
        int temp = nums[i];
        num[i] = nums[0];
        num[0] = temp;
        max_heapify(nums, 0, i);
    }
}

void max_heapify(vector<int> &nums, int beg, int end)
{
    int curr = beg;
    int child = curr * 2 + 1;
    while (child < end) {
        if (child + 1 < end && nums[child] < nums[child + 1]) {
            child++;
        }
        if (nums[curr] < nums[child]) {
            int temp = nums[curr];
            nums[curr] = nums[child];
            num[child] = temp;
            curr = child;
            child = 2 * curr + 1;
        }
    }
}

復雜度分析

堆執行一次調整需要O(logn)的時間，在排序過程中需要遍歷所有元素執行堆調整，所以最終時間復雜度是O(nlogn)。空間復雜度是O(n)。