十大排序算法C++完整实现教程

Zhang_Xuu

800人浏览 · 2025-10-10 11:19:33

Zhang_Xuu · 2025-10-10 11:19:33 发布

九大排序算法C++完整实现教程

1. 冒泡排序

算法原理

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果顺序错误就交换位置，直到没有需要交换的元素为止。

时间复杂度

最优时间：O(n)
平均时间：O(n²)
最坏时间：O(n²)
空间复杂度：O(1)
稳定性：稳定
原地排序

C++实现

#include <iostream>
#include <vector>
using namespace std;

/**
 * 冒泡排序函数
 * @param arr 待排序的整数数组（引用传递）
 * 核心思想：相邻元素两两比较，大的元素"冒泡"到后面
 */
void bubbleSort(vector<int>& arr) {
    int n = arr.size();  // 获取数组长度
    
    // 外层循环：控制遍历的趟数，需要n-1趟
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;  // 优化标志：记录本趟是否发生交换
        
        // 内层循环：每趟将最大元素冒泡到末尾
        // 每趟结束后，最后i个元素已经有序，不需要再比较
        for (int j = 0; j < n - i - 1; j++) {
            // 如果前面的元素大于后面的元素，则交换
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);  // STL提供的交换函数
                swapped = true;  // 标记发生了交换
            }
        }
        
        // 优化：如果本趟没有发生交换，说明数组已经有序，提前结束
        if (!swapped) break;
    }
}

2. 选择排序

算法原理

选择排序每次从未排序的部分中选择最小（或最大）的元素，放到已排序序列的末尾。

时间复杂度

最优时间：O(n²)
平均时间：O(n²)
最坏时间：O(n²)
空间复杂度：O(1)
稳定性：不稳定

C++实现

/**
 * 选择排序函数
 * @param arr 待排序的整数数组（引用传递）
 * 核心思想：每次从未排序部分选择最小元素，放到已排序部分的末尾
 */
void selectionSort(vector<int>& arr) {
    int n = arr.size();  // 获取数组长度
    
    // 外层循环：控制选择的趟数，需要n-1趟
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;  // 假设当前位置i是未排序部分的最小元素
        
        // 内层循环：在未排序部分[i+1, n-1]中查找最小元素的索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;  // 更新最小元素的索引
            }
        }
        
        // 如果最小元素不是当前位置，则交换
        // 将找到的最小元素与位置i的元素交换
        if (minIdx != i) {
            swap(arr[i], arr[minIdx]);
        }
    }
}

3. 插入排序

算法原理

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

时间复杂度

最优时间：O(n)
平均时间：O(n²)
最坏时间：O(n²)
空间复杂度：O(1)
稳定性：稳定

C++实现

/**
 * 插入排序函数
 * @param arr 待排序的整数数组（引用传递）
 * 核心思想：像整理扑克牌一样，将每张牌插入到已排序部分的正确位置
 */
void insertionSort(vector<int>& arr) {
    int n = arr.size();  // 获取数组长度
    
    // 外层循环：从第二个元素开始，逐个将元素插入到已排序部分
    // 第一个元素arr[0]可以看作已排序部分
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 保存当前要插入的元素
        int j = i - 1;     // j指向已排序部分的最后一个元素
        
        // 内层循环：在已排序部分[0, i-1]中找到key的正确位置
        // 将所有大于key的元素向后移动一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // 元素后移
            j--;  // 继续向前查找
        }
        
        // 找到正确位置，插入key
        // 此时j+1就是key应该插入的位置
        arr[j + 1] = key;
    }
}

4. 希尔排序

算法原理

希尔排序是插入排序的改进版本，通过将数组分成若干子序列分别进行插入排序，逐步减小增量直到为1。

时间复杂度

最优时间：O(n log n)
平均时间：O(n^1.3)
最坏时间：O(n²)
空间复杂度：O(1)
稳定性：不稳定

C++实现

