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

数据结构—八种排序算法_数据结构排序方法

作者：知新_RL | 2024-02-29 05:15:54

赞

踩

数据结构排序方法

目录

稳定性：

一、冒泡排序

        概念：

        特点：

        复杂度：

        代码演示：

二、选择排序

        概念：

        特点：

        复杂度：

        代码演示：

三、插入排序

        概念：

        特点：

        复杂度：

        代码演示：

四、希尔排序

        概念：

        特点：

        复杂度：

        代码演示：

五、归并排序

        概念：

        特点：

        复杂度：

        代码演示：

六、快速排序

        概念：

        特点：

        复杂度：

        代码演示：

七、基数排序

        概念：

        特点：

        复杂度：

        代码演示：

八、堆排序

        概念：

        特点：

        复杂度：

        代码演示：

稳定性：

        在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序后，这些记录的相对次序保持不变，则称该排序算法是稳定的。

        例如：数组a  =  {1, 2, 3, 4, 1}，经过排序后为{1, 1, 2, 3, 4}。若第一个1为原先下标为0，第二个1为原先下标为4，则该排序算法是稳定的；若第一个1为原先下标为4，第二个1为原先下标为0，则该排序算法是不稳定的。

        稳定性的排序算法有：冒泡排序，插入排序、归并排序、基数排序。

        不稳定的排序算法有：选择排序、希尔排序、快速排序、堆排序。

以下排序默认为从小到大排序

一、冒泡排序

        概念：

        冒泡排序通过不断比较两个相邻的元素，若前一个元素较大则交换，重复（n-i-1）次为1轮（i表示第i轮，从0开始），重复（n-1）轮后排序完成（最后一轮只有一个元素，所以不用比较）。较小的元素会经由交换慢慢“浮”到数列的前端。

        特点：

        ①冒泡排序是稳定的排序方法②每次比较只比较相邻的两个元素。③每交换一轮就会将一个最大的元素置于数组的最后，即每经过一轮比较，需要比较的元素减一。通俗点说就是每进行一轮就会将当前数组中最大的元素放最后，之后要比较的数组元素减一。

        复杂度：

        时间复杂度O（N²）。空间复杂度O（1）。

        代码演示：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void bubble_sort(int a[], int n) {     //传入数组，数组长度
  5.     for (int i = 0; i < (n-1); i++) {       //总共会进行n轮
  6.         for (int j = 0; j < (n - i - 1); j++) {   //一轮会比较n-i-1次(还要减去1防止越界）
  7.             if (a[j] > a[j + 1]) {
  8.                 int temp = a[j];
  9.                 a[j] = a[j + 1];
  10.                 a[j + 1] = temp;
  11.             }
  12.         }
  13.     }
  14. }
  15.  
  16. int main()
  17. {
  18.     int a[] = { 2, 5, 6, 8, 2, 4, 3 };
  19.     for (int i : a) { cout << i << " "; }
  20.     cout << endl;
  21.  
  22.     bubble_sort(a, sizeof(a) / sizeof(a[0]));
  23.  
  24.     for (int i : a) { cout << i << " "; }
  25.     cout << endl;
  26.  
  27.     return 0;
  28. }

二、选择排序

        概念：

        找出数组中未排序部分的最小值下标，然后将其与未排序部分的首元素交换，重复n-1次即可。

        特点：

        ①选择排序是不稳定排序。②每排序一次都会将未排序数组的最小值放到最前，即每次排序后，最前面的是元素都比后面小。

        复杂度：

        时间复杂度O（n²），空间复杂度O（1）。

        代码演示：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void selection_sort(int a[], int n) {
  5.     for (int i = 0; i < (n - 1); i++) {      //总共查找n-1次最小值
  6.         int t = i;      //当前的最小值下标
  7.         for (int j = i + 1; j < n; j++) {  //寻找未排序部分的最小值下标。
  8.             if (a[j] < a[t]) {
  9.                 t = j;
  10.             }
  11.         }
  12.         if (t != i) {           //如果第a[i]不是当前最小的
  13.             int temp = a[i];
  14.             a[i] = a[t];
  15.             a[t] = temp;
  16.         }
  17.     }
  18. }
  19.  
  20. int main()
  21. {
  22.     int a[] = { 5, 2, 4, 6, 8, 6, 4 };
  23.     for (int i : a) { cout << i << " "; }
  24.     cout << endl;
  25.  
  26.     selection_sort(a, sizeof(a) / sizeof(a[0]));
  27.  
  28.     for (int i : a) { cout << i << " "; }
  29.     cout << endl;
  30.  
  31.     return 0;
  32. }

