飞道的博客

【数据结构】十大排序算法C++实现

2021-05-14 11:47 245人阅读  评论(0)

算法分类

十种常见排序算法可以分为两大类：

  • 比较类排序：通过比较来决定元素间的相对次序，时间复杂度为 O(nlogn)～O(n²)。
  • 非比较类排序：不通过比较来决定元素间的相对次序，其时间复杂度可以突破 O(nlogn)，以线性时间运行。



名次解释：

  • 时间/空间复杂度：描述一个算法执行时间/占用空间与数据规模的增长关系。
  • n：待排序列的个数。
  • k：“桶”的个数（上面的三种非比较类排序都是基于“桶”的思想实现的）。
  • In-place：原地算法，指的是占用常用内存，不占用额外内存。空间复杂度为 O(1) 的都可以认为是原地算法。
  • Out-place：非原地算法，占用额外内存。
  • 稳定性：假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。

时间复杂度为O(n2)级排序算法

冒泡排序

原理

冒泡排序有三种写法：

  • 一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位；
  • 经过优化的写法：使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生交换表示已经有序，不再继续排序；
  • 进一步优化的写法：除了使用变量记录当前轮次是否发生交换外，再使用一个变量记录上次发生交换的位置，下一轮排序时到达上次交换的位置就停止比较。

动图演示

将第一种第二种结合起来实现。本系列算法为升序排序,

代码

#include <bits/stdc++.h>
using namespace std;

class Solution{
   
public:
    vector<int> bubbleSort(vector<int>& nums){
   
        int i = nums.size()-1, j = 0;
        bool flag = true;
        for(; i > 0 && flag; i--){
   // 如果没有发生过交换，说明剩余部分已经有序，排序完成
            flag = false;
            for(j = 0; j < i; j++){
   //保持最右边元素已经排序
                if(nums[j] > nums[j+1]){
   // 如果左边的数大于右边的数，则交换，保证右边的数字最大
                    swap(nums[j],nums[j+1]);
                    flag = true; // 表示发生了交换
                }
            }
        }
        return nums;
    }
};

int main()
{
   
    Solution s;
    vector<int> nums = {
   8,9,1,7,2,3,5,4,6,0};
    vector<int> result = s.bubbleSort(nums);
    return 0;
}

算法分析

冒泡排序属于交换排序，是稳定排序，平均时间复杂度为 O(n2)，空间复杂度为 O(1)。

但是我们常看到冒泡排序的最优时间复杂度是 O(n)，那要如何优化呢？

上面就是优化后的代码，用了一个 flag 参数记录新一轮的排序中元素是否做过交换，如果没有，说明前面参与比较过的元素已经是正序，那就没必要再从头比较了，就可以优化到 O(n) 。

练习题

剑指 Offer 45. 把数组排成最小的数
LeetCode: 283. 移动零

交换元素技巧

  • 引入变量
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

不引入第三个变量

  • 加法
arr[j + 1] = arr[j + 1] + arr[j];
arr[j] = arr[j + 1] - arr[j];
arr[j + 1] = arr[j + 1] - arr[j];
  • 减法
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
arr[j + 1] = arr[j + 1] + arr[j];
  • 位运算
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];

选择排序

原理

  • 固定数组中的第一个元素，分别与剩余的所有元素进行比较，从而找到序列中的最小值和固定元素交换，如果固定元素就是最小值，则无需交换。
  • 在剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。

动图演示

代码

#include <bits/stdc++.h>
using namespace std;
class Solution{
   
public:
    vector<int> select(vector<int>& nums){
   
        int n = nums.size();
        for(int i = 0; i < n; i++){
   
            int tmp = i;//记录比当前元素小的元素下标
            for(int j = i+1; j < n; j++){
   
                if(nums[j] < nums[tmp])
                    tmp = j;
            }
            swap(nums[i],nums[tmp]);
        }
        return nums;
    }
};
int main()
{
   
    Solution s;
    vector<int> nums = {
   8,9,1,7,2,3,5,4,6,0};
    vector<int> result = s.select(nums);
    return 0;
}

算法分析

选择排序是不稳定排序，时间复杂度固定为 O(n2)，空间复杂度固定为 O(1)。
冒泡排序和选择排序有什么异同？
相同点：

  • 都是两层循环，时间复杂度都为 O(n2);
  • 都只使用有限个变量，空间复杂度 O(1)。

