分类导航
程序笔记程序问答

c++排序算法整理

程序笔记   发布时间：2022-07-12  发布网站：大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了c++排序算法整理，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

当然这些都是废话直接sort多好。。。

 1 //放眼望去。。。好眼熟啊。。。
 2 //当然身为神犇大佬的你不希望自己渺小到只会用sort。。。
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 const int MAXN = 1e8 + 10;
 6 int n, a[MAXN];
 7 int main(){
 8     scanf("%d", &n);
 9     for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
10     sort(a + 1, a + 1 + n);//<--!!!!!AC必备经典代码。。。。。
11     for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
12     return 0;

像上面这样简洁的代码难道不XIANG吗。。。（蒟蒻的心里话）

切入正题：@H_696_121@

十种常见排序算法可以分为两大类：@H_696_121@

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。 包括插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序和归并排序

非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。包括计数排序、桶排序和基数排序

算法时/空复杂度： 插入排序：平均时间复杂度O(n^2)，最坏时间复杂度O(n^2))，最好时间复杂度O(n)，空间复杂度O(1)希尔排序：平均时间复杂度O(n^1.3)，最坏时间复杂度O(n^2)，最好时间复杂度O(n)，空间复杂度O(1)选择排序：平均时间复杂度O(n^2)，最坏时间复杂度O(n^2)，最好时间复杂度O(n^2)，空间复杂度O(1)堆排序：平均时间复杂度O(n log2​ n)，最坏时间复杂度O(n log2 n)，最好时间复杂度O(n log2 n)，空间复杂度O(1)冒泡排序：平均时间复杂度O(n^2)，最坏时间复杂度O(n^2)，最好时间复杂度O(n)，空间复杂度O(1)快速排序：平均时间复杂度O(n log2​ n)，最坏时间复杂度O(n^2))，最好时间复杂度O(n log2​ n)，空间复杂度O(n log2​ n) 归并排序：平均时间复杂度O(n log2 ​n)，最坏时间复杂度O(n log2 ​n)，最好时间复杂度O(n log2​ n)，空间复杂度O(n) 计数排序：平均时间复杂度O(n+k)，最坏时间复杂度O(n+k)，最好时间复杂度)O(n+k)，空间复杂度O(n+k)   桶排序：平均时间复杂度O(n+k)，最坏时间复杂度O(n2)，最好时间复杂度O(n)，空间复杂度O(n+k) 基数排序：平均时间复杂度O(n×k)，最坏时间复杂度O(n×k)，最好时间复杂度O(n×k)，空间复杂度O(n+k) 

提前声明：如果有点懵可以看看最后面的链接🔗，有配动图详细解释。

高危预警⚠⚠⚠⚠⚠⚠⚠⚠⚠⚠

1、冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 

算法描述 1.比较相邻的元素。如果第一个比第二个大，就交换它们两个； 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 3.针对所有的元素重复以上的步骤，除了最后一个； 4.重复步骤1~3，直到排序完成。 总共要循环n-1次 

 

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 1e8 + 10;
 4 int a[MAXN], n;
 5 int main(){
 6     scanf("%d", &n);
 7     for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
 8     for (int i = n;i > 1; i--)
 9         for(int j = 1;j < i; j++)
10             if(a[j] > a[j + 1]) swap(a[j], a[j + 1]); //交换两个数
11     for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
12     return 0;
13 }

 

 