三、插入排序

        概念：

        将一个元素插入到已经排好序的有序表中，从而得到一个新的、元素数增1的有序表。

        特点：

        ①插入排序是稳定的②进行 k次排序后前k+1个元素是有序的。

        复杂度：

        时间复杂度O（n²）， 空间复杂度O（1）。

        代码演示：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void snsertion_sort(int a[], int n) {
  5.     for (int i = 1; i < n; i++) {    //默认第一个元素a[0]是排好序的，所以从1开始
  6.         int t = i;   //待插入元素的位置
  7.         for (int j = i - 1; j >= 0; j--) {  //注意是从后往前比较，所以是j--
  8.             if (a[t] < a[j]) {
  9.                 int temp = a[t];
  10.                 a[t] = a[j];
  11.                 a[j] = temp;
  12.                 t = j;                //注意哦，下标也要变化
  13.             }
  14.             else {
  15.                 break;
  16.             }
  17.         }
  18.     }
  19. }
  20.  
  21. int main()
  22. {
  23.     int a[] = { 5, 2, 4, 6, 8, 6, 4 };
  24.     for (int i : a) { cout << i << " "; }
  25.     cout << endl;
  26.  
  27.     snsertion_sort(a, sizeof(a) / sizeof(a[0]));
  28.  
  29.     for (int i : a) { cout << i << " "; }
  30.     cout << endl;
  31.  
  32.     return 0;
  33. }

四、希尔排序

        概念：

        希尔排序基于插入排序改进，先取一个小于n的整数d1作为第一个增量（一般是n/2），把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行插入排序，然后，取第二个增量d2（一般取d1的一半），重复以上步骤直到增量为1进行最后一次插入排序。

        特点：

        ①希尔排序是不稳定的②每次排序都会将增量为d的元素排好序。

        复杂度：

        时间复杂度为O（nlog2n），空间复杂度为O（1）。

        代码演示：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void shells_sort(int a[], int n) {
  5.     int d = n / 2;
  6.     while (d) {     //当d不为0时进行排序
  7.         for (int i = 0; i < d; i++) {    //分成d组
  8.             for (int j = i + d; j < n; j += d) {    //对每一组进行插入排序
  9.                 int t = j;
  10.                 for (int k = j - d; j >= i; j -= d) {
  11.                     if (a[t] < a[k]) {
  12.                         int temp = a[t];
  13.                         a[t] = a[k];
  14.                         a[k] = temp;
  15.                         t = k;
  16.                     }
  17.                     else {
  18.                         break;
  19.                     }
  20.                 }
  21.             }
  22.         }
  23.         d /= 2;
  24.     }
  25. }
  26.  
  27.  
  28. int main()
  29. {
  30.     int a[] = { 5, 2, 4, 6, 8, 6, 4 };
  31.     for (int i : a) { cout << i << " "; }
  32.     cout << endl;
  33.  
  34.     shells_sort(a, sizeof(a) / sizeof(a[0]));
  35.  
  36.     for (int i : a) { cout << i << " "; }
  37.     cout << endl;
  38.  
  39.     return 0;
  40. }

