常见排序算法的 C++ 实现、复杂度和稳定性分析

发表于 更新于 分类于 ，

以下是在 LeetCode Playground 完成的 C++ 实现及测试用例：

以下是来自菜鸟教程的表格，给出了时间复杂度、空间复杂度和稳定性分析：

算法时间复杂度 - 平均时间复杂度 - 最好时间复杂度 - 最坏空间复杂度稳定性
冒泡排序O(n^2)O(n)O(n^2)O(1)稳定
插入排序O(n^2)O(n)O(n^2)O(1)稳定
选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定
快速排序O(nlogn)O(nlogn)O(n^2)O(logn)不稳定
计数排序O(n+k)O(n+k)O(n+k)O(k)稳定

1 冒泡排序

基本思想

遍历数组 nums，对于遍历到的元素 nums[i]，如果 nums[i] > nums[i+1]，那么交换 nums[i] 和 nums[i+1]，这样一轮下来，最后一位必然是 nums 中最大的数字，在下一轮遍历中可以避开这一元素。不断重复这一过程，直到无可遍历元素为止。

可以参考来自菜鸟教程的动图：

C++ 实现

void bubble_sort(std::vector<int>& nums) {
    int n = nums.size();
    for (int i = n-1; i >= 0; --i) {
        bool has_swap = false;
        for (int j = 0; j < i; ++j) {
            if (nums[j] > nums[j+1]) {
                std::swap(nums[j], nums[j+1]);
                has_swap = true;
            }
        }
        if (!has_swap) {
            return;
        }
    }
}

这里的实现，是在冒泡排序的基础实现之上，加了「早停」的思想，即：在一轮冒泡之后，如果没有发生交换，那么说明数组已经有序，直接退出即可。

这也是为什么，冒泡排序的时间复杂度在最好的情况下是 O(n)，因为最好的情况就是数组已经有序，只需遍历一次即可。

2 插入排序

基本思想

遍历数组 nums，对于遍历到的元素 nums[i]，嵌套遍历并后移其前的元素，直到找到比 nums[i] 小的元素，将 nums[i] 插入其后即可。

可以参考来自菜鸟教程的动图：

C++ 实现

void insertion_sort(std::vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        int val = nums[i], j = i-1;
        for (; j >= 0 && nums[j] > val; --j) {
            nums[j+1] = nums[j];
        }
        nums[j+1] = val;
    }
}

3 选择排序

基本思想

遍历数组 nums，对于遍历到的元素 nums[i]，嵌套遍历其后的所有元素，找出其中的最小值 nums[min_num_idx]，将 nums[i] 与 nums[min_num_idx] 进行交换即可。

可以参考来自菜鸟教程的动图：

C++ 实现

void selection_sort(std::vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        int min_num_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (nums[j] < nums[min_num_idx]) {
                min_num_idx = j;
            }
        }
        std::swap(nums[i], nums[min_num_idx]);
    }
}

4 归并排序

基本思想

将数组 nums 拆分为左右两个子数组，不断向下递归，直到无法拆分为止。拷贝左右两个子数组，使用两个指针不断比较，较小者放入原数组中，自此向上递归。

可以参考来自菜鸟教程的动图：

C++ 实现

递归版本：

void merge_sort_recursive_core(std::vector<int>& nums, int beg, int end) {
    if (beg >= end) return;
    int mid = beg + (end - beg) / 2;
    merge_sort_recursive_core(nums, beg, mid);
    merge_sort_recursive_core(nums, mid+1, end);
    std::vector<int> left_sub_arr(nums.begin()+beg, nums.begin()+mid+1);
    std::vector<int> right_sub_arr(nums.begin()+mid+1, nums.begin()+end+1);
    int i = beg, left_idx = 0, right_idx = 0;
    while (left_idx <= mid-beg && right_idx <= end-mid-1) {
        nums[i++] = left_sub_arr[left_idx] < right_sub_arr[right_idx] ?
            left_sub_arr[left_idx++] : right_sub_arr[right_idx++];
    }
    while (left_idx <= mid-beg) {
        nums[i++] = left_sub_arr[left_idx++];
    }
    while (right_idx <= end-mid-1) {
        nums[i++] = right_sub_arr[right_idx++];
    }
}

