devbox
天景科技苑
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

十大排序算法大总结C++实现_十大排序算法总结 c++

作者：天景科技苑 | 2024-08-01 08:14:02

赞

踩

十大排序算法总结 c++

最近为了熟悉经典的排序算法，我又进行了复习总结，实现过程全部由C++完成。代码结构清晰简洁，方便学习和复习，也是我们必须掌握的基础。

算法基本知识

什么是稳定排序、原地排序、时间复杂度、空间复杂度：

1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。

2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

4、非原地排序：需要利用额外的数组来辅助排序。

5、时间复杂度：一个算法执行所消耗的时间。

6、空间复杂度：运行完一个算法所需的内存大小

1、冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素，再进行交换。

  • 冒泡排序是稳定的
    • 如果两个元素相等，不会把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

算法过程

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2、选择排序

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给>二个元素选择第二小的，依次类推，直到第n-1个元素，第n个 元素不用选择了，因为只剩下它一个最大的元素了。

  • 选择排序是非稳定的
    • 在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么 交换后稳定性就被破坏了。

算法过程

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
  3. 以此类推，直到所有元素均排序完毕
  4. 时间负复杂度：O(n^2)，空间O（1），非稳定排序，原地排序

3、插入排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。

  • 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

算法过程

1.从第一个元素开始，该元素可以认为已经被排序

2.取出下一个元素，在已经排序的元素序列中从后向前扫描

3.如果该元素（已排序）大于新元素，将该元素移到下一位置

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5.将新元素插入到该位置后

4、快速排序

思路

1、选取第一个数为基准

2、将比基准小的数交换到前面，比基准大的数交换到后面

3、对左右区间重复第二步，直到各区间只有一个数

  • 我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。
  • 从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

5、希尔排序

希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。

  • 希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。

  • 希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

6、归并排序

将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。 通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 … 直到全部小的数组合并起来。

算法思想

1、把长度为n的输入序列分成两个长度为n/2的子序列；

2、对这两个子序列分别采用归并排序；

3、 将两个排序好的子序列合并成一个最终的排序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

7 堆排序

首先堆heap是一种数据结构，是一棵完全二叉树且满足性质：所有非叶子结点的值均不大于或均不小于其左、右孩子结点的值.

堆排序思想

  • 堆排序的基本思想是利用heap这种数据结构(可看成一个完全二叉树)，使在排序中比较的次数明显减少。

  • 堆排序的时间复杂度为O(n*log(n))， 非稳定排序，原地排序(空间复杂度O(1))。

  • 堆排序的关键在于建堆和调整堆，下面简单介绍一下建堆的过程：

第1趟将索引0至n-1处的全部数据建大顶(或小顶)堆，就可以选出这组数据的最大值(或最小值)。将该堆的根节点与这组数据的最后一个节点交换，就使的这组数据中最大(最小)值排在了最后。

第2趟将索引0至n-2处的全部数据建大顶(或小顶)堆，就可以选出这组数据的最大值(或最小值)。将该堆的根节点与这组数据的倒数第二个节点交换，就使的这组数据中最大(最小)值排在了倒数第2位。

…

第k趟将索引0至n-k处的全部数据建大顶(或小顶)堆，就可以选出这组数据的最大值(或最小值)。将该堆的根节点与这组数据的倒数第k个节点交换，就使的这组数据中最大(最小)值排在了倒数第k位。

  • 其实整个堆排序过程中, 我们只需重复做两件事：

建堆(初始化+调整堆, 时间复杂度为O(n));

拿堆的根节点和最后一个节点交换(siftdown, 时间复杂度为O(n*log n) ).

  • 因而堆排序整体的时间复杂度为O(n*log n).

8 计数排序(Count Sort)

        是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。

计数排序的思想是在给定的一组序列中，先找出该序列中的最大值和最小值，从而确定需要开辟多大的辅助空间，每一个数在对应的辅助空间中都有唯一的下标。

找出序列中最大值和最小值，开辟Max-Min+1的辅助空间
最小的数对应下标为0的位置，遇到一个数就给对应下标处的值+1,。
遍历一遍辅助空间，就可以得到有序的一组序列
 

9 .桶排序

基本思想
      桶排序的基本思想是假设数据在[min,max]之间均匀分布，其中min、max分别指数据中的最小值和最大值。那么将区间[min,max]等分成n份，这n个区间便称为n个桶。将数据加入对应的桶中，然后每个桶内单独排序。由于桶之间有大小关系，因此可以从大到小(或从小到大)将桶中元素放入到数组中。
 

10.基数排序

算法思想
        基数排序是一种非比较型整数排序算法，其原理是将众多数字按位分隔后进行排序。
