十大经典排序算法（C++实现）

前言

目前 Leetcode 刷题刷到排序算法部分，回顾一下十大经典排序算法。

1. 冒泡排序

排序细节：如果有序，直接返回

void bubble_sort(vector<int> &nums){
    bool isOrderly;
    for(int i = 1; i < nums.size(); i++){
        isOrderly = true;
        for(int j = 1; j < nums.size() - i + 1; j++){
            if(nums[j-1] > nums[j]){
                swap(nums[j-1], nums[j]);
                isOrderly = false;
            }
        }
        if(isOrderly){
            break;
        }
    }
}

2. 选择排序

void select_sort(vector<int> &nums){
    int index;
    for(int i = 0; i < nums.size(); i++){
        index = i;
        for(int j = i; j < nums.size(); j++){
            if(nums[j] < nums[index]){
                index = j;
            }
        }
        swap(nums[i], nums[index]);
    }
}

3. 插入排序

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

4. 希尔排序

void shell_sort(vector<int> &nums){
    int gap = nums.size() / 2;
    while(gap > 0){
        for(int i = 0; i < nums.size(); i++){
            for(int j = i; j >= gap; j -= gap){
                if(nums[j] < nums[j-gap]){
                    swap(nums[j], nums[j-1]);
                }
            }
        }
        gap /= 2;
    }
}

5. 归并排序

void merge_sort(vector<int> &nums, int l, int r, vector<int> &temp){
    if (l + 1 >= r) {
        return;
    }
    int mid = l + (r - l) / 2;
    merge_sort(nums, l, mid, temp);
    merge_sort(nums, mid, r, temp);
    int l_index = l, r_index = mid, index = l;
    while (l_index < mid || r_index < r) {
        if (r_index == r || (l_index < mid && nums[l_index] <= nums[r_index])) {
            temp[index++] = nums[l_index++];
        }else{
            temp[index++] = nums[r_index++];
        }
    }
    for (int i = l; i < r; i++) {
        nums[i] = temp[i];
    }
}

6. 快速排序

排序细节：使用双指针，实现空间复杂度 O(1)

1. right 指针从右往左找比第一个元素小的数
2. 然后 left 指针从左往右找比第一个大的元素
3. 二者互换元素，然后回到第一步
4. 当两指针相遇，交换第一个元素和两指针所指的元素

void quick_sort(vector<int> &nums, int l, int r) {
	if (l + 1 >= r) {
        return;
    }
    int left = l, right = r - 1, key = nums[l];
    while (left < right){
        while(left < right && nums[right] >= key) {
            --right;
        }
        while (left < right && nums[left] <= key) {
            ++left;
        }
        swap(nums[left], nums[right]);
    }
    swap(nums[l], nums[left]);
    quick_sort(nums, l, left);
    quick_sort(nums, left + 1, r);
}

7. 堆排序

排序细节：在完全二叉树中，最后一个非叶节点的索引为 len / 2 -1。父节点为 i 则左子节点为 i*2+1，右子节点为 i*2+2

void heap_sort(vector<int>& nums){
    auto adjust_heap = [](vector<int>& nums, int l, int r){
        int dad = l, son = dad * 2 + 1;
        while(son <= r){
            if(son + 1 <= r && nums[son] < nums[son + 1]){
                son++;
            }
            if(nums[dad] > nums[son]){
                return;
            }else{
                swap(nums[dad], nums[son]);
                dad = son;
                son = dad * 2 + 1;
            }
        }
    };
    // 初始化，从最后一个父节点开始调整
    for (int i = nums.size() / 2 - 1; i >= 0; i--){
        adjust_heap(nums, i, nums.size() - 1);
    }
    // 已经调整为大顶堆，依次将元素放在堆顶
    for (int i = nums.size() - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        adjust_heap(nums, 0, i - 1);
    }
}

8. 计数排序

其中 k 为数据范围，当 k 较大时，反而慢，所以只适合整数且数据范围较小的数据

void count_sort(vector<int> &nums){
    int max = INT_MIN, min = INT_MAX;
    for(auto& e : nums){
        if(e > max){
            max = e;
        }else if(e < min){
            min = e;
        }
    }
    vector<int> count(max - min + 1);
    for(auto& e : nums){
        count[e - min]++;
    }
    int index = 0;
    for(int i = 0; i < count.size(); i++){
        if(count[i] > 0){
            for(; count[i] > 0; count[i]--, index++){
                nums[index] = i + min;
            }
        }
    }
}

9. 桶排序

原理是将数组根据数据范围分到有限数量的桶里，每个桶再内部排序（内部排序算法不定），最后依次把各个桶中的记录列出来记得到有序序列。

由于桶排序的实现方式非常多，这里就不加代码了。

10. 基数排序

其中 k 是数据的最大位数，k 较大时反而慢。

void radix_sort(vector<int> &nums){
    int max = INT_MIN;
    for(auto& e : nums){
        if(e > max){
            max = e;
        }
    }
    int digit = 0;
    while(max > 0){
        max /= 10;
        digit++;
    }
    vector<vector<int>> temp(10);
    for(int i = 0; i < digit; i++){
        for(int j = 0; j < nums.size(); j++){
            int index = i == 0 ? nums[j] % 10 : (nums[j] / (i * 10)) % 10;
            temp[index].push_back(nums[j]);
        }
        int index = 0;
        for(auto& vec : temp){
            for(auto& e : vec){
                nums[index] = e;
                index++;
            }
            vec.clear();
        }
    }
}