排序-快速排序及其优化

概念

快速排序是交换类排序，采用分治思想，其基本原理是：通过一趟排序，将待排序数组分割成独立的两部分，其中一部分的关键字均比另一部分小；然后再分别对这两部分序列递归进行快速排序，从而使整个序列有序。

具体算法步骤：

1. 在待排序的记录序列中选取一个记录作为枢轴(pivot)；
2. 通过一趟排序，将所有小于枢轴的记录都移到枢轴的左边，将所有大于枢轴的记录都移到枢轴的右边，其实就是将当前待排序序列分为两部分，左边部分的记录均小于右边部分的记录，这样的操作叫做partition(分割)，分割操作结束后，枢轴所处的位置就是最终排序后它所处的位置；
3. 对枢轴左右两边的子序列重复步骤1和2，直至所有子记录序列只剩下一个记录为止。

以上步骤中，关键点是 1. 枢轴(pivot)的选取方式； 2. 对分割操作(partition)的细节处理。

未优化的快速排序

1. 枢轴的选取：将待排序序列的第1个记录作为枢轴；
2. 分割操作 ： 分割操作中使用到了交换；

Java实现

// 定义接口
interface Sorter {
	/**
	 * 将数组按升序排序
	 */
	int[] sort(int[] arr);

	/**
	 * 交换数组arr中的第i个位置和第j个位置的关键字
	 */
	default void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}

// 未优化的快速排序
class QuickSorter implements Sorter {

	@Override
	public int[] sort(int[] arr) {
		quickSort(arr, 0, arr.length - 1);
		return arr;
	}

	/**
	 * 对数组arr[low...high]的子序列作快速排序，使之有序
	 */
	protected void quickSort(int[] arr, int low, int high) {
		int pivotLoc; // 记录枢轴(pivot)所在位置
		if (low < high) {
			pivotLoc = partition(arr, low, high); // 将arr[low...high]一分为二,并返回枢轴位置

			quickSort(arr, low, pivotLoc - 1);// 递归遍历arr[low...pivotLoc-1]
			quickSort(arr, pivotLoc + 1, high); // 递归遍历arr[pivotLoc+1...high]
		}
	}

	/**
	 * 在arr[low...high]选定pivot=arr[low]作为枢轴（中间位置），将arr[low...high]分成两部分，
	 * 前半部分的子序列的记录均小于pivot，后半部分的记录均大于pivot;最后返回pivot的位置
	 */
	protected int partition(int[] arr, int low, int high) {
		int pivot;
		pivot = arr[low]; // 将arr[low]作为枢轴
		while (low < high) { // 从数组的两端向中间扫描 // A
			while (low < high && arr[high] >= pivot) {  // B
				high--;
			}
			swap(arr, low, high); // 将比枢轴pivot小的元素交换到低位 // C
			while (low < high && arr[low] <= pivot) { //D
				low++;
			}
			swap(arr, low, high); // 将比枢轴pivot大的元素交换到高位 // E
		}
		return low; // 返回一趟下来后枢轴pivot所在的位置
	}
}

演示
为了方便演示，我对上面代码中的分割操作partition方法的代码进行了标注（分别标注为 A,B,C,D,E）。
对于待排序序列 {5, 1, 9, 3, 7, 4, 8, 6, 2}，我们来演示其第一趟排序过程：

low = 0, high = 8, pivot = arr[low] = 5;

• A处，low = 0, high = 8, low<high，进行A循环；

• B处，high的值不断递减，直至arr[high] = 2 小于pivot，跳出B循环：

  pivot
  ↓
  5  1  9  3  7  4  8  6  2
  ↑                       ↑
  low                    high

• C处，执行low和high的元素交换：

                        pivot
                          ↓
  2  1  9  3  7  4  8  6  5
  ↑                       ↑
  low                    high

• D处，low的值不断递增，直至arr[low] = 9 大于 pivot，跳出D循环:

                        pivot
                          ↓
  2  1  9  3  7  4  8  6  5
        ↑                 ↑
       low              high

• E处，执行low和high的元素交换：

      pivot
        ↓
  2  1  5  3  7  4  8  6  9
        ↑                 ↑
       low              high

• A处，low =2, high = 8, low < high，继续循环A；

• B处，high的值不断递减，直至arr[high] = 4 小于pivot，跳出B循环：

      pivot
        ↓
  2  1  5  3  7  4  8  6  9
        ↑        ↑
       low     high

• C处，执行low和high的元素交换：

               pivot
                 ↓
  2  1  4  3  7  5  8  6  9
        ↑        ↑
       low      high

• D处，low的值不断递增，直至arr[low] = 7 大于 pivot，跳出D循环：

               pivot
                 ↓
  2  1  4  3  7  5  8  6  9
              ↑  ↑
            low  high

• E处，执行low和high的元素交换：

               pivot
                 ↓
  2  1  4  3  5  7  8  6  9
              ↑  ↑
            low  high

