今天小玄为大家带来平时代码时常用的一种排序方法——快速排序

算法简介

快速排序（Quick Sort）是在冒泡排序的基础上演变而来的，实际上是冒泡排序的 递归分治法。

快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移到数列的一边，比它小的元素移到数列的另一边，从而把数列拆解成了两个部分。

具体流程如下：

1. 通过分割将对象局部数组分割成前后两个局部数组（Divide）
2. 对前半部分数组执行quickSort(Solve)
3. 对后半部分数组执行quickSort(Solve)

算法解析

我们实现要确定分界点x - 取q【(l + r) / 2】 或者是    随机值 然后使用双指针进行操作 -—— L R

我们确保在分界点左边的数都小于等于x

在分界点右边的数都大于x

L++ R--,直到发现L找到了>x的数，R找到了小于等于x的数，将两个数进行交换 持续这样的过程直到两个指针相遇为止  —— L >=  R

接下来我们只要将这样的过程持续递归进行下去即可。

代码思路

一，“暴力处理”

1. 创建两个数组 a[] b[]
2. 创建存储数组 q[]

1. q[l ~ r] (如果 q[i]  <= x  ——  x -> a[])  
2. q[l ~ r] (如果 q[i]  > x  ——  x -> b[])

3. 结果输入

1. a[]  -> q[]        
2. b[]  -> q[]

二，优美的解法（按上述思路在原数组进行操作）

大致思路如上图所示。

代码实现

C语言

#include <stdio.h>
intarr[1000],n;   //定义全局变量，这两个全局变量需要在函数中使用
voidquicksort(intleft,intright)
{
inti = 0;
intj = 0;
intt = 0;
inttemp = 0;
if(left > right)
return;
temp = arr[left];  //temp中存的是基准数
i = left;
j = right;
while(i!= j)
    {
        //顺序很重要，从右往左找
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
        //交换两个数在数组中的位置
if(i < j) //当哨兵i和哨兵j没有相遇的时候
        {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
        }
    }
        //最终将基准数归位
arr[left] = arr[i];
arr[i] = temp;
quicksort(left,i-1);
quicksort(i+1,right);
return;
}
intmain()
{
inti = 0;
intj = 0;
scanf("%d",&n);
for(i = 0;i < n ;i++)
    {
scanf("%d",&arr[i]);
    }
quicksort(0,n-1);
for(i = 0;i < n-1;i++)
printf("%d ",arr[i]);
printf("%d",arr[n-1]);
return0;
}

c++

#include <iostream>
usingnamespacestd;
constintN = 1e6 + 10;
intn;
intq[N];
voidquick_sort(intq[],intl,intr)
{
if(l >= r) return;
inti = l-1,j = r + 1, x = q[(l + r) >> 1];
while(i < j)
    {
doi ++; while(q[i] < x);
doj--; while(q[j] > x);
if(i < j) swap(q[i],q[j]);
    }
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
intmain()
{
scanf("%d",&n);
for(inti = 0;i < n;i++) scanf("%d",&q[i]);
quick_sort(q,0,n-1);
for(inti = 0;i < n;i++) printf("%d ",q[i]);
return0;
}

延伸讨论

快速排序和归并排序一样基于分治法。 但其执行partition进行分割时就已经在原数组中完成了排序，因此不需要归并排序中那样手动的合并处理。

快速排序在分割的过程中会交换不相邻元素，因此属于不稳定的算法。另一方面，归并排序需要O（n）的外部储存空间，快速排序并不需要用到额外内存。也就是说，快速排序是一种原地算法（内部排序）。

在分割时如果能恰好取到中间值，那么整个过程大致和归并排序一样分为log2n层。快速排序的时间复杂度是O（logn），是一般情况下最高效的排序算法。不过如果我们选择固定的方式来选择基准的话，在处理某些数据（例如已经排序完的数据）时效率会大打折扣，最复杂的情况甚至达到O(n2).不仅如此，某些顺序的数据可能会让递归深度过深，最终导致栈溢出。一般情况下，我们需要在选择基准的方式上多花费心思，比如随机选择，或者任选出几个之后取中间值也可。

今天的文章到此就结束啦，如果觉得对你有帮助的话，请给小玄：