不同点：

  • 冒泡排序在比较过程中就不断交换；而选择排序增加了一个变量保存最小值 / 最大值的下标，遍历完成后才交换，减少了交换次数。
  • 冒泡排序法是稳定的，选择排序法是不稳定的。
    冒泡排序中，只有左边的数字大于右边的数字时才会发生交换，相等的数字之间不会发生交换，所以它是稳定的。
    而选择排序中，最小值和首位交换的过程可能会破坏稳定性。

练习题

LeetCode: 215. 数组中的第 K 个最大元素
LeetCode: 912. 排序数组

插入排序

原理

插入排序（Insertion-Sort）是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素的key，在已经排序的元素序列中从后向前扫描；
  3. 如果扫描到的元素（已排序）大于新元素key，将扫描到的元素移到下一位置；
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；

从接下来的n-1个元素开始重复步骤2~5。

动图演示

代码

#include <bits/stdc++.h>
using namespace std;
class Solution{
   
public:
    vector<int> insertSort(vector<int> &nums){
   
        int i = 1, j = 0;
        for(; i < nums.size(); i++){
   
            int tmp = nums[i];
            for(j = i; j > 0; j--){
   
                if(tmp < nums[j - 1])
                    nums[j] = nums[j-1];// 把已排序元素逐步向后挪位
                else
                    break;//不再执行j--操作
            }
            nums[j] = tmp;// 插入
        }
        return nums;
    }
};

