排序算法总结（C++）

一、稳定性

排序算法的稳定性是指：同样大小的样本 **（同样大小的数据）**在排序之后不会改变原始的相对次序。

稳定性对基础类型对象（如平常的数组）来说毫无意义；稳定性对非基础类型对象（如一些自定义类）有意义，可以保留之前的相对次序。

二、排序算法

• 基于比较的排序：
  只需要定义好两个对象之间怎么比较即可，对象的数据特征并不关心，很通用（除下面两种）；

• 不基于比较的排序：
  和比较无关的排序，对于对象的数据特征有要求，并不通用（如计数排序、基数排序）；

选择、冒泡、插入排序

// 交换数组中的两个元素
void swap(int arr[], int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// 选择排序
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);
    }
}

// 冒泡排序
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

// 插入排序
void insertionSort(int arr[], int n) {
    if (arr == nullptr || n < 2) {
        return;
    }
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
            // printarr(arr, n); // 打印当前数组状态
        }
        
    }
}

归并排序

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // 用于 std::memset

const int MAXN = 100001;

int arr[MAXN];
int help[MAXN];
int n;

// 归并排序递归版
void mergeSort1(int l, int r) {
    if (l == r) {
        return;
    }
    int m = (l + r) / 2;
    mergeSort1(l, m);
    mergeSort1(m + 1, r);
    int i = l, a = l, b = m + 1;
    while (a <= m && b <= r) {
        help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
    }
    while (a <= m) {
        help[i++] = arr[a++];
    }
    while (b <= r) {
        help[i++] = arr[b++];
    }
    for (i = l; i <= r; i++) {
        arr[i] = help[i];
    }
}