/**
 * 希尔排序函数
 * @param arr 待排序的整数数组（引用传递）
 * 核心思想：改进的插入排序，通过间隔gap将数组分组，对每组进行插入排序
 *          逐步缩小gap，最后gap=1时完成最终排序
 */
void swap(vector<int>& arr, int left, int right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
    vector<int> shellSort(vector<int>& arr) {
        int n = arr.size();
        for (int gap = n / 2; gap; gap /= 2)
            for (int i = gap; i < n; ++i)
                for (int j = i; j >= gap && arr[j - gap] > arr[j]; j -= gap)
                    std::swap(arr[j], arr[j - gap]);

        return arr;
    }
    // 最后一趟gap=1时，等同于标准的插入排序，保证整个数组有序
}

5. 归并排序

算法原理

归并排序采用分治法，将数组分成两半分别排序，然后合并两个有序数组。

时间复杂度

最优时间：O(n log n)
平均时间：O(n log n)
最坏时间：O(n log n)
空间复杂度：O(n)
稳定性：稳定

C++实现

/**
 * 合并函数：将两个有序子数组合并成一个有序数组
 * @param arr 原数组
 * @param left 左子数组的起始索引
 * @param mid 左子数组的结束索引（也是右子数组的起始索引-1）
 * @param right 右子数组的结束索引
 */
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;  // 左子数组的长度
    int n2 = right - mid;      // 右子数组的长度
    
    // 创建临时数组来存储左右子数组
    vector<int> L(n1), R(n2);
    
    // 将数据复制到临时数组L[]和R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];  // 复制左子数组
    for (int i = 0; i < n2; i++)
        R[i] = arr[mid + 1 + i];  // 复制右子数组
    
    // 合并两个临时数组回到原数组arr[left...right]
    int i = 0;      // 左子数组的初始索引
    int j = 0;      // 右子数组的初始索引
    int k = left;   // 合并后数组的初始索引
    
    // 比较左右子数组的元素，将较小的元素放入原数组
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {  // 使用<=保证稳定性
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    
    // 将左子数组中剩余的元素复制到arr中（如果有的话）
    while (i < n1) arr[k++] = L[i++];
    
    // 将右子数组中剩余的元素复制到arr中（如果有的话）
    while (j < n2) arr[k++] = R[j++];
}

/**
 * 归并排序的递归函数
 * @param arr 待排序的数组
 * @param left 要排序的子数组的起始索引
 * @param right 要排序的子数组的结束索引
 * 核心思想：分治法，将数组分成两半，分别排序后再合并
 */
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {  // 递归的终止条件：子数组长度大于1
        // 计算中间位置，使用(right-left)/2避免整数溢出
        int mid = left + (right - left) / 2;
        
        // 递归排序左半部分 [left, mid]
        mergeSort(arr, left, mid);
        
        // 递归排序右半部分 [mid+1, right]
        mergeSort(arr, mid + 1, right);
        
        // 合并两个已排序的子数组
        merge(arr, left, mid, right);
    }
}

/**
 * 归并排序的对外接口函数
 * @param arr 待排序的整数数组
 */
void mergeSort(vector<int>& arr) {
    mergeSort(arr, 0, arr.size() - 1);
}

6. 快速排序

算法原理

快速排序通过选择一个基准元素，将数组分为小于基准和大于基准的两部分，然后递归排序。

时间复杂度

最优时间：O(n log n)
平均时间：O(n log n)
最坏时间：O(n²)
空间复杂度：O(log n)
稳定性：不稳定，因为<=会把后面的移到前面去。

C++实现

/**
 * 分区函数：选择一个基准元素，将数组分为两部分
 * @param arr 待分区的数组
 * @param low 子数组的起始索引
 * @param high 子数组的结束索引
 * @return 基准元素的最终位置
 * 分区后：左边元素 < 基准元素 <= 右边元素
 */
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准元素
    int i = low - 1;        // i指向小于基准元素的区域的最后一个位置
    
    // 遍历数组[low, high-1]，将小于基准的元素移到左边
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {  // 如果当前元素小于基准
            i++;  // 扩大小于基准的区域
            swap(arr[i], arr[j]);  // 将当前元素交换到小于基准的区域
        }
    }
    
    // 将基准元素放到正确的位置（i+1）
    // 此时i+1左边的元素都小于基准，右边的元素都大于等于基准
    swap(arr[i + 1], arr[high]);
    return i + 1;  // 返回基准元素的位置
}

