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

数据结构笔记--十大经典排序算法（C++）_数据结构-十大经典排序算法

作者：小舞很执着 | 2024-08-11 21:10:41

赞

踩

数据结构-十大经典排序算法

目录

1--概述

2--冒泡排序

3--选择排序

4--插入排序

5--希尔排序

6--快速排序

7--归并排序

8--堆排序

9--计数排序

10--基数排序

11--桶排序

1--概述

        十大经典排序算法包括：冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序、计数排序、基数排序 和 桶排序；

2--冒泡排序

主要思想：视频讲解参考

        每次将最大的元素移动到最后；

        时间复杂度为 O (n^2)；

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. class Solution{
  6. public:
  7.     // 冒泡排序
  8.     void bubSort(std::vector<int> &input){
  9.         int len = input.size();
  10.         while(--len){ // len 一开始指向最后一个元素
  11.             for(int i = 0; i < len; i++){
  12.                 if(input[i] > input[i + 1]){
  13.                     int tmp = input[i];
  14.                     input[i] = input[i + 1];
  15.                     input[i + 1] = tmp;
  16.                 }
  17.             }
  18.         }
  19.     }
  20.     // 优化的冒泡排序
  21.     void Better_bubSort(std::vector<int> &input){
  22.         int len = input.size();
  23.         int flag = 1;
  24.         while(--len && flag){ // 当前面的已有序，即上一轮没有发生交换，就不会进入循环体
  25.             flag = 0;
  26.             for(int i = 0; i < len; i++){
  27.                 if(input[i] > input[i + 1]){
  28.                     flag = 1;
  29.                     int tmp = input[i];
  30.                     input[i] = input[i + 1];
  31.                     input[i + 1] = tmp;
  32.                 }
  33.             }
  34.         }
  35.     }
  36.     // 打印函数
  37.     void Print(const std::vector<int>& input){
  38.         for(int item : input){
  39.             std::cout << item << " ";
  40.         }
  41.         std::cout << std::endl;
  42.     }
  43. };
  44.  
  45. int main(int argc, char *argv[]){
  46.     std::vector<int> input = {1, 3, 6, 4, 2, 5};
  47.     Solution S1;
  48.     std::cout << "Before Sort: " << std::endl;
  49.     S1.Print(input);
  50.     std::cout << "After Sort: " << std::endl;
  51.     S1.bubSort(input);
  52.     S1.Print(input);
  53.     return 0;
  54. }

3--选择排序

主要思想：视频讲解参考

        选择排序基于冒泡排序的思想，每一轮找到最小值（用 k 指向），将最小值与循环的第一个数（用 i 指向）交换，这样可以确保每一轮将最小值选择排序到前面；

        时间复杂度为 O (n^2)；

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. class Solution{
  6. public:
  7.     // 选择排序
  8.     void selectSort(std::vector<int>& input){
  9.         int len = input.size();
  10.         int k = 0; // 指向本次循环最小值的位置
  11.         for(int i = 0; i < len; i++){
  12.             k = i;
  13.             for(int j = i + 1; j < len; j++){
  14.                 if(input[j] < input[k]) k = j; // 更新本次循环最小值的位置
  15.             }
  16.             int tmp = input[i];
  17.             input[i] = input[k]; // 最小值的位置移动到前面
  18.             input[k] = tmp;
  19.         }
  20.     }
  21.     // 打印函数
  22.     void Print(const std::vector<int>& input){
  23.         for(int item : input){
  24.             std::cout << item << " ";
  25.         }
  26.         std::cout << std::endl;
  27.     }
  28. };
  29.  
  30. int main(int argc, char *argv[]){
  31.     std::vector<int> input = {1, 3, 6, 4, 2, 5};
  32.     Solution S1;
  33.     std::cout << "Before Sort: " << std::endl;
  34.     S1.Print(input);
  35.     std::cout << "After Sort: " << std::endl;
  36.     S1.selectSort(input);
  37.     S1.Print(input);
  38.     return 0;
  39. }

4--插入排序

