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

本文主要是介绍分治法经典思想 - 浅谈快速排序思想（配合代码讲解），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

浅谈快速排序思想（配合代码讲解）

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

快速排序的分治策略是：

（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)

这篇关于分治法经典思想 - 浅谈快速排序思想（配合代码讲解）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！