2、选择排序（SELEction Sort） 选择排序(SELEction-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 

 

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 1e8 + 10;
 4 int a[MAXN], n;
 5 int main(){
 6     scanf("%d", &n);
 7     for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
 8     for (int i = 1;i < n; i++) {
 9         int w = i, Min = a[i];
10         for (int j = i;j <= n; j++) if(Min > a[j]) w = j, Min = a[j]; //寻找🔎最小数和它的位置
11         swap(a[i], a[w]);
12     }
13     for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
14     return 0;
15 }

 

3、插入排序（Insertion Sort） 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 

 

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 1e8 + 10;
 4 int a[MAXN], n;
 5 int main(){
 6     scanf("%d", &n);
 7     for (int i = 1;i <= n; i++) {
 8         scanf("%d", &a[i]); int x = i - 1;
 9         while(a[x] > a[x + 1] && x > 0) swap(a[x], a[x + 1]), x--;
10     }
11     for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
12     return 0;
13 }

4、希尔排序（SHell Sort） 1959年SHell发明，第一个突破O(n^2)的排序算法（听起来挺厉害的。。。），是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。 

算法描述 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述： 

选择一个增量序列t1,t2,t3,.. . tk，其中ti>tj,tk=1； 按增量序列个数k，对序列进行k趟排序； 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为@H_806_133@m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。 参考代码来源

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 1e8 + 10;
 4 int n, a[MAXN];
 5 int main(){
 6     scanf("%d", &n);
 7     for (int i = 0;i < n; i++) scanf("%d", &a[i]);
 8     for (int step = n / 2; step > 0; step /= 2)
 9         for (int i = 0;i < step; i++)
10             for (int j = i + step;j < n; j += step)
11                 if(a[j] < a[j - step]) {
12                     int temp = a[j];
13                     int k = j - step;
14                     while (k >= 0 && temp < a[k]) {
15                         swap(a[k + step], a[k]);
16                         k -= step;
17                     }
18                 }
19     for (int i = 0;i < n; i++) printf("%d ", a[i]); puts("");
20     return 0;
21 }

 

5、归并排序（Merge Sort） 

 

归并排序是建立在归并操作上的一种有效的排序算法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 

 

算法描述 把长度为n的输入序列分成两个长度为n/2的子序列； 对这两个子序列分别采用归并排序； 将两个排序好的子序列合并成一个最终的排序序列。 

 

 

 

参考代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 1e8 + 10;
 4 int n, a[MAXN], T[MAXN];
 5 void Mergesort(int l, int r) {
 6     if (l == r) return; //区间内只有一个数，返回
 7     int mid = l + r >> 1; //相当于(l + r) / 2
 8     Mergesort(l, mid); //递归左半部分
 9     Mergesort(mid + 1, r); //递归右半部分
10     int i = l, j = mid + 1, k = l;
11     while (i <= mid && j <= r) //合并
12         if (a[i] <= a[j]) T[k++] = a[i++];
13         else T[k++] = a[j++];
14     while (i <= mid) T[k++] = a[i++];
15     while (j <= r) T[k++] = a[j++];
16     for (int q = l; q <= r; q++) a[q] = T[q]; //转移
17 }
18 int main() {
19     scanf("%d", &n);
20     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
21     Mergesort(1, n);
22     for (int i = 1; i <= n; i++) printf("%d ", a[i]);
23     return 0;
24 }

 

6、快速排序（Quick Sort） 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 

 

参考代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 1e8 + 10;
 4 int n, a[MAXN];
 5 void quickSort(int l, int r) {
 6     if (l >= r) return;
 7     int i = l, j = r, base = a[l]; //base取最左边的数为基准数
 8     while(i < j) {
 9         while (a[j] >= base && i < j) j--;
10         while (a[i] <= base && i < j) i++;
11         if (i < j) swap(a[i], a[j]);
12     }
13     a[l] = a[i]; a[i] = base; //基准数归位
14     quickSort (l, i - 1); //递归左边
15     quickSort (i + 1, r); //递归右边
16 }
17 int main() {
18     scanf("%d", &n);
19     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
20     quickSort(1, n);
21     for (int i = 1; i <= n; i++) printf("%d ", a[i]);
22     return 0;
23 }

7、堆排序（Heap Sort） 堆排序（Heap-sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 参考地址

 

参考代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 const int MAXN = 1e8 + 10;
 5 int h[MAXN], size;
 6 void down(int u) {
 7     int t = u;  // t记录最小值
 8     if (2 * u <= size && h[2 * u] < h[t]) t = 2 * u; // 左儿子
 9     if (2 * u + 1 <= size && h[2 * u + 1] < h[t]) t = 2 * u + 1; // 右儿子
10     if (t != u) { //需要调整
11         swap(h[t], h[u]);
12         down(t); //递归
13     }
14 }
15 int main() {
16     scanf("%d", &n);
17     for (int i = 1; i <= n; i ++) scanf("%d", &h[i]);
18     size = n;
19     for (int i = n / 2; i >= 1; i--) down(i); //初始化堆
20     while (n--) {
21         printf("%d ", h[1]);
22         h[1] = h[size]; size--;
23         down(1); 
24     }
25     return 0;
26 }

 

参考代码2（优先队列）：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 1e8 + 10;
 4 int n;
 5 priority_queue<int, vector<int>, greater<int> >q; //小根堆
 6 int main() {
 7     scanf("%d", &n); int x;
 8     for (int i = 1;i <= n; i++) scanf("%d", &X), q.push(X);
 9     while (!q.empty()) {
10         printf("%d ", q.top()); //入队
11         q.pop(); //出队
12     }
13     return 0;
14 }

8、计数排序（CounTing Sort） 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 

 

参考代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
long long n, cnt[MAXN];
int main() {
    scanf("%lld", &n); int x = 0, Max = -0x3f3f3f, Min = 0x3f3f3f; //初始化最大值和最小值
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &X); cnt[x]++; //统计
        Max = max(Max, X); Min = min(Min, X); //更新最大值和最小值
    }
    for (int i = Min;i <= Max; i++)
        while(cnt[i]) cnt[i]--, printf("%d ", i); //输出
    return 0;
}

 

 