• A处，low = 4， high = 5， low < high， 继续循环A：

• B处，high不断递减，直至high=4 等于 low，不满足 low < high，跳出B循环：

            pivot
              ↓
  2  1  4  3  5  7  8  6  9
              ↑
             low  
             high

• 因为low和high已经重合，所以在接下来的C、D、E操作中序列均未发生变化

• A处，low=4, high = 4, 不满足 low < high, 跳出A循环，最后返回low=4，即为pivot所在位置；

所以第1趟排序下来之后，序列会变成 {2, 1, 4, 3, 5, 7, 8, 6, 9}；然后再对子序列{2, 1, 4, 3} 和 {7, 8, 6, 9} 做同样的操作即可完成整个排序。

对于partition方法中的low和high，可以这样理解：在low左边的记录都都小于等于枢轴pivot，在high右边的记录都大于等于枢轴pivot，那么当low和high重合时，则表示已经分割完毕，重合的位置（即low的值）就是枢轴pivot的位置。

快速排序的优化

(1) 枢轴的选取方式的优化：
枢轴的选取方式有：(1) 固定位置选取；(2) 随机位置选取； (3) 三值取中法 等

固定位置选取：选取当前序列的第一个元素或者最后一个元素作为枢轴，上面的算法的枢轴选取方式即为固定位置选取。该方法不是一个好的选取方案，因为当整个序列有序时，每次分割(partition)操作只会将待排序序列减1，此时为最坏情况，算法复杂度沦为O(n^2)。然而，在待排序的序列中局部有序是相当常见的，所以固定位置选取枢轴不是一种好的选择。

随机位置选取：随机选取当前待排序序列的任意记录作为枢轴。由于采取随机，所以时间性能要强于固定位置选取。

三值取中法： 待排序序列的前(第一个位置)、中(中间位置)、后(最后一个位置)三个记录中的中间值(按大小排序)作为枢轴，比如:

9 1 7 5 2 8 6 3 4
↑       ↑       ↑
low    mid    high
前      中      后

由于 9 > 4 > 2； 因此将4作为此次分割(partition)操作的枢轴。
三值取中操作后，整个序列变为：

4 1 7 5 2 8 6 3 9
↑       ↑       ↑
low    mid    high
前      中      后

三值取中本质上就是随机位置选取，但是由于随机位置选取过程中需要用到随机种子来产生随机数，而三值取中不需要，所以三值取中要优于随机位置选取。

所以优化枢轴的选取方式时，我们选择三值取中的方式。

(2) 优化小数组时的排序方案：
当局部排序数组长度较小时，采用插入排序，而非快速排序，因为长度分割到够小后，继续分割的效率要低于直接插入排序。

(3) 略去不必要的交换
略去不必要的交换，将交换操作改为替换操作。
因为交换操作需要进行3次赋值操作，而替换操作只需要进行1次赋值操作。

Java实现

// 优化的快速排序
class OptimizedQuickSorter extends QuickSorter {

	/**
	 * 插入排序最大数组长度值
	 */
	private static final int MAX_LENGTH_INSERT_SORT = 7;

	/**
	 * 对数组arr[low...high]的子序列作快速排序，使之有序
	 */
	@Override
	protected void quickSort(int[] arr, int low, int high) {
		int pivotLoc; // 记录枢轴(pivot)所在位置
		if ((high - low + 1) > MAX_LENGTH_INSERT_SORT) {
			// 待排序数组长度大于临界值，则进行快速排序
			pivotLoc = partition(arr, low, high); // 将arr[low...high]一分为二,并返回枢轴位置

			quickSort(arr, low, pivotLoc - 1);// 递归遍历arr[low...pivotLoc-1]
			quickSort(arr, pivotLoc + 1, high); // 递归遍历arr[pivotLoc+1...high]
		} else {
			// 2. 优化小数组时的排序方案，将快速排序改为插入排序
			insertSort(arr, low, high); // 对arr[low...high]子序列进行插入排序
		}
	}

	/**
	 * 在arr[low...high]中利用三值取中选取枢轴(pivot)，将arr[low...high]分成两部分，
	 * 前半部分的子序列的记录均小于pivot，后半部分的记录均大于pivot;最后返回pivot的位置
	 */
	@Override
	protected int partition(int[] arr, int low, int high) {
		int pivot;
		pivot = medianOfThree(arr, low, high); // 1. 优化排序基准，使用三值取中获取中值
		while (low < high) { // 从数组的两端向中间扫描 // A
			while (low < high && arr[high] >= pivot) { // B
				high--;
			}
			// swap(arr, low, high); // 将比枢轴pivot小的元素交换到低位
			arr[low] = arr[high]; // 3. 优化不必要的交换，使用替换而不是交换  // C
			while (low < high && arr[low] <= pivot) { // D
				low++;
			}
			// swap(arr, low, high); // 将比枢轴pivot大的元素交换到高位
			arr[high] = arr[low]; // 3. 优化不必要的交换，使用替换而不是交换 // E
		}
		arr[low] = pivot; // F
		return low; // 返回一趟下来后枢轴pivot所在的位置
	}