实现步骤：
1.将所有待比较的数字（正整数）统一为同一长度，位数不够的数字前面补0；
2.按照从个位，十位，百位······从低到高的顺序进行排序
3.完成从低位到高位的排序后，待排序数字也就完成了排序

  1. #include <iostream>
  2. #include <vector> 
  3. #include <algorithm>
  4. #include <list>
  5. using namespace std;
  6.  
  7. vector<int> bubbleSort(vector<int>& nums) {
  8.   int size = nums.size();
  9.   bool flag = false;
  10.   for (int i = 0; i < size; ++i) {
  11.       flag = false;
  12.       for (int j = 0; j < size - i; ++j) {
  13.           if (nums[j] > nums[j + 1]) {
  14.               swap(nums[j], nums[j + 1]);
  15.               flag = true;
  16.           }
  17.       }
  18.       if (!flag) break;
  19.   }
  20.   return nums;
  21. }
  22.  
  23.  
  24. vector<int> selectSort(vector<int>& nums) {
  25.     int size = nums.size();
  26.     int index = 0;
  27.     for (int i = 0; i < size; ++i) {
  28.         index = i;
  29.         for (int j = i + 1; j < size; ++j) {
  30.             if (nums[j] < nums[index]) {
  31.                 index = j;
  32.             }
  33.         }
  34.         swap(nums[i], nums[index]);
  35.     }
  36.     return nums;
  37. }
  38.  
  39.  
  40. vector<int> insertSort(vector<int>& nums) {
  41.     int size = nums.size();
  42.     for (int i = 0; i < size; ++i) {
  43.         int temp = nums[i];
  44.         int j = i;
  45.         while (j > 0 && nums[j - 1] > temp) {
  46.             nums[j] = nums[j - 1];
  47.             j--;
  48.         }
  49.         nums[j] = temp;
  50.     }
  51.     return nums;
  52. }
  53.  
  54.  
  55. //quickSort with midValue
  56. int midValue(vector<int>& nums, int left, int right) {
  57.     int mid = left + (right - left) / 2;
  58.     if (nums[left] < nums[right]) {
  59.         if (nums[mid] > nums[right]) return right;
  60.         else if (nums[mid] < nums[left]) return left;
  61.         else return mid;
  62.     }
  63.     else {
  64.         if (nums[mid] > nums[left]) return left;
  65.         else if (nums[right] > nums[mid]) return right;
  66.         else return mid;
  67.     }
  68. }
  69.  
  70.  
  71. vector<int> quickSort(vector<int>& nums, int low, int high) {
  72.     if (low >= high) return nums; //递归一定要有结束标志
  73.     int mid = midValue(nums, low, high);
  74.     swap(nums[low], nums[mid]);
  75.     int first = low, last = high;
  76.     int key = nums[first];
  77.     while (first < last) {
  78.         while (first < last && nums[last] >= key) last--;
  79.         if (first < last) nums[first++] = nums[last];
  80.         while (first < last && nums[first] <= key) first++;
  81.         if (first < last) nums[last--] = nums[first];
  82.     }
  83.     nums[first] = key;
  84.     quickSort(nums, low, first - 1);
  85.     quickSort(nums, first + 1, high);
  86.     return nums;
  87. }
  88.  
  89.  
  90.  
  91. vector<int> adjust(vector<int>& nums, int start, int end) {
  92.     int dad = start;
  93.     int son = dad* 2 + 1;
  94.     while (son <= end) {
  95.         if (son + 1 <= end && nums[son] < nums[son + 1])
  96.             son++;
  97.         if (nums[dad] >= nums[son]) break;
  98.         else {
  99.             swap(nums[dad], nums[son]);
  100.             dad = son;
  101.             son = dad* 2 + 1;
  102.         }
  103.     }
  104.     return nums;
  105. }
  106.  
  107. vector<int> heapSort(vector<int>& nums, int size) {
  108.     for (int i = size / 2 - 1; i >= 0; --i) {
  109.         adjust(nums, i, size);
  110.     }
  111.     for (int i = size - 1; i >= 0; --i) {
  112.         swap(nums[i], nums[0]);
  113.         adjust(nums, 0, i - 1);
  114.     }
  115.     return nums;
  116. }
  117.  
  118.  
  119. vector<int> mergeSort(vector<int>& nums, vector<int>& temp, int start, int end) {
  120.     if (start >= end) return temp;
  121.     int low1 = start, high2 = end, mid = start + (end - start) / 2;
  122.     int high1 = mid, low2 = mid + 1;
  123.     mergeSort( temp, nums,low1, high1);
  124.     mergeSort( temp, nums,low2, high2);
  125.     int index = start; // 缓存数组下标
  126.     while (low1 <= high1 && low2 <= high2) {
  127.         temp[index++] = nums[low1] <= nums[low2] ? nums[low1++] : nums[low2++];
  128.     }
  129.     while (low1 <= high1) temp[index++] = nums[low1++];
  130.     while (low2 <= high2) temp[index++] = nums[low2++];
  131.     // for (index = start; index <= end; ++index) { 
  132.     //     nums[index] = temp[index];
  133.     // }
  134.     // for (auto a : nums)
  135.     //     cout << a << " ";
  136.     // cout << endl;
  137.     return temp;
  138. }
  139.  
  140.  
  141.  
  142.  
  143.  
  144. vector<int> shellSort(vector<int>& nums) {
  145.     int size = nums.size();
  146.     for (int gap = size / 2; gap > 0; gap /= 2) { // 注意gap > 0
  147.         for (int i = gap; i < size; ++i) {
  148.             int temp = nums[i];
  149.             int j = i - gap;
  150.         for (; j >= 0 && temp <= nums[j]; j -= gap) { // 注意j >= 0
  151.             nums[j + gap] = nums[j];
  152.         }
  153.         nums[j + gap] = temp;
  154.         }
  155.     }
  156.     return nums;
  157. }
  158.  
  159.  
  160. vector<int> countSort(vector<int>& nums, int maximal) { //计数排序要求元素能够作为数组的下标，自然不能是负数
  161.     int len = nums.size();
  162.     if (len < 1) return nums;
  163.     vector<int> count(maximal + 1, 0);
  164.     vector<int> temp(nums);
  165.     for (auto a : nums) {
  166.         count[a]++;
  167.     }
  168.     for (int i = 1; i <= maximal; ++i) {
  169.         count[i] += count[i - 1];
  170.     }
  171.     for (int i = len - 1; i >= 0; --i) {
  172.         nums[count[temp[i]] - 1] = temp[i];
  173.         count[temp[i]]--;
  174.     }
  175.     return nums;
  176. }
  177.  
  178.  
  179.  
  180. vector<int> bucketSort(vector<int>& nums, int len) {
  181.     // find the maximal value of array 
  182.     int max = nums[0];
  183.     int min = max;
  184.     for (int i = 0; i < len; ++i) {
  185.         if (nums[i] > max) max = nums[i];
  186.     }
  187.     for (int i = 0; i < len; ++i) {
  188.         if (nums[i] < min) min = nums[i];
  189.     }
  190.     
  191.     // get the count of bucket
  192.     int bucketCounts = (max - min) / len + 1;
  193.     vector<vector<int>> bucketArray(bucketCounts);
  194.     
  195.     // assign each value to bucket arrays.
  196.     
  197.     for (int i = 0; i < len; ++i) {
  198.         int num = (nums[i] - min) / len;
  199.         bucketArray[num].push_back(nums[i]);
  200.     }
  201.     
  202.     // sort each bucket
  203.     for (int i = 0; i < bucketCounts; ++i) {
  204.         sort(bucketArray[i].begin(), bucketArray[i].end());
  205.     }
  206.     // collect value from radix arrays to data
  207.     int index = 0;
  208.     for (int i = 0; i < bucketCounts; ++i) {
  209.         for (int j = 0; j < bucketArray[i].size(); ++j) {
  210.             nums[index++] = bucketArray[i][j];
  211.         }
  212.     }
  213.     return nums;
  214. }
  215. int my_max(vector<int>& nums, int n){
  216.     int temp = 1;
  217.     int d = 10;
  218.     for (int i = 0; i < n; i++){
  219.     if (nums[i]>d){
  220.         d *= 10;
  221.         temp++;
  222.   }
  223.  }
  224.  return temp;
  225. }
  226. vector<int> radixSort(vector<int>& nums, int n){
  227.     int max = my_max(nums, n);
  228.     list<int>my_list[10];
  229.     //最高位决定循环的次数！
  230.     for (int i = 0,d=1; i < max; i++,d*=10){
  231.     for (int j = 0; j < n; j++){
  232.     //核心算法以及注意是按照顺序从前往后插入的！
  233.         my_list[(nums[j] / d) % 10].push_back(nums[j]);
  234.     }
  235.     for (int k = 0,m=0; k < 10; k++){
  236.         while (!my_list[k].empty()){
  237.         //这里我们取出来的时候也是从前往后取出来，这样才是排好序的，同时不要忘记把桶清空呀！
  238.         nums[m++] = my_list[k].front();
  239.         my_list[k].pop_front();
  240.     }
  241.    }
  242.  }
  243.  return nums;
  244. }
  245.  
  246.  
  247. int main()
  248. {
  249.     vector<int> nums{2,4,3,6,5,9,7,1, 11, 16, 13};
  250.     vector<int> temp(nums);
  251.     int maximal = nums[0];
  252.     for (int i = 0; i < nums.size(); ++i) {
  253.         if (nums[i] > maximal) maximal = nums[i];
  254.     }
  255.     int len = nums.size();
  256.     vector<int> res;
  257.     //res = bubbleSort(nums);
  258.     //res = selectSort(nums);
  259.     //res = insertSort(nums);
  260.     //res = quickSort(nums, 0, nums.size() - 1);
  261.     //res = heapSort(nums,nums.size());
  262.     //res = mergeSort(nums, temp, 0, nums.size() - 1);
  263.     //res = shellSort(nums);
  264.     //res = countSort(nums, maximal);
  265.     //res = bucketSort(nums, len);
  266.     res = radixSort(nums, len);
  267.     for (auto a : res)
  268.         cout << a << " ";
  269.     
  270. }

注意：十个排序算法都已经测试过，其中需要注意的是由于计数排序需要元素作为下标，所有我给测试数据时候，都用的是正数。

优化：比如冒泡排序，我们可以采用flag判断如果已经有序，我们可以直接中断循环，节省时间；

比如快速排序，我们采用三个数每次都取最中间的数，这样的目的是让快排结果不会有最坏结果。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/913128
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号