1.快速排序
标签：int nlog 包括 als col ++i 一起 pac include
快速排序的基本思想是分治。
快速排序的步骤：
假设区间是从l到r的话
1：确定分界点x。在要排序的数组内找到一个数作为分界点x。（q[l], q[(l + r) / 2], q[r], 随机值）
2：划分区间。使得左区间里的数都小于等于x，右区间里的数都大于等于x。快速排序是选择一个数来划分区间。
3：递归处理左右两区间。左区间排好序，右区间排好序后再拼在一起，整个区间就排好序了。
快速排序的平均时间复杂度是nlogn
有可能被卡为n^2
开俩数组的暴力做法
题目：快速排序
1 #include 2 using namespace std;
3 const int N = 100010;
4 int a[N];
5 void quick_sort(int l, int r) {
6 if (l >= r) { //如果区间里没有数了，或区间里只有一个数
7 return;
8 }
9 int x = a[(l + r) / 2], i = l - 1, j = r + 1;
10 //x是选定的值
11 //i是左指针
12 //j是右指针
13 //两个指针放在区间边界再左右一格
14 while (i j) {
15 while (a[++i] x);
16 while (a[--j] > x);
17 if (i j) {
18 swap(a[i], a[j]);
19 }
20 }
21 //注意若为j，x就不能取a[r]。i指针前面所有的数，不包括i，都是小于等于x的。j指针后面所有的数都是大于等于x的。
22 quick_sort(l, j);
23 quick_sort(j + 1, r);
24 //若为i-1,就不能取a[l],可以是a[(l + r + 1) / 2]
25 //quick_sort(l, i - 1);
26 //quick_sort(i, r);
27 }
28 int main() {
29 ios::sync_with_stdio(false);
30 cin.tie(0);
31 cout.tie(0);
32 int n;
33 cin >> n;
34 for (int i = 0; i ) {
35 cin >> a[i];
36 }
37 quick_sort(0, n - 1); //下标为0和n-1
38 for (int i = 0; i ) {
39 cout " ";
40 }
41 return 0;
42 }
1.快速排序
标签：int nlog 包括 als col ++i 一起 pac include
原文地址：https://www.cnblogs.com/fx1998/p/12795075.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
1.快速排序
文章链接：http://soscw.com/essay/81869.html
评论