目录
概况
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。其基本思想为：任取待排序元素序列中的某元素作为基准值x，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
算法思路
快速排序——分治
思路一：
暴力
1.先开俩个临时空间a[],b[]
2.扫描q[l-r]
若q[i]<=x,则x=a[],q[i]>x,则x=b[],
3.将俩个临时空间a[],b[] 赋回q[ ]
思路二：
1.确定分界点x 左 q [l], 中 q [(l+r)/2], 右 q [r]
2.调整区间 让小于等于x的放在左边，大于等于x的放右边
3.递归处理 左右俩段
例
若x=3
编辑
例题
题目：acwing.785. 快速排序
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5 3 1 2 4 5
输出样例：
1 2 3 4 5
原题链接：AcWing 785. 快速排序
#include<iostream> using namespace std; const int N = 1e6 + 10; int n; int q[N]; void quick_sort(int q[], int l, int r) { if (l >= r) return; //如果左边界大于右边界，则说明数组为空，直接return（判边界） int x = q[(l + r) >> 1], i = l - 1, j = r + 1; //取中间点为临界点 //int x = q[l], i = l-1, j = r+1; //取左临界点 //int x= q[r], i=l,j=r-1//取右临界点 while (i < j) //迭代 { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); /* if（i<j） { int t =q[i]; q[i]=q[j]; q[j]=t; }*/ } quick_sort(q, l, j); quick_sort(q, j + 1, r);//注意：用i不能用l做边界，用j不能用做边界，否则容易死循环 } int main() { scanf("%d", &n);//输入n个数 for (int i = 0; i < n; i++) scanf("%d", &q[i]); quick_sort(q, 0, n - 1); for (int i = 0; i < n; i++) printf("%d ", q[i]); return 0; }
题目：acwing.786. 第k个数
给定一个长度为 n的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第 k 小数。
数据范围
1≤n≤100000
1≤k≤n
输入样例：
5 3 2 4 1 5 3
输出样例：
3
原题链接：AcWing 786. 第k个数
#include <iostream> using namespace std; const int N = 1e6+10;// 数据范围:1≤n≤100000 1≤k≤n int q[N]; int quick_sort(int q[], int l, int r, int k) { // 区间只有一个元素，且k在区间中，则k即为该元素，直接返回即可 if (l >= r) return q[l]; int x = q[(l + r) >> 1],i = l - 1, j = r + 1 ; while (i < j)//迭代 { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); /* if（i<j） { int t =q[i]; q[i]=q[j]; q[j]=t; }*/ } if (j - l + 1 >= k) return quick_sort(q, l, j, k); // // 除去了j-l+1个比k小的数，那么k是剩下数中的第 k - (j-l+1)大的数 else return quick_sort(q, j + 1, r, k - (j - l + 1)); } int main() { int n, k; scanf("%d %d", &n ,& k); for (int i = 0; i < n; i++) scanf("%d", &q[i]); cout << quick_sort(q, 0, n - 1, k) << endl; return 0; }
好了，本篇学习笔记就到此为止了，如有问题欢迎指正，谢谢各位佬的支持!
