分治法经典思想 - 浅谈快速排序思想(配合代码讲解)

浅谈快速排序思想(配合代码讲解)

分治法,分而治之,充分理解分治法是运用好快速排序的关键

快速排序的分治策略是:

(1)划分:选定一个记录作为轴值,以轴值为基准将整个序列划分为两个子序列 r1 … ri-1 和 ri+1 … rn,前一个子序列中记录的值均小于或等于轴值,后一个子序列中记录的值均大于或等于轴值;

(2)求解子问题:分别对划分后的每一个子序列递归处理;

(3)合并:由于对子序列 r1 … ri-1 和 ri+1 … rn 的排序是就地进行的,所以合并不需要执行任何操作。

分治法经典思想 - 浅谈快速排序思想(配合代码讲解)

一次划分过程

这里借用清华大学出版社的一次划分示意图中的内容来进行讲解
分治法经典思想 - 浅谈快速排序思想(配合代码讲解)

  从上图的过程中可以看出,每次排序,选定第一个数为此次排序的轴值,每一次排序的目的就是将选定的这个数字,放到属于他的合适的位置,这个合适的位置是指:它前边的数全部小于它,后面的数全部大于它

之后就是一个递归的过程,分别处理两端,直至处理完成

同样引用清华大学出版社的快速排序示意图进行讲解分治法经典思想 - 浅谈快速排序思想(配合代码讲解)

下面是代码讲解(详细注释表明在代码中)

#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;
}

值得注意的是 在上述图中提到的轴值举例 是以每次排序的第一个数字作为轴值,但在实际情况中,这种取法会造成超时情况产生,所以我们必须使用mid = l + r >> 1取中值计算

时间复杂度O(nlog2n)

上一篇:【算法基础】 - 快速排序


下一篇:Quick BI 的可视分析之路