快速排序（QuickSort）

QuickSort和MergeSort很相似，都是采用的分而治之的算法。

• MergeSort考虑的是将数组分得不能再分了，再一步步的合并，每次合并的结果都是一个有序的子序列，最终使得整体有序。归并排序是稳定的排序
• QuickSort则是采用先选取一个元素，把小于等于它的元素放在左边，大于它的元素放在右边。然后再对左右两边的子序列采用相同的方式递归处理。快速排序是不稳定的排序

分而治之过程

Divide:

将数组A[p..r]重新划分为两个子数组A[p..q-1]和A[q+1..r]
使得A[p..q-1]中的任意元素小于等于A[q],A[q+1,r]中的任意元素大于A[q]
整个过程包括调整数组A[p..r]并返回划分数组的下标q

Conquer：

使用递归排序子数组A[p..q-1]和A[q+1,r]

Combine:

无

划分数组

QuickSort 关键步骤是实现划分函数partition(int[] A, int p, int r)，即如何调整数组`A[p..r]
partition(A,p,r)伪代码：

1  x=A[r]
2  i=p-1
3  for j = p to r-1
4     if(A[j]<=x)
5              i++
6              swap(A[i],A[j])
7   i++
8   swap(A[i],A[j])
9   return i

• 选取A[r]作为轴。其中A[r]的值为x,引入变量i,j 令i=p-1, j=p
• 从p到r-1扫描数组，j记录扫描过程中的数组下标 ，扫描过程中如果A[j]<=x,那么将i++,并交换A[i],A[j]。 一趟扫描完成数组中元素的关系满足如下关系:

树组下标i之前的元素小于等于轴x,（i,j）之前的元素大于x.

• 当扫描结束时i++,交换A[i]和A[r]

以[2,8,7,1,3,5,6,4]这个数组的排序为例，下图描述了partition过程中数组和i,j下标的变化：

数组和下标的变化示意图

java实现

import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args) {
        int[] array = {2, 8, 7, 1, 3, 5, 6, 4};
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(int[] array, int p, int r) {
        if (p < r) {
            int q = partition(array, p, r);
            quickSort(array, p, q - 1);
            quickSort(array, q + 1, r);
        }

    }

    /**
     * 对数组array[p..r]进行划分，设返回值为i ,划分结果为
     * array[p..i-1]<=array[i]<array[i+1..r]
     */
    public static int partition(int[] arrray, int p, int r) {
        int i = p - 1;
        int j = p;
        for (; j < r; j++) {
            if (arrray[j] <= arrray[r]) {
                swapArrayEle(arrray, ++i, j);
            }
        }
        swapArrayEle(arrray, ++i, r);
        return i;
    }

    /**
     * @param array 数组
     * @param x     数组下标x
     * @param y     数组下标y
     *              交换数组下标W为x,y的元素
     */
    public static void swapArrayEle(int[] array, int x, int y) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
}

时空复杂度分析

空间上属于原地排序，通过交换元素就可以实现排序，不需要额外的空间 复杂度为O(n)。
时间上：
分区函数时间复杂度为O(n),因为只需要一次扫描
①最坏情况是数组已经有序（正序或者逆序），因为这会导致划分函数会很不均匀。一边是n-1个元素，一边没有元素。

最坏case: T(n)=T(n-1)+T(0)+O(n)
这是一个等差数列，复杂度为O(n2)

②最好情况。每次划分有很均匀，有

T(n)=2T(n/2)+O(n)
复杂度为nlog(n)

③平均情况也是nlog(n)

优化快速排序

随机选取一个元素作为轴，partition(A,p,r)伪代码做一下调整：

1  y=Random(q,r) //y为q~r中的一个随机数
2  swap(A[y],A[r])
3  x=A[r]
4  i=p-1
5  for j = p to r-1
6     if(A[j]<=x)
7              i++
8              swap(A[i],A[j])
7   i++
9   swap(A[i],A[j])
10 return i

生成q~r范围中的一个随机数可以使用如下java代码实现

 public static  int getRandom(int q,int r){
        int length=r-q+1;
        return new Random().nextInt(length)+q;
    }