快捷導(dǎo)航

一文帶你徹底看懂C++常見排序算法

更新時(shí)間：2026年01月06日 08:32:39 作者：落羽的落羽

在計(jì)算機(jī)科學(xué)中,排序算法是數(shù)據(jù)處理的基礎(chǔ)工具,這篇文章主要介紹了C++常見排序算法的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用C++具有一定的參考借鑒價(jià)值,需要的朋友可以參考下

前言

排序，就是使一組數(shù)據(jù)，按照某種規(guī)則，遞增或遞減排列起來的操作。是生活中應(yīng)用最廣泛的算法之一。包括多種排序算法，今天我們介紹最常見的幾種，下面， 我默認(rèn)都是用int數(shù)據(jù)排成升序作為演示。

一、插入排序

1. 直接插入排序

直接插入排序是一種簡單的插入排序法，基本思想是：把待排序的數(shù)據(jù)按照其大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄都插入完為止，得到一個(gè)新的有序序列。

這種排序思想，類比像我們玩撲克牌時(shí)一張張插入手牌。

當(dāng)插入第i個(gè)元素時(shí)，前面的arr[0] arr[1] ... arr[i-1]已經(jīng)是有序的了，此時(shí)用arr[i]，與這些數(shù)據(jù)進(jìn)行比較，找到正確的位置插入，原位置及之后的元素后移一位。

代碼實(shí)現(xiàn)：

void InsertSort(vector<int>& arr)
{
	int n = arr.size();
    for (int i = 1; i < n; ++i) 
    {
        int tmp = arr[i]; // 當(dāng)前待插入元素

        int j = i - 1;
        // 向前找比tmp大的元素，大就往后移一位
        while (j >= 0 && arr[j] > tmp) 
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = tmp; // 插入到正確位置
    }
}

測試：

復(fù)雜度分析：

時(shí)間復(fù)雜度O(n2)，數(shù)組越接近有序，時(shí)間效率越高
空間復(fù)雜度O(1)

2. 希爾排序

希爾排序是直接插入排序的優(yōu)化版本，也叫 “縮小增量排序”。它的基本思想是：先選定一個(gè)整數(shù)gap（通常是gap = n/3 + 1），把待排序數(shù)據(jù)按照下標(biāo)間隔gap分成各組（如n=10，gap = 4，則下標(biāo)0, 4, 8在同一組），并對每一組內(nèi)的數(shù)據(jù)進(jìn)行插入排序，然后gap = gap/3 + 1，再用新gap分成新組，進(jìn)行插入排序。當(dāng)gap = 1時(shí)，就相當(dāng)于直接插入排序了。

舉個(gè)直觀的分析過程例子：

原數(shù)組[8 9 1 7 2 3 5 4 6 0]

gap = 10/3 + 1 = 4按 gap=4 分組，每組元素下標(biāo)差為 4：
組 1：[8, 2, 6] → 插入排序后 [2, 6, 8]
組 2：[9, 3, 0] → 插入排序后 [0, 3, 9]
組 3：[1, 5] → 插入排序后 [1, 5]
組 4：[7, 4] → 插入排序后 [4, 7]
數(shù)組變?yōu)椋篬2, 0, 1, 4, 6, 3, 5, 7, 8, 9]
gap = 4/3 + 1 = 2按 gap=2 分組，每組元素下標(biāo)差為 2：
組 1：[2, 1, 6, 5, 8] → 插入排序后 [1, 2, 5, 6, 8]
組 2：[0, 4, 3, 7, 9] → 插入排序后 [0, 3, 4, 7, 9]
數(shù)組變?yōu)椋篬1, 0, 2, 3, 5, 4, 6, 7, 8, 9]
gap = 2/3 + 1 = 1此時(shí) gap=1，相當(dāng)于對整個(gè)基本有序的數(shù)組做直接插入排序：
排序后最終結(jié)果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)據(jù)更接近有序。gap == 1時(shí)，數(shù)組已經(jīng)接近有序了，進(jìn)行直接插入排序就會很快

代碼實(shí)現(xiàn)：