9、桶排序（Bucket Sort） 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。 

这里。。。没有查到代码。。。（都是计数排序的。。。）。。。本蒟蒻也不会。。。哪位神犇大佬会桶排序发个代码谢谢！（跪拜大佬） 

 

10、基数排序（Radix Sort） 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。 

 

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int maxbit(int data[], int n) {
 4     int d = 1, p = 10; //d保存最大的位数 
 5     for (int i = 0;i < n; i++) while(data[i] >= p) p *= 10, d++;
 6     return d;
 7 }
 8 void radixsort(int data[], int n) { //基数排序 
 9     int d = maxbit(data, n);
10     int tmp[n];
11     int cnt[15], i, j, k, radix = 1;
12     for (i = 1;i <= d; i++) { //进行d次排序
13         memset(cnt, 0, sizeof(cnt)); //清空计数器
14         for (j = 0;j < n; j++) {
15             k = (data[j] / radiX) % 10;
16             cnt[k]++;
17         }
18         for (j = 1;j < 10; j++) cnt[j] += cnt[j - 1];
19         for (j = n - 1;j >= 0; j--) {
20             k = (data[j] / radiX) % 10;
21             tmp[cnt[k] - 1] = data[j];
22             cnt[k]--;
23         }
24         for (j = 0;j < n; j++) data[j] = tmp[j];
25         radix *= 10;
26     }
27 }
28 const int MAXN = 1e8 + 10;
29 int n, arraY[R_310_11845@AXN];
30 int main(){
31     scanf("%d", &n);
32     for (int i = 0;i < n; i++) scanf("%d", &arraY[i]);
33     radixsort(array, n);
34     for (int i = 0;i < n; i++) printf("%d ", arraY[i]); puts("");
35 }

 

如释重负。。。 

c++排序算法整理

参考资料：@H_696_121@

十大经典排序算法（超详细配动图解释）

 

 

大佬总结

以上是大佬教程为你收集整理的c++排序算法整理全部内容，希望文章能够帮你解决c++排序算法整理所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
标签：c++listphpshellwhile快速排序排序程序员算法索引
猜你在找的程序笔记相关文章
其他相关热搜词更多
phpJavaPython程序员load中如何string使用参数jquery开发安装listlinuxiosandroid工具javascriptcap