void merge_sort_recursive(std::vector<int>& nums) {
    int n = nums.size();
    merge_sort_recursive_core(nums, 0, n-1);
}

循环版本：

void merge_sort_loop(std::vector<int>& nums) {
    int n = nums.size();
    for (int seg = 1; seg < n; seg *= 2) {
        for (int beg = 0; beg < n; beg += seg*2) {
            int mid = min(n-1, beg+seg-1), end = min(n-1, beg+seg*2-1);
            std::vector<int> left_sub_arr(nums.begin()+beg, nums.begin()+mid+1);
            std::vector<int> right_sub_arr(nums.begin()+mid+1, nums.begin()+end+1);
            int i = beg, left_idx = 0, right_idx = 0;
            while (left_idx <= mid-beg && right_idx <= end-mid-1) {
                nums[i++] = left_sub_arr[left_idx] < right_sub_arr[right_idx] ? left_sub_arr[left_idx++] : right_sub_arr[right_idx++];
            }
            while (left_idx <= mid-beg) {
                nums[i++] = left_sub_arr[left_idx++];
            }
            while (right_idx <= end-mid-1) {
                nums[i++] = right_sub_arr[right_idx++];
            }
        }
    }
}

5 快速排序

基本思想

在数组 nums 中，挑选出一个基准数字 pivot，一般为数组头部的数字。使用两个指针 beg 和 end 分别从数组头部和尾部遍历，nums[end] 比 pivot 小者挪至 beg 处，nums[beg] 比 pivot 大者挪至 end 处，从而保证在 beg 和 end 相遇时，相遇位置左侧的所有元素均小于 pivot，相遇位置右侧的所有元素均大于 pivot。之后递归地处理左右两个子数组即可。

可以参考来自菜鸟教程的动图：

C++ 实现

递归版本：

void partition_recursive(std::vector<int>& nums, int beg, int end) {
    if (beg >= end) return;
    int pivot = nums[beg], beg_t = beg, end_t = end;
    while (beg < end) {
        while (beg < end && nums[end] > pivot) --end;
        nums[beg] = nums[end];
        while (beg < end && nums[beg] <= pivot) ++beg;
        nums[end] = nums[beg];
    }
    nums[beg] = pivot;
    partition_recursive(nums, beg_t, beg-1);
    partition_recursive(nums, beg+1, end_t);
}

void quick_sort_recursive(std::vector<int>& nums) {
    int n = nums.size();
    partition_recursive(nums, 0, n-1);
}

循环版本：

int partition_loop(std::vector<int>& nums, int beg, int end) {
    if (beg >= end) return -1;
    int pivot = nums[beg], beg_t = beg, end_t = end;
    while (beg < end) {
        while (beg < end && nums[end] > pivot) --end;
        nums[beg] = nums[end];
        while (beg < end && nums[beg] <= pivot) ++beg;
        nums[end] = nums[beg];
    }
    nums[beg] = pivot;
    return beg;
}

void quick_sort_loop(std::vector<int>& nums) {
    int n = nums.size();
    std::stack<pair<int, int>> s;
    s.push({0, n-1});
    while (!s.empty()) {
        auto [beg, end] = s.top(); s.pop();
        int idx = partition_loop(nums, beg, end);
        if (idx == -1) continue;
        s.push({beg, idx-1});
        s.push({idx+1, end});
    }
}

6 计数排序

基本思想

计数排序适用于：数据的范围不大，方差不大，且均为离散值。

在数组 nums 中，找到最小值 min_num 和最大值 max_num，就可以得到 nums 中数字的范围，将这个范围表示为计数数组 cnts，将 nums 中数字在对应索引处进行计数，最后将 cnts 中的数字依次填回 nums 即可。

可以参考来自菜鸟教程的动图：

C++ 实现

void counting_sort(std::vector<int>& nums) {
    if (nums.empty()) return;
    int min_num = INT_MAX, max_num = INT_MIN;
    for (auto num : nums) {
        min_num = min(min_num, num);
        max_num = max(max_num, num);
    }
    vector<int> cnts(max_num-min_num+1, 0);
    for (auto num : nums) {
        ++cnts[num-min_num];
    }
    int idx = 0;
    for (int i = 0; i < max_num-min_num+1; ++i) {
        for (int j = cnts[i]; j > 0; --j) {
            nums[idx++] = min_num + i;
        }
    }
}