【排序算法系列 6】 高级排序——归并排序（由冒泡排序改进）

【排序算法系列 1】冒泡排序 【排序算法系列 2】选择排序 【排序算法系列 3】 插入排序 【排序算法系列 4】 高级排序——希尔排序（插入排序的改进） 【排序算法系列 5】 高级排序——归并排序 【排序算法系列 6】 高级排序——归并排序（由冒泡排序改进） 【排序算法系列 7】堆排序

---

简介

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

需求

排序前：{6, 1, 2, 7, 9, 3, 4, 5, 8}排序后：{1, 2, 3, 4, 5, 6, 7, 8, 9}

快速排序原理

首先设定一个分界值，通过该分界值将数组分成左右两部分；将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

快速排序API设计

类名Quick构造方法Quick()：创建Quick对象成员方法 11.public static void sort(Comparable[] a)：对数组内的元素进行排序成员方法 22.private static void sort(Comparable[] a, int lo, int hi)：对数组a中从索引lo到索引hi之间的元素进行排序成员方法 33.public static int partition(Comparable[] a,int lo,int hi):对数组a中，从索引 lo到索引 hi之间的元素进行分组，并返回分组界限对应的索引成员方法 44.private static boolean less(Comparable v,Comparable w):判断v是否小于w成员方法 55.private static void exch(Comparable[] a,int i,int j)：交换a数组中，索引i和索引j处的值

切分原理

把一个数组切分成两个子数组的基本思想：

找一个基准值，用两个指针分别指向数组的头部和尾部；先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；交换当前左边指针位置和右边指针位置的元素；重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。

快速排序的代码实现

public class Quick { //比较v元素是否小于w元素 private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } //数组元素i和j交换位置 private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } //对数组内的元素进行排序 public static void sort(Comparable[] a) { int lo = 0; int hi = a.length-1; sort(a,lo,hi); } //对数组a中从索引lo到索引hi之间的元素进行排序 private static void sort(Comparable[] a, int lo, int hi) { //安全性校验 if (hi<=lo){ return; } //需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）； int partition = partition(a, lo, hi);//返回的是分组的分界值所在的索引，分界值位置变换后的索引 //让左子组有序 sort(a,lo,partition-1); //让右子组有序 sort(a,partition+1,hi); } //对数组a中，从索引 lo到索引 hi之间的元素进行分组，并返回分组界限对应的索引 public static int partition(Comparable[] a, int lo, int hi) { //确定分界值 Comparable key = a[lo]; //定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置 int left=lo; int right=hi+1; //切分 while(true){ //先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止 while(less(key,a[--right])){ if (right==lo){ break; } } //再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止 while(less(a[++left],key)){ if (left==hi){ break; } } //判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可 if (left>=right){ break; }else{ exch(a,left,right); } } //交换分界值 exch(a,lo,right); return right; } }

快速排序的时间复杂度:

最优情况下，快速排序的时间复杂度为O(nlogn)

最坏情况下，快速排序的时间复杂度为O(n^2)