分治法,分而治之,充分理解分治法是运用好快速排序的关键
这里借用清华大学出版社的一次划分示意图中的内容来进行讲解
从上图的过程中可以看出,每次排序,选定第一个数为此次排序的轴值,每一次排序的目的就是将选定的这个数字,放到属于他的合适的位置,这个合适的位置是指:它前边的数全部小于它,后面的数全部大于它
之后就是一个递归的过程,分别处理两端,直至处理完成
同样引用清华大学出版社的快速排序示意图进行讲解
#include <iostream> #include <cstring> #include <algorithm> using namespace std; //定义一些全局变量 在主函数以及函数中都可以使用 int n; const int N = 1e6+10; 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;//因为我们每次都是 先移动再比较 所以第一次移动的时候我们需要把边界扩大一格 int j = r+1;//同理 while(i<j) { do i++; while(q[i] < x);//若左边的值小于x i一直向右移 do j--; while(q[j] > x);//若右边的值大于x j一直向左移 if(i < j) swap(q[i],q[j]);//如果停下 说明要交换啦 swap交换函数 } //对上述提到的轴值两边分别进行快速排序 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]);//写出数据 return 0; }