/**
 * 快速排序的递归函数
 * @param arr 待排序的数组
 * @param low 要排序的子数组的起始索引
 * @param high 要排序的子数组的结束索引
 * 核心思想：选择基准元素，分区后递归排序左右两部分
 */
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {  // 递归终止条件：子数组长度大于1
        // 分区操作，返回基准元素的位置
        int pi = partition(arr, low, high);
        
        // 递归排序基准元素左边的子数组 [low, pi-1]
        quickSort(arr, low, pi - 1);
        
        // 递归排序基准元素右边的子数组 [pi+1, high]
        quickSort(arr, pi + 1, high);
    }
}

/**
 * 快速排序的对外接口函数
 * @param arr 待排序的整数数组
 */
void quickSort(vector<int>& arr) {
    if (!arr.empty()) {
        quickSort(arr, 0, arr.size() - 1);
    }
}

7. 堆排序

算法原理

堆排序利用堆这种数据结构，先将数组构建成最大堆，然后依次取出堆顶元素放到数组末尾。

时间复杂度

最优时间：O(n log n)
平均时间：O(n log n)
最坏时间：O(n log n)
空间复杂度：O(1)
稳定性：不稳定

C++实现

/**
 * 堆调整函数（大顶堆）：维护堆的性质
 * @param arr 待调整的数组
 * @param n 堆的大小（有效元素个数）
 * @param i 要调整的节点索引
 * 功能：确保以i为根的子树满足大顶堆性质（父节点 >= 子节点）
 */
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;        // 初始化最大值为根节点
    int left = 2 * i + 1;   // 左子节点的索引
    int right = 2 * i + 2;  // 右子节点的索引
    
    // 如果左子节点存在且大于根节点，更新最大值索引
    if (left < n && arr[left] > arr[largest])
        largest = left;
    
    // 如果右子节点存在且大于当前最大值，更新最大值索引
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    // 如果最大值不是根节点，需要进行调整
    if (largest != i) {
        swap(arr[i], arr[largest]);  // 交换根节点和最大值节点
        
        // 递归调整受影响的子树
        // 因为交换可能破坏了子树的堆性质
        heapify(arr, n, largest);
    }
}

/**
 * 堆排序函数
 * @param arr 待排序的整数数组
 * 核心思想：
 * 1. 构建大顶堆（最大元素在堆顶）
 * 2. 将堆顶元素与末尾元素交换，堆大小减1
 * 3. 重新调整堆，重复步骤2，直到堆大小为1
 */
void heapSort(vector<int>& arr) {
    int n = arr.size();
    
    // 第一步：构建大顶堆（Build Max Heap）
    // 从最后一个非叶子节点开始，自底向上调整
    // 最后一个非叶子节点的索引是 n/2 - 1
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // 第二步：逐个提取堆顶元素（最大值）
    // 将堆顶元素（最大值）与末尾元素交换，然后重新调整堆
    for (int i = n - 1; i > 0; i--) {
        // 将当前堆的最大值（arr[0]）移到数组末尾（arr[i]）
        swap(arr[0], arr[i]);
        
        // 调整剩余元素，使其重新满足堆性质
        // 堆的大小减1（变为i），不包括已排序的元素
        heapify(arr, i, 0);
    }
    // 排序完成后，数组从小到大有序
}

8. 计数排序

算法原理

计数排序不基于比较，而是统计每个元素出现的次数，适用于整数且范围不大的情况。

时间复杂度

最优时间：O(n + k)
平均时间：O(n + k)
最坏时间：O(n + k)
空间复杂度：O(k)，k为数据范围
稳定性：稳定

C++实现