void ShellSort(vector<int>& arr)
{
    int n = arr.size();

    int gap = n;
    while (gap > 1) // gap > 1 時(shí)做預(yù)排序
    {
        gap = gap / 3 + 1;

        // 直接遍歷所有元素，按gap做插入排序
        for (int i = gap; i < n; i++)
        {
            int tmp = arr[i]; // 當(dāng)前待插入元素
            int j = i - gap; // 同組的前一個(gè)元素下標(biāo)

            // 向前找比tmp大的元素，大則后移
            while (j >= 0 && arr[j] > tmp)
            {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = tmp; // 插入到正確位置
        }
    }
}

測試：

復(fù)雜度分析：

時(shí)間復(fù)雜度：希爾排序的時(shí)間復(fù)雜度受gap的影響，很難去計(jì)算，通常介于O(n1.3)~O(n2)之間，數(shù)組越接近有序，時(shí)間效率越高。綜合來說，它的效率還是優(yōu)于直接插入排序的。
空間復(fù)雜度O(1)

二、選擇排序

選擇排序的基本思想是，每一次從待排序元素中選出最小的元素，放在已排好序列的起始位置，直到全部待排序數(shù)據(jù)選擇完畢。

1. 直接選擇排序

直接選擇排序，就是按照上面的思路進(jìn)行：

代碼實(shí)現(xiàn)：

void SelectSort(vector<int>& arr)
{
    int n = arr.size();
    for (int i = 0; i < n - 1; i++)
    {
        int min = i; // min記錄當(dāng)前最小元素的下標(biāo)

        // 找到[i+1, n)中的最小元素
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }
        //將找到的最小位置交換到當(dāng)前位置
        swap(arr[i], arr[min]);
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度O(n2)，實(shí)際中很少使用
空間復(fù)雜度O(1)

2. 堆排序

堆排序是指利用“堆”這種數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的一種排序算法，它是選擇排序的一種，利用堆來進(jìn)行選擇數(shù)據(jù)。以前我有一篇文章講過了：堆的講解當(dāng)時(shí)我是用C語言實(shí)現(xiàn)的，在C++中，我們有了std::priority_queue，而它的底層也是使用的堆；或者STL的算法庫中還有一個(gè)std::make_head，可以直接在一段迭代器區(qū)間上建堆！所以C++中寫堆排序可以直接利用它們了。

代碼實(shí)現(xiàn)：

// 寫法1, 用priority_queue
void HeapSort1(vector<int>& arr) 
{
    // 1. 構(gòu)建小根堆（priority_queue默認(rèn)是大根堆，要傳greater使堆頂為最小值）
    priority_queue<int, vector<int>, greater<int>> pq(arr.begin(), arr.end());

    int n = arr.size();
    // 堆頂是當(dāng)前最小值，從前往后填充數(shù)組
    for (int i = 0; i < n; i++)
    {
        arr[i] = pq.top();
        pq.pop();
    }
}

// 寫法2, 用make_heap算法
void HeapSort2(vector<int>& arr) 
{
    int n = arr.size();
    for (int i = 0; i < n; i++) 
    {
        //每次調(diào)整未排序部分為小根堆, 每次調(diào)整后堆頂位置i都是最小值
        make_heap(arr.begin() + i, arr.end(), greater<int>());
    }
}

測試：

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度O(1)

三、交換排序

所謂交換，就是根據(jù)序列中兩個(gè)數(shù)據(jù)的比較結(jié)果來交換它們在序列中的位置。

交換排序的特點(diǎn)是：將鍵值較大的數(shù)據(jù)向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

1. 冒泡排序

冒泡排序應(yīng)該是我們最早學(xué)習(xí)的一種排序算法了，不必多言

代碼實(shí)現(xiàn)：

void BubbleSort(vector<int>& arr) 
{
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) 
    {
        bool swapped = false; // 標(biāo)記是否發(fā)生交換

        // 每輪將最大元素“冒泡”到末尾
        for (int j = 0; j < n - 1 - i; ++j) 
        {
            if (arr[j] > arr[j + 1]) 
            {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) 
            break; // 無交換, 則已有序
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n2)
空間復(fù)雜度O(1)

2. 快速排序

快速排序是一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想是：取待排序元素序列中的某元素為基準(zhǔn)值，按照該值將待排序集合分割成兩子序列，左子序列中元素小于基準(zhǔn)值，右子序列元素大于基準(zhǔn)值。然后左右子序列重復(fù)該過程，直到所有元素排列完成。

以數(shù)組 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0] 為例，選第一個(gè)元素8作為基準(zhǔn)：

第一次分區(qū)（基準(zhǔn) = 8）
遍歷數(shù)組，將 <8 的元素放左邊，>8 的放右邊：
左區(qū)：[1,7,2,3,5,4,6,0]右區(qū)：[9]數(shù)組變?yōu)椋?code>[1,7,2,3,5,4,6,0,8,9]
遞歸處理左區(qū) [1,7,2,3,5,4,6,0]（基準(zhǔn) = 1）
分區(qū)后：
左區(qū)：[0]右區(qū)：[7,2,3,5,4,6]數(shù)組變?yōu)椋?code>[0,1,7,2,3,5,4,6,8,9]
遞歸處理右區(qū) [7,2,3,5,4,6]（基準(zhǔn) = 7）
分區(qū)后：
左區(qū)：[2,3,5,4,6]右區(qū)：[]數(shù)組變?yōu)椋?code>[0,1,2,3,5,4,6,7,8,9]
遞歸處理剩余子數(shù)組…
直到所有子數(shù)組長度為 1，最終得到有序數(shù)組：[0,1,2,3,4,5,6,7,8,9]