主要思想：视频讲解参考

        遍历每一个元素，将其插入到前面已经排好序的序列中，即与前面的数逐一比较，直到找到比其小的数，将元素插入到其后面；

        时间复杂度为 O (n^2)；

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. class Solution{
  6. public:
  7.     // 插入排序
  8.     void insertSort(std::vector<int>& input){
  9.         int len = input.size();
  10.         int key; // key表示本次循环中要插入的值
  11.         for(int i = 1; i < len; i++){ // i 从 1 开始，因为input[0]已经是有序的
  12.             key = input[i];
  13.             int j = i-1; // 从前一个数开始比较
  14.             while(j >= 0 && key < input[j]){ // 向前寻找，直到找到第一个比 key 小的数
  15.                 input[j+1] = input[j]; // 比较过的元素向后移动，因为要空出一个位置
  16.                 j--; // 继续向前寻找
  17.             }
  18.             input[j+1] = key; // 将 key 插入到第一个比它小的数的后面
  19.         }
  20.     }
  21.     // 打印函数
  22.     void Print(const std::vector<int>& input){
  23.         for(int item : input){
  24.             std::cout << item << " ";
  25.         }
  26.         std::cout << std::endl;
  27.     }
  28. };
  29.  
  30. int main(int argc, char *argv[]){
  31.     std::vector<int> input = {1, 3, 6, 4, 2, 5};
  32.     Solution S1;
  33.     std::cout << "Before Sort: " << std::endl;
  34.     S1.Print(input);
  35.     std::cout << "After Sort: " << std::endl;
  36.     S1.insertSort(input);
  37.     S1.Print(input);
  38.     return 0;
  39. }

5--希尔排序

主要思想：视频讲解参考

        希尔排序是插入排序的进阶版，实质上是使用多次插入排序，只是每次插入比较的步长是step，当 step 为1时，希尔排序就退化为普通的插入排序；

        希尔排序主要应用在数据量很大的排序问题中，本质上是减少交换的次数，因为当 step 退化为 1 时，序列已经大部分是有序的，所以交换的次数很少。

        希尔排序的时间复杂度为：O(n^(1.3--2))，是一种不稳定的排序；

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. class Solution{
  6. public:
  7.     // 希尔排序
  8.     void shellSort(std::vector<int>& input){
  9.         int len = input.size();
  10.         //初始比较的 step 为 len/2，每一轮退化为 step/2;
  11.         for(int step = len / 2; step > 0; step = step / 2){
  12.             // 每一轮使用插入排序
  13.             for(int i = step; i < len; i++){
  14.                 int key = input[i]; // 要插入的数
  15.                 int j = i - step; // 与前一个数进行比较
  16.                 while(j >= 0 && key < input[j]){
  17.                     input[j + step] = input[j]; 
  18.                     j = j - step; // 不断前移
  19.                 }
  20.                 input[j + step] = key;
  21.             } 
  22.         }
  23.     }
  24.     // 打印函数
  25.     void Print(const std::vector<int>& input){
  26.         for(int item : input){
  27.             std::cout << item << " ";
  28.         }
  29.         std::cout << std::endl;
  30.     }
  31. };
  32.  
  33. int main(int argc, char *argv[]){
  34.     std::vector<int> input = {1, 3, 6, 4, 2, 5};
  35.     Solution S1;
  36.     std::cout << "Before Sort: " << std::endl;
  37.     S1.Print(input);
  38.     std::cout << "After Sort: " << std::endl;
  39.     S1.shellSort(input);
  40.     S1.Print(input);
  41.     return 0;
  42. }

6--快速排序

