379 字
2 分钟
排序算法
各种排序
| 排序 | 概述 | 时间复杂度 |
|---|---|---|
| 计数排序 | 对应票投入对应票箱 | O(n) |
| 选择排序 | 最小的放前 (两重循环) | O(n^2^) |
| 冒泡排序 | 依次比较相邻 (两重循环) | O(n^2^) |
| 插入排序 | 依次拿出一张牌插入排列中 (两重循环) | O(n^2^) |
| … |
这些排序各适用不同情况，但时间复杂度总体较大。
快速排序
程序设计竞赛中最普遍的排序。
随机选择哨兵，时间复杂度O(n log n)。但极端情况O(n^2^)。
概述：
选出一个哨兵，比哨兵小的数全放左边，比他大的全放右边。
再分别在左边和右边选出哨兵，进行分类。
以此循环，直到排序完成。
#include <iostream>using namespace std;
void qsort(int num[],int first,int last) { int i = first, j = last, flag = num[(first + last) / 2], temp; do { while (num[i] < flag) i++; while (num[j] > flag) j--; if (i <= j) { temp = num[i]; num[i] = num[j]; num[j] = temp; i++; j--; } } while (i <= j); //带=为了让i和j交错而过，这样才可以用递归 if(first<j) qsort(num, first, j); if(i<last) qsort(num, i, last);}
int main(){ int n, num[100000]; cin >> n; //必须从i=1开始 for (int i = 1; i <= n; i++) { cin >> num[i]; } qsort(num,1,n); for (int i = 1; i <= n; i++) { cout << num[i]<<" "; } return 0;}当然也可以直接用algorithm头文件中的sort函数，
我们学会自己写是为了理解原理，提升思维，
同时在有特殊需求的时候可以更自定义化。
分享文章
生成精美分享图或复制链接，与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ，距今已过 1306 天
部分内容可能已过时
评论