Loading... 使用模板编写，自带类型均可使用，使用类 class 或结构体 struct 时必须重载大于 > 运算符 参数汇总 -------- # 1. 冒泡排序 > 思路：比较相邻两个元素，小者交换到前面 > 从前到后两两交换，一直比较到最后，最大值置于最后 ## 1.0 简化冒泡 ```cpp template <typename T> void bubbleSort(vector<T>& nums) { for (int i = 0; i < nums.size() - 1; ++i) { for (int j = 0; j < nums.size() - 1 - i; ++j) if (nums[j] > nums[j + 1]) swap(nums[j], nums[j + 1]); } } ``` ## 1.1 优化 用 flag 优化，写有序时跳出循环 ```cpp void bubbleSort(vector<T>& nums) { for (int i = 0; i < nums.size() - 1; ++i) { bool flag = true; for (int j = 0; j < nums.size() - 1 - i; ++j) if (nums[j] > nums[j + 1]) { swap(nums[j], nums[j + 1]); flag = false; } if(flag) break; } } ``` ## 参数 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | :----------------: | :----------------: | :----------------: | :----------: | :------: | | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 | # 2. 选择排序 > 思路： 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 > 再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。 ```cpp template<typename T> void selectSort(vector<T>& nums) { for (int i = 0; i < nums.size() - 1; ++i) { int min = i; for (int j = i + 1; j < nums.size(); ++j) { if (nums[j] < nums[min]) min = j; } swap(nums[i], nums[min]); } } ``` ## 参数 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | :----------------: | :----------------: | :----------------: | :----------: | :------: | | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 | # 3. 插入排序 > 思路：从数组的第二个元素开始，将元素按顺序插入到前面已经排好序的数组中 > 一般以第一个元素作为起始元素，从第二个元素开始依次插入 ```cpp template<typename T> void insertSort(vector<T>& nums) { for (int i = 0; i < nums.size() - 1; ++i) { for (int j = i + 1; j > 0; --j) { if (nums[j] >= nums[j - 1]) break;// 减少比较次数 else swap(nums[j], nums[j - 1]); } } } ``` ## 参数 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | :----------------: | :----------------: | :----------------: | :----------: | :------: | | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 | # 4. 希尔排序 > 思路：希尔排序 插入排序的一种更高效的改进版本，非稳定排序算法 > 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序； > 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰分成一组，算法便终止 > 与插入排序区别是，插入排序每次递增量是 1 ，希尔排序是 gap ```cpp template<typename T> void shellSort(vector<T>& nums) { int i, j, gap; int n = nums.size(); for (gap = n / 2; gap > 0; gap /= 2) { // 共 gap 个组，对每组都执行直接插入排序 for (int i = 0; i < gap; ++i) {// 此后为插入排序！！！ // 注意内部循环写法 for (j = i + gap; j < n; j += gap) { // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。 if (nums[j] < nums[j - gap]) { T tmp = nums[j]; int k = j - gap; // 此时插入要向前循环，k 会变化，因此要检验 // 不能简单将上面式子代入！！ while (k >= 0 && nums[k] > tmp) { nums[k + gap] = nums[k]; k -= gap; } nums[k + gap] = tmp; //交换完成 } } } } } ``` ## 参数 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | :----------------: | :----------------: | :----------------: | :----------: | :------: | | $O(nlogn)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 不稳定 | # 5. 归并排序 > 思路：分而治之，后序遍历二叉树的思想 ```cpp template <typename T> // [] 区间 void mergeSort(vector<T> &nums, int left, int right) { if (left < right) { int mid = (right + left) >> 1; mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); mergeSortHelpter(nums, left, mid, right); } } template <typename T> void mergeSortHelpter(vector<T> &nums, int left, int mid, int right) { vector<T> tmp = nums; int start = left; // // 注意此处 start = left，不是 0 int i = start, j = mid + 1; // 都是 <= while (i <= mid && j <= right) nums[start++] = tmp[i] < tmp[j] ? tmp[i++] : tmp[j++]; while (i <= mid) nums[start++] = tmp[i++]; while (j <= right) nums[start++] = tmp[j++]; }``` ## 参数 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | |:---------:|:---------:|:---------:|:------:|:---:| | $O(nlog(n))$ | $O(nlog(n))$ | $O(nlog(n))$ | $O(n)$ | 稳定 | # 6. 快速排序 > 思路：在数组中选择一个元素作为基准 > 小于基准元素移到基准左边，反之移到基准右边（分区操作） > 此时基准元素所在位置就是排序完成后，基准元素的最终位置 > 对基准元素的左右两个子集重复一二步，直到子集中剩余一个元素为止 ```cpp template<typename T> void quickSort(vector<T>& nums, int left, int right) { if (left < right) { int pivot = quickSortHelper(nums, left, right); quickSort(nums, left, pivot - 1); quickSort(nums, pivot + 1, right); } } template<typename T> int quickSortHelper(vector<T>&nums, int left, int right) { int pivot = nums[left]; while (left < right) { // pivot 取 left，则先从右边开始 -- // 都是交换 left 与 right，pivot 只是起到一个记录的作用 while (left < right&&pivot <= nums[right]) right--; nums[left] = nums[right]; while (left < right&&nums[left] <= pivot) left++; nums[right] = nums[left]; } nums[left] = pivot; return left; } ``` ## 参数 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | :----------------: | :----------------: | :----------------: | :----------: | :------: | | $O(nlog(n))$ | $O(n^2)$ | $O(nlog(n))$ | $O(nlogn)$ | 不稳定 | # 7. 堆排序 利用堆此种数据结构设计的排序算法 堆是一种特殊的树（完全二叉树 叶子结点只可能在最大的两层出现） > 特点：根节点下标为 0，若父节点下标为 i 1. 其左孩子下标为 2*i+1 2. 右孩子为 2*i+2 3. 第一个非叶子节点为 arr.size()/2-1 - 小顶堆：每个节点的值都 >= 其子节点的值 => 堆排序的升序排序 - 大顶堆：每个节点的值都 <= 其子节点的值 => 堆排序的降序排序 - 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] - 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] ## 思想 利用大(小)顶堆记录最大(小)关键词的特性 1. 将数组构建成大顶堆，此堆为初始的无序区(堆顶确定) 2. 将堆顶元素R[0]与最后一个元素R[n-1]交换得到无序区[0,n-2]与有序区[n-1] 3. 调整无序区为新堆，重复2，3 4. 无序区不断减少，有序区逐渐增加，当有序区间元素个数为 n-1 时完成 ```cpp template <typename T> void heapSort(vector<T> &nums) { int n = nums.size(); //1. 构建一个最大堆 // 从最后一个非叶子节点开始 for (int i = n / 2 - 1; i >= 0; --i) { heapSortHelperMin(nums, i, n); //heapSortHelperMax(nums, i, n); } //2. 将堆顶（最大值）与末位交换，再重新调整最大堆 for (int i = n - 1; i > 0; --i) { swap(nums[0], nums[i]); // 构造堆时，遍历每个非叶子节点已经排好序 // 当交换元素时，只会影响最顶端的顺序，最低端是有序区 // 因为堆是整体有序的，因此只需要管理受影响的最顶端，有问题可以递归处理后面受影响的堆 heapSortHelperMin(nums, 0, i); //heapSortHelperMax(nums, 0, i); } } // 调整堆，不是构造堆 template <typename T> void heapSortHelperMax(vector<T> &nums, int father, int length) { int maxIndex = father; // 如有左子树，同时左子树大于父节点，则最大指针指向左子树 if (father * 2 + 1 < length && nums[father * 2 + 1] > nums[maxIndex]) maxIndex = 2 * father + 1; // 如有右子树，同时右子树大于父节点和左子树，则最大指针指向右子树 if (father * 2 + 2 < length && nums[father * 2 + 2] > nums[maxIndex]) maxIndex = 2 * father + 2; // 父节点不是最大值，则将父节点与最大值交换，同时递归调整 if (maxIndex != father) { swap(nums[maxIndex], nums[father]); heapSortHelperMax(nums, maxIndex, length); } } template <typename T> void heapSortHelperMin(vector<T> &nums, int father, int length) { int minIndex = father; if (father * 2 + 1 < length && nums[father * 2 + 1] < nums[minIndex]) minIndex = 2 * father + 1; if (father * 2 + 2 < length && nums[father * 2 + 2] < nums[minIndex]) minIndex = 2 * father + 2; if (minIndex != father) { swap(nums[minIndex], nums[father]); heapSortHelperMin(nums, minIndex, length); } } ``` ## 构造堆的其它方法 使用 STL 的优先队列，`priority_queue`，需要头文件<queue> 底层就是一个堆结构，通过 top() 来访问队首元素 `priority_queue< type, container, function >` 三个参数，后面两个可以省略，第一个不可以。其中： 1. **type**数据类型； 2. **container**实现优先队列的底层容器； 3. **function**元素之间的比较方式； container，要求必须是数组形式实现的容器，例如vector、deque，不能是list 在STL中，默认情况下（不加后面两个参数）是以vector为容器，以 operator< 为比较方式，所以在只使用第一个参数时，优先队列默认是一个最大堆，每次输出的堆顶元素是此时堆中的最大元素。 ```cpp // 默认为大顶堆 priority_queue<int> big_heap; //另一种构建大顶堆的方法 priority_queue<int,vector<int>,less<int> > big_heap2; //构造一个空的优先队列,此优先队列是一个小顶堆 priority_queue<int,vector<int>,greater<int> > small_heap; ``` ## 优先队列堆排序 ```cpp // 利用优先队列实现 template <typename T> // 调整遍历顺序或大小堆，即可逆转排序 void heapSort(vector<T> &nums) { int n = nums.size(); //1. 构建一个最大堆 priority_queue<T, vector<T>> bigHeap; priority_queue<T, vector<T>, less<T>> smallHeap; for (auto x : nums) bigHeap.push(x); //2. 将堆顶（最大值）与末位交换，再重新调整最大堆 for (int i = 0; i < n; ++i) { nums[i] = bigHeap.top(); bigHeap.pop(); } } ``` ## 参数 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | :----------------: | :----------------: | :----------------: | :----------: | :------: | | $O(nlog(n))$ | $O(nlog(n))$ | $O(nlog(n))$ | $O(1)$ | 不稳定 | # 8. 计数排序 > 思路：将输入的数据值转化为键存储在额外开辟的数组空间中 > 要求输入的数据：必须在***确定范围***内的***整数*** - 找出待排序的数组中最大和最小的元素 - 统计数组中每个值为i的元素出现的次数，存入数组C的第i项 - 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加） - 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1 ```cpp void countSort(vector<int>& nums) { int n = nums.size(); int minVal = nums[0], maxVal = nums[0]; for (int i = 0; i < n; ++i) { minVal = min(minVal , nums[i]); maxVal = max(maxVal, nums[i]); } vector<int> bucket(maxVal - minVal + 1, 0); int offset = minVal - 0; // 将数据存入 bucket for (auto x : nums) bucket[x - offset]++; int j = 0; for (int i = 0; i < bucket.size(); ++i) { // 对应数值是 i+offset // 每个数值次数是 bucket[i] // 外部 -- while (bucket[i]--) nums[j++] = i + offset; } } ``` ## 参数 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | :----------------: | :----------------: | :----------------: | :----------: | :------: | | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | 稳定 | # 9. 桶排序 桶排序是计数排序的升级版，利用函数的映射关系，把计数排序中的多个坑位整合成为一个桶 ## 思路 (1) 设置一个定量的数组当作空桶； (2) 遍历输入数据，并且把数据一个一个放到对应的桶里去； (3) 对每个不是空的桶进行排序； (4) 从不是空的桶里把排好序的数据拼接起来。 算法效率在于映射函数的确定。为了更加高效，需要： 1. 在外部空间充足的情况下，尽可能**增大桶的数量** 2. 使用的映射函数能够将输入的 N 个数据**均匀地分配到 K 个桶中** 最快：输入数据均匀分配到每个桶中 最慢：输入数据被分配到同一个桶中 当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 O(n) ```cpp // 桶排序 // 桶的大小 void bucketSort(vector<int>& nums, int bucketSize) { int n = nums.size(); if (n < 2) return; int minVal = nums[0], maxVal = nums[0]; for (int i = 1; i < n; ++i) { minVal = min(nums[i], minVal); maxVal = max(nums[i], maxVal); } // 桶的数量，当 bucketSize 为 1 时，退货为计数排序 int bucketCount = (maxVal - minVal) / bucketSize + 1; int offset = minVal - 0; vector<vector<int>> bucketVec(bucketCount, vector<int>()); // 元素入桶 for (int i = 0; i < n; ++i) { // 重点！！！ bucketVec[(nums[i] - offset) / bucketSize].push_back(nums[i]); } // clear 之后，不能直接用 []，因为并没有初始化，需要用 push_back nums.clear(); for (int i = 0; i < bucketCount; ++i) { // 内部可以选择方法对桶内元素进行排序 // 空桶跳过，提高效率 if (bucketVec[i].size() != 0) { sort(bucketVec[i].begin(), bucketVec[i].end()); for (auto x : bucketVec[i]) nums.push_back(x); //nums[j++] = x; } } } ``` ## 参数 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | :----------------: | :----------------: | :----------------: | :----------: | :------: | | $O(n+k)$ | $O(n^2)$ | $O(n)$ | $O(n+k)$ | 稳定 | # 10. 基数排序 一种非比较型整数排序算法，原理是将整数按位数切割成不同的数字，按每个位数分别比较 因为整数可以表达字符串(名字或日期)和特定模式的浮点数，因此基数排序也可用于字符串 ### 计数排序，桶排序，基数排序区别 三者都使用了桶的概念，但是 1. 计数排序：每个桶只存储单一键值 2. 桶排序：每个桶存储一定范围的数值 3. 基数排序：根据键值的每位数字来分配桶 基数排序的方式可以采用 LSD（Least significant digital） 或 MSD（Most significant digital） - LSD: 由键值的 最右边（最小位） 开始, 适用于位数少的序列，可采用桶排序 - MSD: 由键值的 最左边（最大位） 开始, 适用于位数多的序列，可采用计数排序 > 在进行某个特定位数比较时，要用稳定排序，将上次排序成果保留。例如十位数的排序过程能保留个位数的排序成果，百位数的排序过程能保留十位数的排序成果。 > 基数排序对有负数和0的数列难以进行排序   ```cpp void radixSort(vector<int>& nums) { int maxVal = 0; for (int x : nums) if (x > maxVal) maxVal = x; // d 表示 1，10，100 等，序列最大值长度为3，d = 100 int d = 10; while (maxVal / 10) { d *= 10; maxVal /= 10; } // 从个位开始 int index = 1; while (index<d) { // 从0到9总共10个桶 // 每个桶最多有 nums.size()个元素，初始化大小后才能使用 [] // 如何要使用 push_back() 就不要初始化大小，因为再 push_back() 则会将元素保存在初始化大小的元素之后！！！ // 同时放于此处可以不用清空数组，当更换数位时 vector<vector<int>> bucketVec(10, vector<int>()); //将序列的每个数字放在相应的桶里 for (int x : nums) { // 当前位上的数值 int digit = (x / index) % 10; bucketVec[digit].push_back(x); } // 重写入数组时遍历秩，当下一轮位数变化时，k 能自己重置为 0 int k = 0; // 将上一次排序结果覆盖到原数组 for (int i = 0; i < 10; i++) { // 若桶内有元素，依次取出放到原数组中 if (bucketVec[i].size()!=0) { for (int j = 0; j < bucketVec[i].size(); ++j) nums[k++] = bucketVec[i][j]; } } // 将位数前移 index *= 10; } } ``` ## 参数 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | :----------------: | :----------------: | :----------------: | :----------: | :------: | | $O(n*k)$ | $O(n*k)$ | $O(n*k)$ | $O(n+k)$ | 稳定 | 最后修改：2023 年 03 月 27 日 10 : 27 PM © 允许规范转载 赞赏 如果觉得我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付