主要思路：

        每次选定一个基准轴元素 (pivot)，从两边开始扫描，比 pivot 小的元素放在轴的左边，比 pivot 大的元素放在轴的右边；

        经过一次遍历之后，pivot 左边的元素都比 pivot 小，pivot 右边的元素都比 pivot 大，这样对于最终的结果来说，pivot 所在的位置是排好序的，只需递归排序 pivot 左边的元素和右边的元素即可；

        快速排序的时间复杂度为：O(nlogn) ~ O(n^2)

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. class Solution{
  6. public:
  7.     // 快速排序
  8.     void quickSort(std::vector<int>& input, int left, int right){
  9.         if(left >= right) return; // 递归结束条件
  10.         int len = input.size();
  11.         int pivot = input[left]; // 记录基准轴元素
  12.         int i = left, j = right;
  13.         while(i < j){
  14.             while(i < j && input[j] >= pivot) j--; // 从右往左扫描直到找到第一个比 pivot 小的元素停下
  15.             input[i] = input[j]; // 将小的数放到 pivot 的左边
  16.             while(i < j && input[i] <= pivot) i++; // 从左往右扫描直到找到第一个比 pivot 大的元素停下
  17.             input[j] = input[i]; // 将大的数放到 pivot 的右边
  18.         }
  19.         // 一趟遍历之后，将基准元素 pivot 放在 i 的位置（i == j）
  20.         input[i] = pivot;
  21.         // 递归排序pivot左边的元素和右边的元素
  22.         quickSort(input, left, i - 1);
  23.         quickSort(input, i+1, right);
  24.     }
  25.     // 打印函数
  26.     void Print(const std::vector<int>& input){
  27.         for(int item : input){
  28.             std::cout << item << " ";
  29.         }
  30.         std::cout << std::endl;
  31.     }
  32. };
  33.  
  34. int main(int argc, char *argv[]){
  35.     std::vector<int> input = {1, 3, 6, 4, 2, 5};
  36.     Solution S1;
  37.     std::cout << "Before Sort: " << std::endl;
  38.     S1.Print(input);
  39.     std::cout << "After Sort: " << std::endl;
  40.     S1.quickSort(input, 0, input.size()-1);
  41.     S1.Print(input);
  42.     return 0;
  43. }

7--归并排序

        普通归并排序将两个有序的序列归并为一个有序的新序列；视频讲解

  1. #include <iostream>
  2. #include <vector>   
  3.  
  4. class Solution{
  5. public:
  6.     std::vector<int> mergeSort(std::vector<int> input1, std::vector<int> input2){
  7.         std::vector<int> Res;
  8.         int i = 0, j = 0;
  9.         while(i < input1.size() && j < input2.size()){
  10.             if(input1[i] < input2[j]){
  11.                 Res.push_back(input1[i]);
  12.                 i++;
  13.             }
  14.             else{
  15.                 Res.push_back(input2[j]);
  16.                 j++;
  17.             }
  18.         }
  19.         while(i < input1.size()){
  20.             Res.push_back(input1[i]);
  21.             i++;
  22.         } 
  23.         while(j < input2.size()){
  24.             Res.push_back(input2[j]);
  25.             j++;
  26.         }
  27.         return Res;
  28.     }
  29.  
  30.     // 打印函数
  31.     void Print(const std::vector<int>& input){
  32.         for(int item : input){
  33.             std::cout << item << " ";
  34.         }
  35.         std::cout << std::endl;
  36.     }
  37. };
  38.  
  39. int main(int argc, char *argv[]){
  40.     std::vector<int> input1 = {1, 3, 4, 6};
  41.     std::vector<int> input2 = {2, 5, 7, 8};
  42.     Solution S1;
  43.     std::cout << "Before Sort: " << std::endl;
  44.     S1.Print(input1);
  45.     S1.Print(input2);
  46.     std::cout << "After Sort: " << std::endl;
  47.     std::vector<int> output = S1.mergeSort(input1, input2);
  48.     S1.Print(output);
  49.     return 0;
  50. }

        进阶归并排序将一个无序的序列归并排序为一个有序的系列；通过递归将无序的序列二分，从底层开始将二分的序列归并排序为有序序列；

  1. #include <iostream>
  2. #include <vector>   
  3.  
  4. class Solution{
  5. public:
  6.     // 归并排序
  7.     std::vector<int> mergeSort(std::vector<int> input){
  8.         std::vector<int> Res = split(input, 0, input.size() - 1);
  9.         return Res;
  10.     }
  11.  
  12.     // 二分序列
  13.     std::vector<int> split(std::vector<int> input, int left, int right){
  14.         if(left == right){ // 只剩下一个元素，返回由该元素构成的有序序列
  15.             std::vector<int> Res = {input[left]};
  16.             return Res;
  17.         }
  18.         int mid = left + (right - left) / 2;
  19.         std::vector<int> input1 = split(input, left, mid);
  20.         std::vector<int> input2 = split(input, mid+1, right);
  21.         std::vector<int> Res = merge(input1, input2); // 二分至底层，进行归并排序再回溯
  22.         return Res;
  23.     }
  24.  
  25.     // 将两个有序的序列归并排序
  26.     std::vector<int> merge(std::vector<int> input1, std::vector<int> input2){
  27.         std::vector<int> Res;
  28.         int i = 0, j = 0; 
  29.         while(i < input1.size() && j < input2.size()){
  30.             if(input1[i] < input2[j]){
  31.                 Res.push_back(input1[i]);
  32.                 i++;
  33.             }
  34.             else{
  35.                 Res.push_back(input2[j]);
  36.                 j++;
  37.             }
  38.         }
  39.         while(i < input1.size()){
  40.             Res.push_back(input1[i]);
  41.             i++;
  42.         }
  43.         while(j < input2.size()){
  44.             Res.push_back(input2[j]);
  45.             j++;
  46.         }
  47.         return Res;
  48.     }
  49.  
  50.     // 打印函数
  51.     void Print(const std::vector<int>& input){
  52.         for(int item : input){
  53.             std::cout << item << " ";
  54.         }
  55.         std::cout << std::endl;
  56.     }
  57. };
  58.  
  59. int main(int argc, char *argv[]){
  60.     std::vector<int> input = {1, 4, 6, 3, 5, 2, 8, 7, 10, 9, 11, 12};
  61.  
  62.     Solution S1;
  63.     std::cout << "Before Sort: " << std::endl;
  64.     S1.Print(input);
  65.     std::cout << "After Sort: " << std::endl;
  66.     std::vector<int> output = S1.mergeSort(input);
  67.     S1.Print(output);
  68.     return 0;
  69. }

