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 赞赏作者 扫一扫支付