【学习笔记】手写快速排序，难点在哪里？

假设我们有如下数组，要用快速排序对其进行排序：
[10, 23, 15, 7, 18, 3, 15, 10, 28]
数组一共有9个元素。快速排序的过程基本如下：

1. 选取一个分割值；
2. 将小于等于分割值的元素排在它前面，大于等于分割值的元素排在它后面；
3. 确定该分割值在有序数列中的序号（index）；比如我们选18作为分割值，那么排序后（[3, 7, 10, 10, 15, 15, 18, 23, 28]），18的序号应该是6。
4. 使用递归分别对分割值前、分割值后的元素进行排序。

快速排序的整体思路并不难，但如果手写代码，里面有一些特殊情况需要考虑：

• 当选取的分割值为数组的最大值或者最小值；
• 当数组里面有相等的元素。

快速排序分析

上面提到的第2、3步骤就是算法代码里面的partition。想象我们用左右两个光标，通过移动光标、跟分割值比较，来把小于等于分割值的元素排在它前面，将大于等于分割值的元素排在它后面。

当选取的分割值不是最大值或最小值

[10, 23, 15, 7, 28, 3, 15, 10, 18]

1. 18为分割值，移动到数组最末端；
2. 左光标从左往右，找到大于分割值的第一个元素（23），左光标从index 0移动到index 1；
3. 右光标从右到左，找到小于分割值的第一个元素（10），该元素index为7；
4. 将23跟10对调，数组变成[10, 10, 15, 7, 28, 3, 15, 23, 18]；
5. 左光标继续往右移动，找到大于分割值的下一个元素（28），左光标从index 1移动到index 4;
6. 右光标继续往左移动，找到小于分割值的下一个元素（15），右光标从index 7移动到index 6；
7. 将28跟15对调，数组变成[10, 10, 15, 7, 15, 3, 28, 23, 18]；
8. 左光标继续往右移动，找到大于分割值的下一个元素（28），左光标从index 4移动到index 6；
9. 右光标继续往左移动，找到小于分割值的下一个元素（3），右光标从index 6移动到index 5；
10. 此时，左光标的index大于右光标的index，停止移动；
11. 此时，左光标前面的元素，均小于等于分割值，左光标后面的元素均大于等于分割值；
12. 将分割值18与左光标所指的28对调（注意这里，分割值是跟左光标所指的元素对调），数组变成[10, 10, 15, 7, 15, 3, 18, 23, 28]；
13. 左光标的index就是我们要找的分割值的最终序号。也就是说，18这个分割值，在最终排序后的数组里面，index一定是6。
14. 最后使用递归，对序号[0 ~ 5]、[7 ~ 8]的数组元素进行快速排序。

当选取的分割值为最大值

[10, 23, 15, 7, 18, 3, 15, 10, 28]

1. 选取28为分割值；
2. 左光标，从左往右，寻找大于28的第一个元素，寻找失败，光标移动到数组最末端（index = 8）;
3. 右光标，从右到左，寻找小于28的第一个元素（10），该元素index = 7；
4. 但因为左光标的index大于右光标的index，左右光标所指的元素不对调，将分割值与左光标所指的28对调；这里要对调的原因在于，通过后面的分析，我们可以得出一个结论，无论选取的是不是最大值最小值，分割值都是跟左光标所指的元素对调。这样方便代码书写，减少代码里面的特殊情况讨论。
5. 分割值28的最终序号就是index 8；
6. 使用递归，对序号[0 ~ 7]的数组元素进行快速排序。

当选取的分割值是最小值

[10, 23, 15, 7, 18, 3, 15, 10, 28]

1. 选取10作为分割值，并将10移动到数组最末端，数组变成[28, 23, 15, 7, 18, 3, 15, 10, 10]；
2. 左光标，从左往右，寻找大于10的第一个元素（28），左光标的index = 0；
3. 右光标，从右到左，寻找小于10的第一个元素（10），寻找失败，右光标移动到数组最左端；
4. 左右光标停止移动，分割值与左光标所指的28对调（又是左光标），左光标的index就是分割值10在数组最终排序后的index；
5. 使用递归，对序号[1 ~ 8]的数组元素进行快速排序。