五、归并排序

        概念：

       先将数组不断二分出子数组直到每个子数组的元素数目均为1，此时每个子数组都是有序的，然后两两合并有序的子数组，重复该合并步骤。（合并方式为：比较两个子数组的首个元素，将小的放进新的空间中，然后重复这一步骤）

        特点：

        ①归并排序是稳定的②每一次合并都会合并2的倍数个有序元素。即第i次合并后每2的i次方个元素是有序的。

        复杂度：

        时间复杂度O（nlogn），空间复杂度O（n）

        代码演示：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void merge(int a[], int left, int middle, int right) {
  5.     int* b = new int[right - left + 1];     //创建一个数组b用来接收有序数组
  6.     int i = left, j = middle + 1;
  7.     int k = 0;
  8.     for (; (i <= middle) && (j <= right); ) {  //将小的元素按序存入直到一个子数组全存入
  9.         if (a[i] <= a[j]) {     //这里要用小于等于，不然可能会变成不稳定的排序
  10.             b[k++] = a[i++];
  11.         }
  12.         else {
  13.             b[k++] = a[j++];
  14.         }
  15.     }
  16.     if (i > middle) {    //将剩余的也按序存入
  17.         for (; j <= right; j++) { b[k++] = a[j]; }
  18.     }
  19.     else {
  20.         for (; i <= middle; i++) { b[k++] = a[i]; }
  21.     }
  22.     for (int i = left; i <= right; i++) { a[i] = b[i-left]; }     //赋值回数组a
  23.     delete[]b;  //new完先delete
  24. }
  25.  
  26. void merge_sort(int a[], int left, int right) {   //归并排序,参数为数组，数组下标的最小值和最大值。
  27.     if (right <= left) { return; }  //当子数组长度为1时停止二分。
  28.     int middle = (left + right) / 2;
  29.     //先将数组不断二分
  30.     merge_sort(a, left,  middle);
  31.     merge_sort(a, middle+1, right);
  32.     //合并二分后的有序数组。
  33.     merge(a, left, middle, right);
  34. }
  35.  
  36.  
  37. int main()
  38. {
  39.     int a[] = { 5, 2, 4, 6, 8, 6, 4 };
  40.     for (int i : a) { cout << i << " "; }
  41.     cout << endl;
  42.  
  43.     merge_sort(a, 0, sizeof(a) / sizeof(a[0])-1);  //注意，是下标值，所以要减一
  44.  
  45.     for (int i : a) { cout << i << " "; }
  46.     cout << endl;
  47.  
  48.     return 0;
  49. }

六、快速排序

        概念：

        先设置一个分界值（通常是第一个元素），将数组分为小于分界值和大于分界值两部分，重复这一步骤。

        特点：

        ①快速排序是一个不稳定排序②每排序一次，分界值左边的值都小于分界值，右边的值都大于分界值。

        复杂度：

        时间复杂度为O（nlog2n），空间复杂度为O（log2n）

        代码演示：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void swap(int a[], int l, int r) {
  5.     int temp = a[l];
  6.     a[l] = a[r];
  7.     a[r] = temp;   
  8. }
  9.  
  10. void quick_sort(int a[], int left, int right) {
  11.     if (left >= right) { return; }
  12.     int l = left, r = right, t = left;
  13.     while (l < r) {
  14.         while (a[r] >= a[t]) { r--; }
  15.         if (r > l) { swap(a, t, r); t = r; }
  16.         else { break; }
  17.         while (a[l] <= a[t]) { l++; }
  18.         if (l < r) { swap(a, t, l); t = l; }
  19.     }
  20.     quick_sort(a, left, t - 1);
  21.     quick_sort(a, t+1, right);
  22. }
  23.  
  24. int main()
  25. {
  26.     int a[] = { 5, 2, 4, 6, 8, 6, 4 };
  27.     for (int i : a) { cout << i << " "; }
  28.     cout << endl;
  29.  
  30.     quick_sort(a, 0, sizeof(a) / sizeof(a[0])-1);  //注意，是下标值，所以要减一
  31.  
  32.     for (int i : a) { cout << i << " "; }
  33.     cout << endl;
  34.  
  35.     return 0;
  36. }

