[数据结构与算法]快速排列算法详细解析

本文讲解一种快速排列的算法以及其实现形式，之前我们的排序算法有比较排序，冒泡排序等，但是这次我们讲一个快速排序的方法消耗时间最短。

原理部分：

对于一个数组而言，我们假设排序的起点为l,重点为r,在这段数组中我们随机选择一个数字x。设定两个指针，分别指向l和r，也就是数组的两端，然后分别从两端开始向中间挪动，右端指针指向的数字大于x，则指针向左边（中间）挪动，指向下一个数组元素，如果指向的数组元素等于或者小于x，则停止指针的移动。开始左端指针的判断，如果指针指向的数字小于x,指针向右面移动一个，直到指针指向的数字大于等于x，停止指针的移动。这时交换指针指向的数组元素。然后继续指针判断向中间移动，直到两个指针相遇。

我们通过这样一个过程最终得到的数据形式为：

?这样我们这个数组就被x，分为两段了。那么我们在分开的两段中分别再找一个随机的数最为比较的对象，再将这两段各自分为两段，分到最后就完成了排序过程。

算法思路很简单，但是实现起来不是特别容易，用到迭代思维和边界处理。

void quick_sort(int l,int r,int q[]) //定义左边界l,有边界r,用来比较的数值x
{
    if(l>=r) return;    //迭代思维：在过程中我们遇到左边界等于有边界说明数组就剩下一个元素，完成 
                        //排序，可退出
    int  x = q[l],i = l-1,j = r+1;     //这里的加一减一是因为下面首先进行了加加操作和减减操作
    while(i < j)        //直到两指针相遇，完成一次分段
    {
        do i++; while(q[i] < x);   //先做加加操作是为了在指针指向的数字等于x的时候能够跳到下一个 
                                  //位置
        do j++; while(q[j] > x);
        if(i < j) swap(q[i],q[j]);
    }
    //当两个指针相遇后，进行再分段操作--->>>迭代思维
    quick_sort(0,j,q);
    quick_sort(j+1,n,q);
}

接下来我们做一个完整的测试：

#include <iostream>
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], 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);    //这里必须将J作为分界点，我在下面会做一个分析
    quick_sort(q, j + 1, r);
}

int main()
{
    //scanf("%d", &n);
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) cin >> q[i];//scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n;i++) cout << q[i] << " ";//scanf("%d", &q[i]);
 
    return 0;
}

?我选取了一个随机数组，进行测验

?

那么我们到了一个确定边界的时刻，很重要，可选i或j。会出现什么情况呢？

?在以i为分界点的时候，我们最终的分组失败，左边出现了大于3的数字24，而且这个数字24永远无法分到后面去了，我运行了一下代码验证了，如图：

?24永远在第一次分组的左边，最终导致算法出错！！！

所以分界点还是选j，因为j <= i，在停止对的时候我们能够保证q[j]是一定<=q[l]，但是不能保证q[i]=q[l]；因此选j作为分界点。