当数组所有元素均相等

[10, 10, 10, 10, 10]

1. 任意选取一个index的元素作为分割值，并移动到数组最末端；
2. 左光标，从左往右，寻找大于10的第一个元素，寻找失败，左光标移动到index 4；
3. 右光标，从右到左，寻找小于10的第一个元素，寻找失败，右光标移动到数组最左端；
4. 左右光标停止移动，分割值与左光标所指的10对调（又是左光标）；
5. 使用递归，对序号[0 ~ 3]的数组元素进行快速排序。

代码实现

Java版本

partition是代码里面最tricky的部分。下面是Java版的代码实现，这个版本里面，分割值是随机挑选；如果不随机挑选，可以每次把数组的最后一个元素作为分割值，这样可以直接把choosePivot的代码删掉。

import java.util.Arrays;
import java.lang.Math;

public class QuickSort {
	// swap函数
	public static void swap(int[] arr, int first, int second) {
		int temp = arr[first]; 
		arr[first] = arr[second]; 
		arr[second] = temp; 
	} 
	
	// 随机选取分割值 choose a random pivot 
	public static void choosePivot(int[] arr, int start, int end) {
		int random = (int) (Math.random() * (end - start + 1)); 
		int randomPivot = start + random; 
		
		// 将随机选取的分割值，放在数组最末端
		swap(arr, randomPivot, end); 
	}

	// 寻找分割值的最终index
	public static int partition(int[] arr, int start, int end) {		
		// 左右光标
		int i = start, j = end - 1; 
		// 左右光标所指元素对调
		while(true) {
			// 左光标，从左往右，寻找大于分割值的元素 
			// 确保左光标的index，最大不能超过数组的最大index
			while(i < end && arr[i] <= arr[end]) {
				i++; 
			} 
			
			// 右光标，从右到左，寻找小于分割值的元素
			// 注意这里右光标的index最小可以到-1
			while(j >= 0 && arr[j] >= arr[end]) {
				j--; 
			}
			
			// 如果左光标的index > 右光标的index，就不左右对调，跳出这个while loop
			if(i > j) break; 
			// 否则，左右对调，继续寻找分割值两边的元素
			swap(arr, i, j); 
		} 
		
		// 将分割值与左光标所指的元素对调
		swap(arr, end, i); 
		// return左光标的index
		return i; 
	}
	
	// quick sort函数
	public static void quickSort(int[] arr, int start, int end) {
		// 递归的base condition
		if(start >= end) return; 

		// 随机选取分割值
		choosePivot(arr, start, end); 
		
		// 寻找分割值的最终index
		int i = partition(arr, start, end); 

		// 使用递归，对分割值左右的数组元素进行快速排序
		quickSort(arr, start, i - 1);
		quickSort(arr, i + 1, end); 
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {15, 3, 23, 26, 28, 26, 15, 3, 29, 34}; 
		System.out.println("Before quick sort: " + Arrays.toString(arr)); 

		quickSort(arr, 0, arr.length - 1); 

		System.out.println("After quick sort: " + Arrays.toString(arr)); 
	}
}
复制代码

JavaScript版本

function swap(arr, left, right) {
    let temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

function partition(arr, start, end) {
    let left = start;
    let right = end - 1;

    while (true) {
        while (left < end && arr[left] <= arr[end]) left++;

        while (right >= start && arr[right] >= arr[end]) right--;

        if (left > right) break;
        swap(arr, left, right);
    }

    swap(arr, end, left);
    return left;
}

function quickSort(arr, start, end) {
    if (start >= end) return;

    let i = partition(arr, start, end);

    quickSort(arr, start, i - 1);
    quickSort(arr, i + 1, end);
}

let arr = [15, 3, 23, 7, 15, 19, 76, 32, 0, 21];

quickSort(arr, 0, arr.length - 1);
console.log("After sort: " + arr);
复制代码