	/**
	 * 通过三值取中(从arr[low...high]子序列中)获取枢轴pivot的值，让arr[low]变成中值;并返回计算的枢轴(pivot)
	 */
	private int medianOfThree(int[] arr, int low, int high) {
		int mid = low + ((high - low) >> 1); // mid = low + (high-low)/2, 中间元素下标

		// 使用三值取中得到枢轴
		if (arr[low] > arr[high]) { // 目的：让arr[low] <= arr[high]
			swap(arr, low, high);
		}
		if (arr[mid] > arr[high]) { // 目的：让arr[mid] <= arr[high]
			swap(arr, mid, high);
		}
		if (arr[mid] > arr[low]) { // 目的： 让arr[low] >= arr[mid]
			swap(arr, low, mid);
		}
		// 经过上述变化，最终 arr[mid]<=arr[low]<=arr[high]，则arr[low]为中间值
		return arr[low];
	}

	/**
	 * 对子序列arr[low...high]进行插入排序
	 */
	private void insertSort(int[] arr, int low, int high) {
		int i, j;
		int tmp;
		for (i = low + 1; i <= high; i++) { // 从下标low+1开始遍历,因为下标为low的已经排好序
			if (arr[i] < arr[i - 1]) {
				// 如果当前下标对应的记录小于前一位记录,则需要插入,否则不需要插入，直接将记录数增加1
				tmp = arr[i]; // 记录下标i对应的元素
				for (j = i - 1; j >= low && arr[j] > tmp; j--) {
					arr[j + 1] = arr[j]; // 记录后移
				}
				arr[j + 1] = tmp; // 插入正确位置
			}
		}
	}
}

演示
为了方便演示，我对上面代码中的分割操作partition方法的代码仍然进行了标注（分别标注为 A,B,C,D,E,F）。
对于待排序序列 {5, 1, 9, 3, 7, 4, 8, 6, 2}，我们来演示其第一趟排序过程：

low = 0， high = 8， high-low+1=9 > MAX_LENGTH_INSERT_SORT， 所以需要进行快速排序，接下来进行分割(partition)操作；

• 此时待排序序列：

  5  1  9  3  7  4  8  6  2
  ↑                       ↑
  low                    high

• 三值取中前：

  5  1  9  3  7  4  8  6  2
  ↑           ↑           ↑
  low        mid        high

• 三值取中后：

  pivot
  ↓
  5  1  9  3  2  4  8  6  7
  ↑           ↑           ↑
  low        mid        high

pivot = 5；

• A处，low = 0, high = 8, low < high, 进行A循环；

• B处，high的值不断递减，直至arr[high] = 4 小于pivot，跳出B循环：

  5  1  9  3  2  4  8  6  7
  ↑              ↑
  low           high

• C处，arr[low] = arr[high]，将低位的值替换成高位的值：

  4  1  9  3  2  4  8  6  7
  ↑              ↑
  low           high

• D处，low的值不断递增，直至arr[low] = 9 大于 pivot，跳出D循环:

  4  1  9  3  2  4  8  6  7
        ↑        ↑
       low     high

• E处，arr[high] = arr[low]， 将高位的值替换成低位的值：

  4  1  9  3  2  9  8  6  7
        ↑        ↑
       low     high

• A处，low = 2, high = 5, low < high, 进行A循环；

• B处，high的值不断递减，直至arr[high] = 2 小于pivot，跳出B循环：

  4  1  9  3  2  9  8  6  7
        ↑     ↑
       low   high

• C处，arr[low] = arr[high]，将低位的值替换成高位的值：

  4  1  2  3  2  9  8  6  7
        ↑     ↑
       low   high

• D处，low的值不断递增，直至low = 4, high = 4, low == high，不满足 low < high，跳出D循环:

  4  1  2  3  2  9  8  6  7
           ↑
          low
          high

• 因为low和high已经重合，所以在接下来的E操作中序列未发生变化；

• A处，low=4, high = 4, 不满足 low < high, 跳出A循环；

• F处， arr[low] = pivot:

  4  1  2  3  5  9  8  6  7
              ↑
             low
             high

• 最后返回low = 4，即为pivot所在的位置。

所以这趟排序下来之后，序列会变成 {4 1 2 3 5 9 8 6 7}；然后再对子序列{4, 1, 2, 3} 和 {9, 8, 6, 7} 做同样的操作即可完成整个排序。

复杂度

时间复杂度：
时间复杂度为O(nlogn)，在对快速排序进行各种细节性的优化后，快速排序的性能大大提高，在一般条件下超越了其它排序方法，故得此名。

空间复杂度：
就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。

参考链接：
常见排序算法 - 快速排序 (Quick Sort)
三种快速排序以及快速排序的优化