8--堆排序

关于堆的知识：从堆的定义到优先队列、堆排序（强烈推荐）

堆排序基本知识：视频讲解参考

        ① 堆排序中的堆分为大根堆和小根堆，小根堆中孩子结点的值必须大于父亲结点的值（即堆顶是最小值），大根堆中孩子结点的值必须小于父亲结点的值（即堆顶是最大值）；

        ② 大根堆和小根堆本质上是一个完全二叉树，满足以下性质：结点连续存储，假设结点从0开始编号，则左孩子的位置为 2*parent + 1，右孩子的位置为 2*parent + 2；

        ③ （外堆且基于小顶堆）堆排序本质上分为入堆和出堆两步：

        入堆时新加入结点，结点需要自底向上与父亲结点进行比较，重构大根堆和小根堆，确保满足上面的性质；

        出堆时返回堆顶元素，并将最后一个元素放在堆顶位置，自顶向下与较小的孩子结点进行比较，重构大根堆和小根堆，确保满足上面的性质；

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. class Solution{
  6. public:
  7.     void heapSort(std::vector<int>& input){
  8.         int size = input.size();
  9.         // 入堆
  10.         for(int data : input){
  11.             pushHeap(data);
  12.         }
  13.         // 出堆
  14.         for(int i = 0; i < size; i++){
  15.             input[i] = popheap();
  16.         }
  17.     }
  18.  
  19.     // 入堆
  20.     void pushHeap(int data){
  21.         if(len == 0){
  22.             heap.push_back(data); // 入堆
  23.             len++;
  24.             return;  
  25.         }
  26.  
  27.         heap.push_back(data); // 入堆
  28.         len++; // 元素个数 +1
  29.  
  30.         // 重新排序堆
  31.         int cur = len - 1; // 当前堆中最后一个元素的位置
  32.         int parent = (cur-1) / 2; // 父亲节点的位置
  33.         while(parent != cur){ // 直到根节点
  34.             if(heap[cur] < heap[parent]){
  35.                 swap(cur, parent); // 交换两个位置的值
  36.                 cur = parent;
  37.                 parent = (cur-1) / 2; // 从下往上比较，不断交换
  38.             }
  39.             else break;
  40.         }
  41.     }
  42.  
  43.     // 出堆
  44.     int popheap(){
  45.         int res = heap[0]; // 堆顶元素
  46.         int cur = len - 1; // 最后一个元素的位置
  47.         heap[0] = heap[cur]; // 最后一个元素的位置放到堆顶中
  48.         len--; // 堆中元素 -1
  49.         // 重新排序堆
  50.         int start = 0;
  51.         while(start <= len){ // 从根节点开始排序
  52.             int l_child = 2*start+1;
  53.             int r_child = 2*start+2;
  54.             if(l_child > len || r_child > len) break; // 防止溢出
  55.             int small = heap[l_child] < heap[r_child] ? l_child : r_child; // 较小的孩子
  56.     
  57.             if (heap[small] < heap[start]){ // 从上到下与较小的孩子交换位置
  58.                 swap(small, start);
  59.                 start = small;
  60.             }
  61.             else break;
  62.         }
  63.         return res;
  64.     }
  65.  
  66.     void swap(int index1, int index2){
  67.         int temp = heap[index1];
  68.         heap[index1] = heap[index2];
  69.         heap[index2] = temp;
  70.     }
  71.  
  72.     // 打印函数
  73.     void Print(const std::vector<int>& input){
  74.         for(int item : input){
  75.             std::cout << item << " ";
  76.         }
  77.         std::cout << std::endl;
  78.     }
  79.  
  80. private:
  81.     std::vector<int> heap; // 小顶堆
  82.     int len = 0; // 堆中元素的个数
  83. };
  84.  
  85. int main(int argc, char *argv[]){
  86.     std::vector<int> input = {1, 3, 6, 4, 2, 5, 8, 7, 10, 9};
  87.     Solution S1;
  88.     std::cout << "Before Sort: " << std::endl;
  89.     S1.Print(input);
  90.     std::cout << "After Sort: " << std::endl;
  91.     S1.heapSort(input);
  92.     S1.Print(input);
  93.     return 0;
  94. }