// 归并排序非递归版
void mergeSort2() {
    for (int step = 1; step < n; step <<= 1) {
        int l = 0;
        while (l < n) {
            int m = l + step - 1;
            if (m + 1 >= n) {
                break;
            }
            int r = std::min(l + (step << 1) - 1, n - 1);
            int i = l, a = l, b = m + 1;
            while (a <= m && b <= r) {
                help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
            }
            while (a <= m) {
                help[i++] = arr[a++];
            }
            while (b <= r) {
                help[i++] = arr[b++];
            }
            for (i = l; i <= r; i++) {
                arr[i] = help[i];
            }
            l = r + 1;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }

    // 选择一种归并排序方式
    // mergeSort1(0, n - 1);
    mergeSort2();

    for (int i = 0; i < n - 1; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << arr[n - 1] << std::endl;

    return 0;
}

随机快速排序

#include <iostream>
#include <cstdlib> // 用于 rand() 和 srand()
#include <ctime>   // 用于 time()

const int MAXN = 100001;
int arr[MAXN];
int n;

// 随机快速排序改进版
void quickSort2(int l, int r) {
    if (l >= r) {
        return;
    }
    // 随机选择基准值
    int x = arr[l + rand() % (r - l + 1)];
    // 调用荷兰国旗问题的划分函数
    partition2(l, r, x);
    // 获取等于区域的左右边界
    int left = first;
    int right = last;
    // 递归排序左右两部分
    quickSort2(l, left - 1);
    quickSort2(right + 1, r);
}

// 荷兰国旗问题的划分函数
int first, last;//分别控制左右两侧的边界移动

void partition2(int l, int r, int x) {
    first = l;
    last = r;
    int i = l;
    while (i <= last) {
        if (arr[i] == x) {
            i++;
        } else if (arr[i] < x) {
            std::swap(arr[first++], arr[i++]);
        } else {
            std::swap(arr[i], arr[last--]);
        }
    }
}

// 主函数
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }

    // 初始化随机数种子
    std::srand(std::time(nullptr));

    // 调用快速排序
    quickSort2(0, n - 1);

    // 输出排序结果
    for (int i = 0; i < n - 1; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << arr[n - 1] << std::endl;

    return 0;
}

堆排序

#include <iostream>
#include <vector>

// 主函数，对数组进行排序
std::vector<int> sortArray(std::vector<int>& nums) {
    if (nums.size() > 1) {
        // heapSort1为从顶到底建堆然后排序
        // heapSort2为从底到顶建堆然后排序
        // 用哪个都可以
        // heapSort1(nums);
        heapSort2(nums);
    }
    return nums;
}

// i位置的数，向上调整大根堆
// arr[i] = x，x是新来的！往上看，直到不比父亲大，或者来到0位置(顶)
void heapInsert(std::vector<int>& arr, int i) {
    while (arr[i] > arr[(i - 1) / 2]) {
        swap(arr, i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
}

// i位置的数，变小了，又想维持大根堆结构
// 向下调整大根堆
// 当前堆的大小为size
void heapify(std::vector<int>& arr, int i, int size) {
    int l = i * 2 + 1;
    while (l < size) {
        // 有左孩子，l
        // 右孩子，l+1
        // 评选，最强的孩子，是哪个下标的孩子
        int best = (l + 1 < size && arr[l + 1] > arr[l]) ? l + 1 : l;
        // 上面已经评选了最强的孩子，接下来，当前的数和最强的孩子之前，最强下标是谁
        best = (arr[best] > arr[i]) ? best : i;
        if (best == i) {
            break;
        }
        swap(arr, best, i);
        i = best;
        l = i * 2 + 1;
    }
}

void swap(std::vector<int>& arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// 从顶到底建立大根堆，O(n * logn)
// 依次弹出堆内最大值并排好序，O(n * logn)
// 整体时间复杂度O(n * logn)
void heapSort1(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        heapInsert(arr, i);
    }
    int size = n;
    while (size > 1) {
        swap(arr, 0, --size);
        heapify(arr, 0, size);
    }
}

// 从底到顶建立大根堆，O(n)
// 依次弹出堆内最大值并排好序，O(n * logn)
// 整体时间复杂度O(n * logn)
void heapSort2(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = n - 1; i >= 0; i--) {
        heapify(arr, i, n);
    }
    int size = n;
    while (size > 1) {
        swap(arr, 0, --size);
        heapify(arr, 0, size);
    }
}

int main() {
    // 示例测试
    std::vector<int> nums = {3, 2, 1, 5, 6, 4};
    std::vector<int> sortedNums = sortArray(nums);

    std::cout << "排序后的数组: ";
    for (int num : sortedNums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

基数排序

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // 用于 memset

using namespace std;

const int BASE = 100; // 可以设置进制
const int MAXN = 50001;

int help[MAXN];
int cnts[BASE];

// 返回 number 在 BASE 进制下有几位
int bits(int number) {
    int ans = 0;
    while (number > 0) {
        ans++;
        number /= BASE;
    }
    return ans;
}

// 基数排序核心代码
// arr 内要保证没有负数
// n 是 arr 的长度
// bits 是 arr 中最大值在 BASE 进制下有几位
void radixSort(vector<int>& arr, int n, int bits) {
    for (int offset = 1; bits > 0; offset *= BASE, bits--) {
        memset(cnts, 0, sizeof(cnts)); // 初始化计数数组
        for (int i = 0; i < n; i++) {
            // 数字提取某一位的技巧
            cnts[(arr[i] / offset) % BASE]++;
        }
        // 处理成前缀次数累加的形式
        for (int i = 1; i < BASE; i++) {
            cnts[i] = cnts[i] + cnts[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            // 前缀数量分区的技巧
            // 数字提取某一位的技巧
            help[--cnts[(arr[i] / offset) % BASE]] = arr[i];
        }
        for (int i = 0; i < n; i++) {
            arr[i] = help[i];
        }
    //      for (int num : arr) {
    //     cout << num << " ";
    // }
    // cout << endl;
    }
}

vector<int> sortArray(vector<int>& arr) {
    if (arr.size() > 1) {
        int n = arr.size();
        // 找到数组中的最小值
        int min_val = arr[0];
        for (int i = 1; i < n; i++) {
            min_val = min(min_val, arr[i]);
        }
        int max_val = 0;
        for (int i = 0; i < n; i++) {
            // 数组中的每个数字，减去最小值，转成非负数组
            arr[i] -= min_val;
            // 记录数组中的最大值
            max_val = max(max_val, arr[i]);
        }
        // 根据最大值在 BASE 进制下的位数，决定基数排序做多少轮
        radixSort(arr, n, bits(max_val));
        // 数组中所有数都减去了最小值，最后还原
        for (int i = 0; i < n; i++) {
            arr[i] += min_val;
        }
    }
    return arr;
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    // cin >> n;
    vector<int> arr({170, 45, 75, 90, 802, 24, 2, 66}); // 示例数组
    cout << "Enter the elements: ";
    // for (int i = 0; i < n; i++) {
    //     cin >> arr[i];
    // }

    vector<int> sorted_arr = sortArray(arr);
    cout << "Sorted array: ";
    for (int num : sorted_arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

计数排序

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 计数排序方法，接受一个整数数组作为参数，返回排序后的数组
vector<int> countingSort(const vector<int>& arr) {
    // 如果输入数组为空或者长度小于等于1，直接返回原数组
    // 因为空数组或只有一个元素的数组本身就是有序的
    if (arr.size() <= 1) {
        return arr;
    }

    // 找出数组中的最大值和最小值，用于确定计数数组的范围
    int max_val = arr[0];
    int min_val = arr[0];
    for (int num : arr) {
        // 如果当前数字大于最大值，则更新最大值
        if (num > max_val) {
            max_val = num;
        }
        // 如果当前数字小于最小值，则更新最小值
        else if (num < min_val) {
            min_val = num;
        }
    }

    // 创建计数数组，其长度为最大值与最小值的差加1
    // 这样计数数组的每个索引就可以对应于原数组中的一个值（经过最小值偏移）
    vector<int> count(max_val - min_val + 1, 0);
    // 统计原数组中每个值出现的次数
    // 通过将每个数减去最小值来得到在计数数组中的偏移索引
    for (int num : arr) {
        count[num - min_val]++;
    }

    // 将计数数组转换为每个元素的最终位置索引数组
    // 这里的操作是对计数数组进行累加
    // 例如，如果count[0]=3，count[1]=2，那么经过这个循环后count[1]=5
    // 表示原数组中值为1（假设最小值为0）的最后一个元素应该放在新数组的第5个位置（索引为4）
    for (size_t i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    // 创建一个与原数组长度相同的输出数组，用于存储排序后的结果
    vector<int> output(arr.size());
    // 从原数组的末尾开始遍历
    for (int i = arr.size() - 1; i >= 0; i--) {
        // 根据计数数组中的位置信息，将原数组中的元素放入输出数组中正确的位置
        // 注意这里要先减1，因为数组索引从0开始
        output[count[arr[i] - min_val] - 1] = arr[i];
        // 将计数数组中对应位置的值减1，表示已经处理了一个该值的元素
        count[arr[i] - min_val]--;
    }

    // 返回排序后的数组
    return output;
}

// 主函数，用于测试计数排序算法
int main() {
    vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    // 调用计数排序方法对数组进行排序
    vector<int> sorted = countingSort(arr);
    // 输出排序后的数组
    for (int num : sorted) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

三、总结

• 数据量非常小的情况下可以做到非常迅速：插入排序
• 性能优异、实现简单且利于改进（面对不同业务可以选择不同划分策略）、不在乎稳定性：随机快排
• 性能优异、不在乎额外空间占用、具有稳定性：归并排序
• 性能优异、额外空间占用要求O(1)、不在乎稳定性：堆排序