如何分出左右區(qū)是核心，有多種方法，這里介紹一種“挖坑法”：

代碼實(shí)現(xiàn)：

void _QuickSort(vector<int>& arr, int left, int right)
{
    if (left >= right)
        return;

    int l = left;
    int r = right;

    // 選第一個(gè)元素作為基準(zhǔn)，也可以選其他的
    int mid = arr[l];
    while (l < r)
    {
        // 從右找比基準(zhǔn)小的元素
        while (l < r && arr[r] >= mid)
        {
            r--;
        }
        arr[l] = arr[r]; // 放到基準(zhǔn)左邊的坑l，r成為新坑

        // 從左找比基準(zhǔn)大的元素
        while (l < r && arr[l] <= mid)
        {
            l++;
        }
        arr[r] = arr[l]; // 放到基準(zhǔn)右邊的坑r，l成為新坑
    }
    arr[l] = mid; // 基準(zhǔn)放到最終位置

    // 遞歸處理左右區(qū)間
    _QuickSort(arr, left, l - 1);  // 左區(qū)間：[left, l-1]
    _QuickSort(arr, l + 1, right); // 右區(qū)間：[l+1, right]
}

void QuickSort(vector<int>& arr)
{
    _QuickSort(arr, 0, arr.size() - 1);
}

測試：

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(nlogn)，std::sort主要就是快速排序?qū)崿F(xiàn)的
空間復(fù)雜度O(logn)

四、歸并排序

歸并排序是建立在歸并操作上的一種排序算法，采用分治的思路。

分：將待排序數(shù)組遞歸地拆分成兩個(gè)子數(shù)組，直到每個(gè)子數(shù)組只有1個(gè)元素（天然有序）治：遞歸地對每個(gè)子數(shù)組進(jìn)行歸并排序合并：將兩個(gè)有序的子數(shù)組合并成一個(gè)有序的大數(shù)組

以數(shù)組 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0] 為例，分步展示過程：

從最小的有序子數(shù)組開始，兩兩合并為更大的有序數(shù)組：
合并 [8] 和 [9] → [8,9]；
合并 [7] 和 [2] → [2,7]，再合并 [1] 和 [2,7] → [1,2,7]；
合并 [8,9] 和 [1,2,7] → [1,2,7,8,9]；
同理，右半部分合并為 [0,3,4,5,6]；
最終合并 [1,2,7,8,9] 和 [0,3,4,5,6] → [0,1,2,3,4,5,6,7,8,9]。

代碼實(shí)現(xiàn)：

void _MergeSort(vector<int>& arr, int left, int right) 
{
    if (left >= right) 
    {
        return; // 子數(shù)組長度為1，遞歸終止
    }

    // 等價(jià)于 (low + high)/2，但防止low+high超出int范圍
    int mid = left + (right - left) / 2;

    _MergeSort(arr, left, mid);       // 遞歸排序左子數(shù)組
    _MergeSort(arr, mid + 1, right);  // 遞歸排序右子數(shù)組

    // 合并左右數(shù)組
    // 臨時(shí)數(shù)組存儲合并結(jié)果
    vector<int> tmp(right - left + 1);

    int i = left;    // 指向左數(shù)組
    int j = mid + 1; // 指向右數(shù)組
    int k = 0;       // 指向臨時(shí)數(shù)組

    // 合并兩個(gè)有序子數(shù)組到臨時(shí)數(shù)組
    while (i <= mid && j <= right)
    {
        // 小的放入臨時(shí)數(shù)組
        if (arr[i] <= arr[j])
        {
            tmp[k++] = arr[i++];
        }
        else
        {
            tmp[k++] = arr[j++];
        }
    }

    // 處理左子數(shù)組剩余元素
    while (i <= mid)
        tmp[k++] = arr[i++];

    // 處理右子數(shù)組剩余元素
    while (j <= right)
        tmp[k++] = arr[j++];

    // 將臨時(shí)數(shù)組拷貝回原數(shù)組
    for (k = 0; k < tmp.size(); k++)
        arr[left + k] = tmp[k];
}

void MergeSort(vector<int>& arr) 
{
    _MergeSort(arr, 0, arr.size() - 1);
}

測試：