七、基数排序

        概念：

        先创建一个10个桶（编号从0到9）（可以是二维的动态数组），然后将数组中的元素按个位数的大小放入对应的桶中（这算第零轮）。找出数组中最大的位数k，重复以下操作k-1次：按顺序取出桶中元素（先取出编号为0的桶的所有元素，再取出为1的...），找出他们在该位数的数（第一轮就是十位数，第二轮就是百位数...）放入对应的新桶中（也是编号从0到9的10个桶）。重复完成后再遍历所有的桶，将值按序赋给数组。

        特点：

        ①基数排序是稳定的②每一轮的桶中都是按基数进行排序的。

        复杂度：

        时间复杂度O (nlog(r)m)，其中r为所采取的基数（桶的数量），而m为堆数（最大值的位数），空间复杂度O（n+m），m为桶的数量。

        代码演示：

  1. #include <iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. int maxbit(int a[], int n) {
  6.     int t = a[0], bit = 0;   //最大值与其位数
  7.     for (int i = 1; i < n; i++) {     //找出最大值
  8.         if (a[i] > t) { t = a[i]; }
  9.     }
  10.     while (t) {   //求位数
  11.         bit++;
  12.         t /= 10;
  13.     }
  14.     return bit;
  15. }
  16.  
  17. void radix_sort(int a[], int n) {
  18.     vector<vector<int> > v(10);       //其实用链表存更好，但我懒。注意，这里第一行全是0.
  19.     for (int i = 0; i < n; i++) {    //先进行一轮，之后就不用对a操作了
  20.         int yu = a[i] % 10;
  21.         v[yu].emplace_back(a[i]);      
  22.     }
  23.     int k = maxbit(a, n);       //先找出所有元素中最大值的位数
  24.     for (int i = 1; i < k; i++) {    //一共进行k轮（由于先进行了一轮，所以从1开始）
  25.         vector<vector<int> > v1(10);  
  26.         for (int i1 = 0; i1 < v[0].size(); i1++) { v1[0].emplace_back(v[0][i]); }
  27.         for (int j = 1; j < 10; j++) {   //对数组v遍历,不用对v【0】的数操作。
  28.             int m = v[j].size();
  29.             for (int u = 0; u < m; u++) {
  30.                 int t = (v[j][u] / (i * 10)) % 10;    //求余数
  31.                 v1[t].emplace_back(v[j][u]);
  32.             }
  33.         }
  34.         v = v1;
  35.     }
  36.     int tm = 0;
  37.     for (int i = 0; i < 10; i++) {
  38.         for (int j = 0; j < v[i].size(); j++) {
  39.             a[tm++] = v[i][j];
  40.         }
  41.     }
  42. }
  43.  
  44. int main()
  45. {
  46.     int a[] = { 5, 2, 24, 16, 8, 6, 4, 54};
  47.     for (int i : a) { cout << i << " "; }
  48.     cout << endl;
  49.  
  50.     radix_sort(a, sizeof(a) / sizeof(a[0]));  //注意，是下标值，所以要减一
  51.  
  52.     for (int i : a) { cout << i << " "; }
  53.     cout << endl;
  54.  
  55.     return 0;
  56. }

八、堆排序

        概念：

        利用堆的性质所设计的（大根（顶）堆：父节点的值大于子节点的值）。将待排序的数组构造成一个大根堆，将顶端的数与末尾的数交换，此时末尾的数为最大值，再将剩下的数重复以上步骤。（第i个节点的子节点是2i+1和2i+2）。

        特点：

        ①堆排序是不稳定的②没进行一次堆排序后，最大值会被换到最后，且除了a[0]和a[n-1]外，a[i] > max(a[2*i+1], a[2*i+2])。

        复杂度：

        时间复杂度O（nlogn），空间复杂度O（1）。其中建堆的时间复杂度是O(n),之后的排序时间复杂度是O(log n)。

        代码演示：

  1. #include <iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. void swap(int a[], int i, int j) {
  6.     int t = a[i];
  7.     a[i] = a[j];
  8.     a[j] = t;
  9. }
  10.  
  11. void maxhead_sort(int a[], int n) {  //升序，所以是大根（顶）堆
  12.     if (n <= 1) { return; }
  13.     for (int i = (n - 2) / 2; i >= 0; i--) {    //最后一个节点下标是（n-2）/2。
  14.         int t = 2 * i + 1;
  15.         if (t < n - 1) {
  16.             if (a[2 * i + 1] < a[2 * i + 2]) { t += 1; }
  17.         }
  18.         if (a[t] > a[i]) { swap(a, i, t); }
  19.     }
  20.     swap(a, 0, n - 1);  //将最大的数移到最后
  21.     maxhead_sort(a, n - 1);  //剩余的数继续
  22. }
  23.  
  24. int main()
  25. {
  26.     int a[] = { 5, 2, 24, 16, 8, 6, 4, 54 };
  27.     for (int i : a) { cout << i << " "; }
  28.     cout << endl;
  29.  
  30.     maxhead_sort(a, sizeof(a) / sizeof(a[0]));  //注意，是下标值，所以要减一
  31.  
  32.     for (int i : a) { cout << i << " "; }
  33.     cout << endl;
  34.  
  35.     return 0;
  36. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/163837
推荐阅读
相关标签

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

  

闽ICP备14008679号