C语言十大经典排序算法：快速排序

在对于刚接触编程这个领域的同学，对排序还没有一定的了解的时候，就光是听到快速排序这个名称就会觉得很有吸引力，那实际上，它的作用就和它的名字一样很有分辨性。

快速排序是对冒泡排序的一种改进，就如同它的名字一般，相对于其他几种排序来说效率较高，速度更快，其实对于初学者而言，快速排序还是很难理解的。因为快速排序的一些特殊性，现在很多公司也会去选择它作为面试的考题，如果仅仅是依靠背代码，默写的方式的话估计很难去把快速排序写好，用好，所以我们这个时候就得知道思路的一个重要性，只有把它的思想理解到位，我们才能更快的把快速排序玩会。

首先，我们先来看一下快速排序的一个概念：快速排序是指通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。

这一段话呢，我们可以提取几个重要的点：

1、它是通过分治法的策略把一段数据分成两个子数据

2、通过递归的方式

虽然快速排序的架构比起其他排序相对来说是效率较快的，但还是免不了有最坏的结果，在n个项目的比较中，时间复杂为O(n2) ,也就是说比较n个数，可能要比较n2次，不过这个过程还是不常见的，之前我看过很多博主的文章都是在说快速排序的不稳定性，但是快速排序虽然有最坏的结果，但在绝大部分情况，还是很优秀的，那为什么要说它不稳定呢？有人说时间不稳定，这句话是完全可以推翻的，十种排序里面基本上光靠时间来推理说它不稳定就可以发现这句话的漏洞所在，所以光看时间这么一点就果断的说这个排序不稳定的，只能说很不谨慎了。

我为了很谨慎的去找到它的不稳定的原因，试了很多例子，最后发现一个数组里如果有两个相同的数的时候，快排会搞混它们两个的位置，了解数组的同学肯定都知道数组里面的数虽然可以相等，但是下标绝对会不一样，快排在排序的过程中就可能导致下标大的反而在前面，下标小的反而在后面，我想这就是为什么说快速排序不稳定的原因了吧。

那回到我们最开始的思路，我们代入上面提取出来的两个点来详细看一下快速排序的思路

首先呢，得去找一个基准数，一般来说数组第一个为基准数，现在可以理解为数组第一个数赋值给了key，成为基准数，数组的第一个位置产生了空缺（有位置没人坐），再去找到一个最左边的下标，一个最右边的下标（其实就是长度减一）

为了我们后面排序更好的进行，我们再去定义两个下标i,j分别等于left,right

int i = left,j = right;
int key = a[i];

i 和 j就会一个从左边进行比较，一个从右边进行比较，记录每次比较之后的下标

接下来从右边第一个数开始和基准数对比，大于基准数则不变，小于基准数则放到空缺的位置上面去，那现在从右边的对比就暂时结束，新的空缺位产生 

while((i < j) && (a[j] > key))
{
    j--;
}
    a[i] = a[j];

接下来再从左边开始和基准数对比，比基准数小则保持不变，比基准数大则移到空缺位，新的空缺位产生，从左边的对比暂时结束

while((i < j) && (a[i] < key))
{
    i++;
}
    a[j] = a[i];

继续从右边上一次的位置进行之前相同的操作

现在就回到了左边，我们可以清晰的看到i 和 j已经相遇了那这个时候第一次对比结束，将基准数放回最后的空缺位置，第一次快排结束。

这时候聪明的同学就会发现一个隐藏条件，也是循环的退出条件 i < j 

a[i] = key；

第一次快排结束之后整个排序并没有结束，接下来我们通过递归继续剩下来的对比，由之前这个基准数为界，划分为左右两部分，两部分同时进行第一次快排相同的步骤，直到全部比较完变成一个有序的数组。

sort(a,left,i-1);
sort(a,i+1,right);

以上呢，是数组实现快速排序的基本步骤，一些重点的代码部分也写了出来，为的就是让同学们学会将思想转化为代码。

那接下来我们来一起看看快速排序的完整代码

#include <stdio.h>
void sort(int a[],int left,int right)
{
    int i = left,j = right;
    int key = a[i];
    if(left >= right) //左边始终要小于我们的右边，如果等于结束整个程序
        return;
    while(i < j)  //  每次快排退出条件
    {
        while((i < j) && (a[j] > key))
        {
            j--;
        }
            a[i] = a[j];
            while((i < j) && (a[i] < key)) // 这里的i < j防止上面的j减过头导致程序出现错误
        {
            i++;
        }
            a[j] = a[i];
    }
    a[i] = key;
    sort(a,left,i-1);     //递归将数组分成两部分同时进行快排
    sort(a,i+1,right);   //  i  就是第一次快排相遇的下标位置
}
int main()
{
    int i;
    int a[]={2,1,5,4,6,3};
    int len = sizeof(a)/sizeof(a[0]);
    sort(a,0,len-1);      //传参，left = 0,right = 长度 - 1
    for(i = 0; i < len; i++)
    {
        printf("%d",a[i]);
    }
    printf("
");
    return 0;
}