9--计数排序

        在计数排序中，用一个数组的下标表示原数组的真值，数组下标对应的值表示真值出现的次数；遍历记录的数组，当下标对应的值不为0时，输入其下标（值多大就输出多少次）；

        在 C++ 中可以通过哈希表的形式来实现计数排序，key 表示原数组的真值，value 表示真值出现的次数；

        经典利用数组实现计数排序可以参考视频讲解

  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4.  
  5. class Solution{
  6. public:
  7.     std::vector<int> countSort(std::vector<int> input){
  8.         for(int item : input){ // 遍历每一个数
  9.             M.insert(std::pair<int, int>(item, M.count(item)+1));
  10.         }
  11.         for(auto item : M){ // map自动根据key排好序了，因此直接遍历即可
  12.             int num = item.second; // 出现的次数
  13.             while(num != 0){
  14.                 Res.push_back(item.first);
  15.                 num--;
  16.             } 
  17.         }
  18.         return Res;
  19.     }
  20.  
  21.     // 打印函数
  22.     void Print(const std::vector<int>& input){
  23.         for(int item : input){
  24.             std::cout << item << " ";
  25.         }
  26.         std::cout << std::endl;
  27.     }
  28.  
  29. private:
  30.     std::map<int, int> M; // <真值，出现的次数>
  31.     std::vector<int> Res;
  32. };
  33.  
  34. int main(int argc, char *argv[]){
  35.     std::vector<int> input = {1, 3, 6, 4, 2, 5, 8, 7, 10, 9};
  36.     Solution S1;
  37.     std::cout << "Before Sort: " << std::endl;
  38.     S1.Print(input);
  39.     std::cout << "After Sort: " << std::endl;
  40.     std::vector<int> output = S1.countSort(input);
  41.     S1.Print(output);
  42.     return 0;
  43. }

10--基数排序

        在基数排序中，对每一个数依次按照个位、十位、百位 ... 来排序，对最高位排序后即为有序结果，返回即可；

11--桶排序

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

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

  

闽ICP备14008679号