acwing学习笔记中如何高效掌握快速排序算法？

本文共计531个文字，预计阅读时间需要3分钟。

基本思想+这是一种快速排序的模板题目，主要思想是分治，通过在数组两端设置两个指针+l和+r，然后设置一个中间指针x，x可以是l，也可以是(l+r)/2，还可以是r作为参照物。如果是由小到大排序，则当x的值大于等于r时，停止递归。

基本思想

这是快速排序的一道模板题，主要思想是分治，通过在数组两边设置两个指针 l 和 r ， 然后设置一个 x ， x可以是l， 也可以是 (l + r) / 2, 也可以是r作为参照物。如果是由小到大排序，l 指针和 r 指针每次往后移动一位，当l > x 时, l 指针不动，当 r < x 时， r 不动， 此时 l 和 人交换位置，那么只要 x 左边的数是小于x的， x 右边的数是大于x的，往下递归，等到l >= r ,也就是，两个指针重和或穿插过去后，排序完成，程序结束。

#include <iostream> using namespace std; const int N = 1e6 + 10; int q[N]; int n; void quick_sort(int q[], int l, int r) { if(l >= r) return; //排序结束 //x可以取l，r， （l + r ) / 2 //这里i和j要注意边界问题，i和j之所以要往两边移一位，是因为为了保证指针每次都是移动的，那么无论怎样，都要先往里移动一次 int x = q[l], i = l - 1, j = r + 1; while(i < j) { //左边i指针往右移动，只要指针指向的数字是小于x的，否则停下 do i++; while(q[i] < x); do j--; while(q[j] > x); //等到两个指针都停下了，那么交换i和j指针，这样就能保证x左边小于x，x右边大于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]); }