简介

快速排序，看这名字就知道这是一种很快的排序方法，实际上也是如此。快速排序属于分治法的一种，就是说通过把数据分成几部分来同时处理的一种算法。这种算法很重要，所以研发岗的面试经常考。

快速排序的步骤

我们以数组int[]a={7,5,3,2,9,10,8,4,6,1};这个数组为例来说明一下快速排序到底是怎么进行的。

第1步：找基准值

所谓的基准值，顾名思义就是以它为基准进行比大小。通常来说，我们选取数组的第一个数为基准值。在数组a里基准值就是7.

第2步：比大小

先从数组的最右边开始往左边找比基准值小的第一个数，然后从数组的最左边开始往右找比基准值大的第一个数。那么为什么要这么找呢？因为现在我们要把数组从小到大排序，所以要找出比基准值小的数放到基准值的左边，找出比基准值的数放在基准值的右边。
那么在数组a里，从左往右找，第一个比7大的数就是9，我们把它的坐标记为i；从右往左找，第一个比7小的数就是1，我们把它的坐标记为j。

第3步：交换

找到之后，如果这个时候i<j，那么就交换这两个数，因为i=4,j=9，符合条件，将9和1进行交换。现在数组变成了int[]a={7,5,3,2,1,10,8,4,6,9};
如果j>=i，那么不做处理
为什么还要判断i和j的大小呢？就像第二步说的，我们要找出比基准值小的数放到基准值的左边，找出比基准值的数放在基准值的右边。所以如果i<j的话，交换就达到目的了，如果i>=j，比基准值小的数就在基准值的左边，比基准值大的数已经在基准值的右边了，这时候就没必要交换了。

第4步：继续查找

在i<j的前提下，继续向右查找比基准值大的数，往左找比基准值小的数，然后交换。
在我们的例子中，10和6、8和4都符合交换的条件，所以数组就变成了
int[]a={7,5,3,2,1,6,4,8,10,9};这时候i=6,j=7

第5步：交换基准值到合适的位置

当查找继续进行，这时候i=j=6，已经不满足继续查找和交换的条件了，那么我们应该怎么办呢？答案就是把a[6]和基准值交换，因为i=j的时候说明已经到了一个分界线的位置，分界线左边的数比基准值小，分界线右边的数比基准值大，而这个分界线就是我们的基准值，所以把它和a[i]交换，这时候数组就变成：
int[]a={4,5,3,2,1,6,7,8,10,9};

第6步：重复

对基准值左右两边的两个子数组重复前面五个步骤直至排序完成。

复杂度

时间复杂度

从上面的步骤可以看出来快速排序的快慢取决于区域划分的次数，理想情况下是每次都等分，所以划分次数为logn（即log₂n)，时间复杂度为
T[n] = 2T[n/2] + O(n)其中O(n)为PARTITION()的时间复杂度，对比主定理，

T[n]= aT[n/b]+f (n)

我们的快速排序中：a = 2, b = 2, f(n) = O(n)

最坏的情况就是每次划分之后，一边只有一个元素，另一边有n-1个元素，这样就得划n-1次，这时候时间复杂度为O(n²)

所以平均的时间复杂度为O(nlogn)

空间复杂度

不需要额外的空间，空间复杂度为O(1)

稳定性

快速排序算法的稳定性取决于和基准值交换的那个数的大小，如果它们相等的话，那么稳定性就被破坏了，所以快速排序是一种不稳定的排序方法。

java实现

  public void quickSort(int[]a,int left,int right)
{
    if(left>right)
        return;
    int pivot=a[left];//定义基准值为数组第一个数
    int i=left;
    int j=right;
    
    while(i<j)
  {
     while(pivot<=a[j]&&i<j)//从右往左找比基准值小的数
           j--;
     while(pivot>=a[i]&&i<j)//从左往右找比基准值大的数
           i++;
       if(i<j)                     //如果i<j，交换它们
    {
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
  }
   a[left]=a[i];
   a[i]=pivot;//把基准值放到合适的位置
   quickSort(a,left,i-1);//对左边的子数组进行快速排序
   quickSort(a,i+1,right);//对右边的子数组进行快速排序
}

参考

快速排序
That's all.