Dorado's host
首页
日常
追番
随笔
工作
技术杂项
开源项目
学习
java基础
mit 6.S081
算法
写题目
学知识
友链
留言
关于我
登录
首页
日常
追番
随笔
工作
技术杂项
开源项目
学习
java基础
mit 6.S081
算法
写题目
学知识
首页
›
学知识
›
快速排序
快速排序
2022-02-05 17:29
834
0
## 思想 快速排序本质上是一个分治的算法,大致步骤如下: 1. 确定分界点:可以是左右边界,中间点或者随机random下标 2. **重新划分区间:调整区间为保证所有x左边的数都小于等于x,所有x右边的数都大于等于x** 3. 递归处理左右两端 ## 如何优雅的划分区间 ``` TEST DATA 6 5 9 6 8 ``` ### 暴力 暴力的思想是开拓新的空间存放x的左右区间值,最后再合并的做法 对于测试数据来说,我们取 `x = 6`,并开两个数组表示6的左右区间,分别为a,b 一遍遍历之后可以得到,`a[] = {5, 6}, b[] = {9, 8}` ### 双指针 双指针思想的大致思想是创建两个指针分别指向数据的左右边界,然后左右指针分别移动,当左指针找到比x大的,右指针找到比x小的数时,交换两个指针所指向的数。当两个指针重合时,即可划分区间。 ``` first x = 6 ============================== 6 5 9 6 8 l r ============================== 初始状态 ``` ``` second x = 6 ============================== 6 5 9 6 8 l r ============================== l指针向后移动发现第一个大于 x = 6 的数 ``` ``` third x = 6 ============================== 6 5 9 6 8 l r ============================== r指针向前移动发现第一个小于 x = 6 的数 ``` ``` fourth x = 6 ============================== 6 5 6 9 8 l r ============================== swap(i, j) ``` ``` fourth x = 6 ============================== 6 5 6 9 8 lr ============================== l指针向后移动发现小于 x = 6 的数 ``` ``` fourth x = 6 ============================== 6 5 6 9 8 r l ============================== r指针向前继续移动发现大于 x = 6 的数 ``` ``` fourth x = 6 ============================== 6 5 6 9 8 r l ============================== 发现l > r, 排序结束 ``` ## 板子 ``` #include
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; int x = q[(l + r) >> 1]; int 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]); } quick_sort(q, l, j); quick_sort(q, j + 1, r); } int main() { scanf("%d", &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]); }; } ``` # 例题 ``` https://www.acwing.com/problem/search/1/?search_content=快速排序 ```
相关文章
评论
(暂无评论)
取消回复
发表评论
dorado
一个平平无奇的打工人
17
文章
1
评论
12
栏目
热门文章
寻找两个正序数组的中位数
0 评论
ubutnu下的git常用命令
0 评论
IDEA快捷键一览(转)
0 评论
每日一报自动点击脚本
0 评论
端口查询
0 评论
更多