int main()
{
      Solution s;
    vector<int> nums = {
   3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    vector<int> result = s.insertSort(nums);
    return 0;
}

算法分析

一般来说，插入排序都采用in-place在数组上实现(即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

练习题

LeetCode: 912. 排序数组
[LeetCode: 147. 对链表进行插入排序]

时间复杂度为O(nlog n)级排序算法

希尔排序

1959年Shell发明第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

原理

具体算法描述如下：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，这样可以让一个元素可以一次性地朝最终位置前进一大步，然后算法再取越来越小的步长进行排序。仅增量因子为1时，整个序列作为一个记录序列来处理，即最后一步进行普通的插入排序后，序列有序。

图片来源于【数据结构】十大排序算法—— C++实现＜全＞

动图演示

代码

#include <bits/stdc++.h>
using namespace std;
class Solution{
   
public:
    vector<int> shellSort(vector<int>& nums){
   
        int n = nums.size(), tmp = 0;
        int gap = n / 2;// 间隔序列，在希尔排序中我们称之为增量序列
        while(gap){
   
            for(int i = gap; i < n; i++){
   // 从 gap 开始，按照顺序将每个元素依次向前插入自己所在的组
                tmp = nums[i];//站起来，开始找位置
                int preIndex = i - gap;// 该组前一个数字的索引
                while(preIndex >= 0 && nums[preIndex] > tmp){
   
                    nums[preIndex + gap] = nums[preIndex];// 向后挪位置
                    preIndex -= gap;
                }
                nums[preIndex + gap] = tmp; // tmp找到了自己的位置，坐下
            }
            gap /= 2;
        }
        return nums;
    }
};
int main()
{
   
    Solution s;
    vector<int> nums = {
   8,9,1,7,2,3,5,4,6,0};
    vector<int> result = s.shellSort(nums);
    return 0;
}

算法分析

本例中，我们采用的增量序列为 Dm = N/2, Dk =Dk+1 /2，这个序列正是当年希尔发表此算法的论文时选用的序列，所以也被称之为希尔增量序列。
增量序列的选择会极大地影响希尔排序的效率。增量序列如果选得不好，希尔排序的效率可能比插入排序效率还要低。

LeetBook注: 希尔排序在面试或是实际应用中都很少遇到，读者仅需了解即可。

练习题

LeetCode: 506. 相对名次

堆排序

堆：符合以下两个条件之一的完全二叉树：

  • 根节点的值 ≥ 子节点的值，这样的堆被称之为最大堆，或大顶堆；
  • 根节点的值 ≤ 子节点的值，这样的堆被称之为最小堆，或小顶堆。

一棵深度为k且有2k-1个结点的二叉树称为满二叉树。

  • 满二叉树每一层的结点个数都达到了最大值, 即满二叉树的第i层上有 2i-1个结点 (i≥1) 。
  • 如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。
  • 从满二叉树和完全二叉树的定义可以看出, 满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树。

原理

堆排序过程如下：

  • 用数列构建出一个大顶堆，取出堆顶的数字；
  • 调整剩余的数字，构建出新的大顶堆，再次取出堆顶的数字；
  • 循环往复，完成整个排序。

整体的思路就是这么简单，我们需要解决的问题有两个：

  1. 如何用数列构建出一个大顶堆；
  2. 取出堆顶的数字后，如何将剩余的数字调整成新的大顶堆。
    构建大顶堆 & 调整堆
    构建大顶堆有两种方式：
  • 方案一：从 0 开始，将每个数字依次插入堆中，一边插入，一边调整堆的结构，使其满足大顶堆的要求；
  • 方案二：将整个数列的初始状态视作一棵完全二叉树，自底向上调整树的结构，使其满足大顶堆的要求。
    方案二更为常用，动图演示如下：

    将根节点的下标视为 0，则完全二叉树有如下性质：
  • 对于完全二叉树中的第 i 个数，它的左子节点下标：left = 2i + 1
  • 对于完全二叉树中的第 i 个数，它的右子节点下标：right = left + 1
  • 对于有 n 个元素的完全二叉树(n≥2)(n≥2)，它的最后一个非叶子结点的下标：n/2 - 1

动图演示

代码

#include <bits/stdc++.h>
using namespace std;

class Solution {
   
public:
    vector<int> sortArray(vector<int>& nums) {
   
        int len = nums.size();
        buildMaxHeap(nums, len); // 构建一个大顶堆 升序排列
        return nums;
    }
    void buildMaxHeap(vector<int>& nums, int len){
   
        //第一个for循环 从下到上 调整为大顶堆
        for(int i = len / 2 - 1; i >= 0; i--)
            adjustHeap(nums, i, len); // 逐一调整为大顶堆
        for(int i = len - 1; i >= 0; i--){
   
            swap(nums[0], nums[i]);  // 交换根结点和最后的结点 最大值放在最后
            adjustHeap(nums, 0 , i); // 对剩下的序列从上到下调整为大顶堆
        }

    }
    // 从上到下 调整为大顶堆
    void adjustHeap(vector<int>& nums, int node, int len){
   
        int left = 2 * node + 1;
        int right = 2 * node + 2;
        int max = node; // 定义max 存储某棵子树的最大结点下标
        if(left < len and nums[left] > nums[max])
            max = left; // 存在左孩子 左孩子结点大于其父结点
        if(right < len and nums[right] > nums[max])
            max = right;  // 判断该子树 哪一个结点大于父结点
        if(max != node){
    // 如果真存在子结点大于父结点的情况 进行交换
            swap(nums[max], nums[node]);
            adjustHeap(nums, max, len);// 交换后 判断子树结点是否满足大顶堆的性质
        }
    }

};

int main()
{
   
    Solution s;
    vector<int> nums = {
   8,9,1,7,2,3,5,4,6,0};
    vector<int> result = s.sortArray(nums);
    return 0;
}

算法分析

堆排序是不稳定的排序算法。

复杂度分析
堆排序分为两个阶段：初始化建堆（buildMaxHeap）和重建堆(adjustHeap，直译为大顶堆化）。所以时间复杂度要从这两个方面分析。

  • 根据数学运算可以推导出初始化建堆的时间复杂度为 O(n)，重建堆的时间复杂度为 O(nlogn)，所以堆排序总的时间复杂度为 O(nlogn)。推导过程较为复杂，故不再给出证明过程。
  • 堆排序的空间复杂度为 O(1)，只需要常数级的临时变量。

堆排序是一个优秀的排序算法，但是在实际应用中，快速排序的性能一般会优于堆排序，我们将在下一节介绍快速排序的思想。

练习题

LeetCode: 215. 数组中的第 K 个最大元素
剑指 Offer 40. 最小的 k 个数

快速排序

原理

快速排序算法的基本思想是：

  • 从数组中取出一个数，称之为基数（pivot）
  • 遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
  • 将左右两个区域视为两个数组，重复前两个步骤，直到排序完成

动图演示

代码

#include <bits/stdc++.h>
using namespace std;
class Solution{
   //考研《天勤高分笔记》的写法
public:
    void quickSort(vector<int>& nums, int left, int right){
   
        if(left >= right) return;
        int cur = left + 1;
        int pivot = left; //每次交换,pivot需要右移一个分界位置
        while(cur <= right){
   
            if(nums[left] >= nums[cur]){
   //交换位置,保证新分界点pivot左侧都是小于nums[pivot]
                swap(nums[pivot+1],nums[cur]);
                pivot++;
            }
            cur++;
        }
        swap(nums[pivot],nums[left]);//把分界点pivot移到新的分界位置
        quickSort(nums,left,pivot-1);
        quickSort(nums,pivot+1,right);
    }
    vector<int> sortArray(vector<int>& nums){
   
        int n = nums.size();
        quickSort(nums,0,n-1);
        return nums;
    }
};

class Solution2 {
   //严蔚敏《数据结构》定义枢轴函数写法
public:
// 将 nums 从 low 到 high 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
    int partition(vector<int>& nums,int low,int high){
   
        int pivot = nums[low]; // 取第一个数为基数
        while(low < high){
   
            while(low < high and nums[high] >= pivot)
                --high;// 找到第一个小于基数的位置
            nums[low] = nums[high];
            while(low < high and nums[low] <= pivot)
                ++low;// 找到第一个大于基数的位置
            nums[high] = nums[low];// 交换这两个数，使得左边分区都小于或等于基数，右边分区大于或等于基数
        }
        nums[low] = pivot;
        return low;
    }
    void QuickSort(vector<int>& nums,int low,int high){
   
        if(low < high){
   
            int pivotpos = partition(nums, low, high);// 将数组分区，并获得中间值的下标
            QuickSort(nums, low, pivotpos - 1);// 对左边区域快速排序
            QuickSort(nums, pivotpos + 1, high);// 对右边区域快速排序
        }
    }
    vector<int> sortArray(vector<int>& nums) {
    // 主函数
        int n = nums.size();
        QuickSort(nums, 0, n - 1);
        return nums;
    }
};

int main()
{
   
    Solution2 s;
    vector<int> nums = {
   8,9,1,7,2,3,5,4,6,0};
    vector<int> result = s.sortArray(nums);
    return 0;
}

算法分析

快速排序是一种不稳定的排序算法，在分区过程中，相同数字的相对顺序可能会被修改。

复杂度分析
平均时间复杂度为 O(nlogn)，最坏的时间复杂度为 O(n2)，空间复杂度与递归的层数有关，每层递归会生成一些临时变量，所以空间复杂度为 O(logn) ~ O(n)，平均空间复杂度为 O(logn)。

快速排序的优化思路

  • 第一种就是我们在前文中提到的，每轮选择基数时，从剩余的数组中随机选择一个数字作为基数。这样每轮都选到最大或最小值的概率就会变得很低了。所以我们才说用这种方式选择基数，其平均时间复杂度是最优的;
  • 第二种解决方案是在排序之前，先用洗牌算法将数组的原有顺序打乱，以防止原数组正序或逆序。

练习题

LeetCode: 169. 多数元素

归并排序

原理

具体算法描述如下：

  1. 把长度为n的输入序列分成两个长度为n/2的子序列；
  2. 对这两个子序列分别采用归并排序；
  3. 将两个排序好的子序列合并成一个最终的排序序列。

动图演示

代码

#include <bits/stdc++.h>
using namespace std;
class Solution {
   
public:
    vector<int> sortArray(vector<int>& nums) {
   
        int n = nums.size();
        MergeSort(nums, 0, n - 1);
        return nums;
    }
    void MergeSort (vector<int>& nums, int low,int high) {
   
        if(low >= high)
            return; // 终止递归的条件，子序列长度为1
        int mid =  low + (high - low) / 2;  // 取得序列中间的元素
        MergeSort(nums, low, mid);  // 对左半边递归
        MergeSort(nums, mid + 1, high);  // 对右半边递归
        Merge(nums, low, mid, high);  // 合并
    }
    void Merge(vector<int>& nums, int low, int mid, int high){
   
        //合并两个相邻有序区间,使之成为新的有序区间
        //low为第1有序区的第1个元素，i指向第1个元素, mid为第1有序区的最后1个元素
        int i = low,j = mid + 1, k = 0;  //mid+1为第2有序区第1个元素，j指向第1个元素
        //int *temp = new int[high - low + 1]; //temp数组暂存合并的有序序列
        vector<int> temp(high-low+1);
        while(i <= mid && j <= high){
   
            if(nums[i] <= nums[j]) //较小的先存入temp中
                temp[k++] = nums[i++];
            else
                temp[k++] = nums[j++];
        }
        while(i <= mid)//若比较完之后，第一个有序区仍有剩余，则直接复制到t数组中
            temp[k++] = nums[i++];
        while(j <= high)//同上
            temp[k++] = nums[j++];
        for(i=low, k=0; i <= high; i++,k++)//将排好序的存回arr中low到high这区间
            nums[i] = temp[k];
        //delete [] temp;//释放内存，由于指向的是数组，必须用delete []
    }
};
int main()
{
   
    Solution s;
    vector<int> nums = {
   8,9,1,7,2,3,5,4,6,0};
    vector<int> result = s.sortArray(nums);
    return 0;
}

算法分析

复杂度分析

  • 拆分数组的过程中，会将数组拆分 logn 次，每层执行的比较次数都约等于 n 次，所以时间复杂度是 O(nlogn)。
  • 空间复杂度是 O(n)，主要占用空间的就是我们在排序前创建的长度为 n 的 result 数组。

分析归并的过程可知，归并排序是一种稳定的排序算法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。

练习题

面试题 10.01. 合并排序的数组
剑指 Offer 51. 数组中的逆序对

时间复杂度为O(n)级排序算法

记数排序

原理

计数排序（Heap Sort）不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

创建一个长度为数组中最大元素+1的数组，用这个新的数组来统计原数组中每个元素出现的频率，然后遍历新的数组，根据每个元素出现的频率把元素放回到老的数组中，得到已经排好序的数组。过程如下:

  • 找出待排序的数组中最大和最小的元素；
  • 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
  • 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
  • 反向填充目标数组：将每个元素i放在新数组的第 C(i) 项，每放一个元素就将 C(i) 减去 1。

动图演示

代码

#include <bits/stdc++.h>
using namespace std;
class Solution{
   
public:
    vector<int> countSort(vector<int>& nums){
   
        int maxVal = *max_element(nums.begin(),nums.end());
        int n = maxVal+1, sortIndex = 0;//原数组重新插入元素下标
        vector<int> temp(n);//构造新数组,用于统计原数组每个元素频率
        for(int& i:nums) temp[i]++;
        for(int i = 0; i < n; i++){
   
            while(temp[i] > 0){
   //说明该元素在原数组中出现过,记录下来
                nums[sortIndex++] = i;
                temp[i]--;
            }
        }
        return nums;
    }
};

int main()
{
   
    Solution s;
    //vector<int> nums = {0,2,1,2,2,3,5,4,5,0};
    //vector<int> nums = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    vector<int> nums = {
   3,5,2,4};
    vector<int> result = s.countSort(nums);
    return 0;
}

算法分析

复杂度分析

  • 每次遍历都是进行 n 次或者 k 次，所以计数排序的时间复杂度为 O(n + k)，k 表示数据的范围大小。
  • 用到的空间主要是长度为 k 的计数数组和长度为 n 的结果数组，所以空间复杂度也是 O(n + k)。

计数排序属于非交换排序，是稳定排序，适合数据范围不显著大于数据数量的序列。

计数排序与O(nlogn) 级排序算法的本质区别

《算法导论》定理 8.1：在最坏情况下，任何比较排序算法都需要做 O(nlogn) 次比较。
《算法导论》推论8.2：堆排序和归并排序都是渐进最优的比较排序算法。

如果基于比较来进行排序，无论怎么优化都无法突破 O(nlogn) 的下界。计数排序和基于比较的排序算法相比，根本区别就在于：它不是基于比较的排序算法，而是利用了数字本身的属性来进行的排序。整个计数排序算法中没有出现任何一次比较

练习题

[1122. 数组的相对排序]

桶排序

桶排序 （Bucket sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

原理

桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

  • 设置一个定量的数组当作空桶(首先得到待排序序列的最大最小值, 根据给定桶的容量来确定桶的个数)；
  • 遍历输入数据，并且把数据一个一个放到对应的桶里去；
  • 对每个不是空的桶进行排序；
  • 从不是空的桶里把排好序的数据拼接起来。

动图演示

代码

#include <bits/stdc++.h>
using namespace std;
class Solution{
   
public:
    void countSort(vector<int>& nums){
   
        int maxValue = *max_element(nums.begin(),nums.end());
        int n = maxValue+1, sortIndex = 0;
        vector<int> temp(n);
        for(int& i:nums) temp[i]++;
        for(int i = 0; i < n; i++){
   
            while(temp[i] > 0){
   
                nums[sortIndex++] = i;
                temp[i]--;
            }
        }
    }
    vector<int> bucketSort(vector<int>& nums,int bucket_size = 10){
    // 定义桶的大小
        //int minValue = *min_element(nums.begin(),nums.end());
        //int maxValue = *max_element(nums.begin(),nums.end());
        int minValue = nums[0], maxValue = nums[0];
        for(int i = 1; i < nums.size(); i++){
   // 找到数组元素的范围
            if(nums[i] <= minValue) minValue = nums[i];
            else if(nums[i] >= maxValue) maxValue = nums[i];
        }
        int bucketCount = int( (maxValue - minValue) / bucket_size) + 1;// 计算出桶的数量
        vector<vector<int>> buckets(bucketCount,vector<int>());
        for(int i = 0; i < nums.size(); i++){
   // 把所有元素放入对应的桶里面
            int bucketId = int((nums[i]-minValue)/bucket_size);
            buckets[bucketId].push_back(nums[i]);
        }
        nums.clear();
        for(int i = 0; i < buckets.size(); i++){
   
            countSort(buckets[i]);// 对每个桶进行排序
            for(int j = 0; j < buckets[i].size(); j++){
   // 还原桶里面的元素到原数组
                nums.push_back(buckets[i][j]);
            }
        }
        return nums;
    }
};

int main()
{
   
    Solution s;
    //vector<int> nums = {0,2,1,2,2,3,5,4,5,0};
    vector<int> nums = {
   3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    int bucket_size = 10;
    vector<int> result = s.bucketSort(nums,bucket_size);
    return 0;
}

算法分析

桶排序是稳定排序，但仅限于桶排序本身，假如桶内排序采用了快速排序之类的非稳定排序，那么就是不稳定的。
复杂度分析

  • 每次遍历都是进行 n 次或者 k 次，所以计数排序的时间复杂度为 O(n + k)，k 表示桶中数据的数量。
  • 用到的空间主要是长度为 k 的计数数组和长度为 n 的结果数组，所以空间复杂度也是 O(n + k)。

练习题

基数排序

原理

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
具体算法描述如下：

  • 取得数组中的最大数，并取得其位数；
  • nums为原始数组，从最低位开始取每个位组成radix数组；
  • 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

动图演示

代码

#include <bits/stdc++.h>
using namespace std;

class Solution{
   
public:
    vector<int> radixSort(vector<int>& nums){
   
        int minValue = *min_element(nums.begin(),nums.end()); // 获取最大值和最小值
        int maxValue = *max_element(nums.begin(),nums.end());
        if(minValue < 0){
   // 假如序列中有负数，所有数加上一个常数，使序列中所有值变成正数
            for(int i = 0; i < nums.size(); i++) nums[i] -= minValue;
            maxValue -= minValue;
        }
        int digits = 0,  RADIX = 10;
        while(maxValue > 0){
   
            maxValue /= RADIX;
            digits++;// 获取最大值位数
        }
        vector<vector<int>> bucket( RADIX, vector<int>());
        int mod = 10, div = 1;
        for(int i = 0; i < digits; i++,mod *= 10, div *= 10){
   
            for(int j = 0; j < nums.size(); j++){
   
                int num = (nums[j] % mod) / div;//分别对待排序序列的个位、十位、百位……进行桶排序
                bucket[num].push_back(nums[j]);
            }
            int index = 0;
            for(int j = 0; j < bucket.size(); j++){
   
                for(int k = 0; k < bucket[j].size(); k++){
   
                    nums[index++] = bucket[j][k];
                }
                bucket[j].clear();
            }
        }
        if(minValue < 0){
   // 假如序列中有负数，收集排序结果时再减去前面加上的常数
            //for(int& i : nums) i += minValue;
            for(int i = 0; i < nums.size(); i++) nums[i] += minValue;
        }
        return nums;
    }
};
int main()
{
   
    Solution s;
    vector<int> nums = {
   0,2,1,2,2,3,5,4,5,0};
    //vector<int> nums = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    //vector<int> nums = {0,2,-1,-2};
    vector<int> result = s.radixSort(nums);
    return 0;
}

算法分析

基数排序是稳定排序，适用于关键字取值范围固定的排序。
复杂度分析

  • 每次遍历都是进行 n 次或者 k 次，所以计数排序的时间复杂度为 O(n + k)，k 表示桶中数据的数量。
  • 用到的空间主要是长度为 k 的计数数组和长度为 n 的结果数组，所以空间复杂度也是 O(n + k)。

练习题

164. 最大间距
561. 数组拆分 I

参考

数据结构十大排序算法讲解：算法原理和LeetCode代码实现（C++，java）
【数据结构】十大排序算法—— C++实现＜全＞
十大经典排序算法（C++实现）


转载：https://blog.csdn.net/qq_42147969/article/details/116718490
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场