/**
 * 计数排序函数
 * @param arr 待排序的整数数组
 * 核心思想：统计每个元素出现的次数，然后按顺序输出
 * 适用场景：整数排序，且数据范围不大（否则会浪费大量空间）
 * 优点：线性时间复杂度，稳定排序
 */
void countingSort(vector<int>& arr) {
    if (arr.empty()) return;  // 空数组直接返回
    
    // 找出数组中的最大值和最小值，确定计数数组的范围
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;  // 计数数组的大小
    
    // 创建计数数组和输出数组
    vector<int> count(range, 0);    // 计数数组，初始化为0
    vector<int> output(arr.size()); // 输出数组，存储排序结果
    
    // 第一步：统计每个元素出现的次数
    // count[i]表示值为(i + minVal)的元素出现的次数
    for (int num : arr)
        count[num - minVal]++;
    
    // 第二步：累加计数数组，使count[i]表示小于等于(i + minVal)的元素个数
    // 这样count[i]-1就是值为(i + minVal)的元素在输出数组中的最后位置
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];
    
    // 第三步：构建输出数组（从后向前遍历保证稳定性）
    // 从后向前遍历原数组，保证相同元素的相对顺序不变
    for (int i = arr.size() - 1; i >= 0; i--) {
        // 找到arr[i]在输出数组中的位置
        output[count[arr[i] - minVal] - 1] = arr[i];
        // 该元素已放置，计数减1（处理重复元素）
        count[arr[i] - minVal]--;
    }
    
    // 第四步：将排序结果复制回原数组
    arr = output;
}

9. 基数排序

算法原理

基数排序按照数字的每一位进行排序，从最低位到最高位依次排序。

时间复杂度

最优时间：O(d × (n + k))
平均时间：O(d × (n + k))
最坏时间：O(d × (n + k))
空间复杂度：O(n + k)
稳定性：稳定

C++实现

int getMax(vector<int>& arr) {
    return *max_element(arr.begin(), arr.end());
}

void countingSortByDigit(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n);
    vector<int> count(10, 0);
    
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;
    
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    arr = output;
}

void radixSort(vector<int>& arr) {
    int maxVal = getMax(arr);
    
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSortByDigit(arr, exp);
}

10. 桶排序

算法原理

分成几段

C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    // 桶排序函数
    vector<float> bucketSort(vector<float>& arr) {
        int n = arr.size();
        if (n <= 1)
            return arr;  // 特判：空数组或单个元素直接返回

        // ① 创建 n 个桶
        vector<vector<float>> buckets(n);

        // ② 把元素分配到桶中
        for (int i = 0; i < n; i++) {
            int index = n * arr[i];   // 计算桶索引 (假设 arr[i] ∈ [0,1) )
            buckets[index].push_back(arr[i]);
        }

        // ③ 对每个桶内部排序
        for (int i = 0; i < n; i++)
            sort(buckets[i].begin(), buckets[i].end());

        // ④ 合并所有桶中的结果
        vector<float> sorted;
        for (int i = 0; i < n; i++)
            for (float val : buckets[i])
                sorted.push_back(val);

        return sorted;
    }
};

完整测试代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr)
        cout << num << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    
    cout << "原始数组: ";
    printArray(arr);
    
    // 测试冒泡排序
    vector<int> arr1 = arr;
    bubbleSort(arr1);
    cout << "冒泡排序: ";
    printArray(arr1);
    
    // 测试快速排序
    vector<int> arr2 = arr;
    quickSort(arr2);
    cout << "快速排序: ";
    printArray(arr2);
    
    // 测试归并排序
    vector<int> arr3 = arr;
    mergeSort(arr3);
    cout << "归并排序: ";
    printArray(arr3);
    
    return 0;
}

排序算法对比总结

算法	最优时间	平均时间	最坏时间	空间复杂度	稳定性
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
希尔排序	O(n log n)	O(n^1.3)	O(n²)	O(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定
基数排序	O(d×(n+k))	O(d×(n+k))	O(d×(n+k))	O(n+k)	稳定