快速排序 | 白筱汐

前言

快速排序，是十大经典排序之一。它的时间复杂度为O(nlogn)。快速排序使用了“分而治之”的思想，使用这种思想的算法有二分查找、归并排序等。

“分而治之”是一种算法或问题解决策略，它将一个复杂的问题划分为更小、更简单的子问题，然后逐个解决这些子问题，最后将它们的解合并起来，得到原始问题的解。

解题思路

我们随机选取数组中的一个元素作为基准值，小于等于基准值的元素放到一个小数组，大于基准值的元素放到另一个小数组。然后再对小数组重复上面的操作，当小数组的元素只有一个时，我们认为它是已经排序的。

快速排序使用“递归”来实现。所以我们需要寻找“基准条件”和“递归条件”。
(ps:关键名词可以通过谷歌搜索或阅读《图解算法》来了解具体含义)

第一步：完成递归函数的整体思路代码

function quickSort(arr,low,high) {
    // 数组长度必须大于1，否则认为数组已经排序好了
    if (low < high) { 
        // 获取基准值的索引
        const povitIndex = partiton(arr,low,high); 
        // 对分割后的左右子数组继续划分
        quickSort(arr, low, povitIndex - 1);
        quickSort(arr, povitIndex + 1,high);
    }
    return arr
}

第二步：完成划分函数的具体代码，这一步是解决问题的关键步骤

假设数组的最后一个元素为基准值povit,设置一个指针为i，它从数组的最左边开始。遍历数组，当元素小于等于基准值时，把当前遍历到的元素与指针i对应的元素交换位置，之后指针后移一步。当遍历到数组的倒数第二个元素时，循环结束。此时所有索引小于i的元素都小于基准值，也就是指针左侧的元素都是小于基准值的，交换povit与指针i对应元素的值。最后返回的i就是下一次分割的基准值索引。

function partiton(arr, low, high) {
    // 设置指针i来寻找下次分割的基准值索引，它从最左边开始
    let i = low
    // 假设数组最后一个元素是基准值
    let povit = arr(high) 
    for (let j = i; j < arr.length - 1; j++) {
        // 小于等于基准值的元素放在前面
        if (arr[j] <= povit) {
            // 交换元素的位置
            swap(arr,i,j)
            i++
        }
    }
    // 交换指针i对应元素和基准值的位置
    // 指针i左侧的元素总是小于等于基准值，右侧的元素总是大于基准值
    swap(arr,i,high)
    // 分割完成，返回基准值的索引
    return i
}

function swap(arr,i,j) {
    const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

go语言完整代码实现如下：

func quickSort(arr []int, low, high int) []int {
	if low < high {
		pivotIndex := partition(arr, low, high)
		quickSort(arr, low, pivotIndex-1)
		quickSort(arr, pivotIndex+1, high)
	}
	return arr
}

func partition(arr []int, low, high int) int {
	i := low
	pivot := arr[high]
	for j := i; j < high; j++ {
		if arr[j] <= pivot {
			arr[j], arr[i] = arr[i], arr[j]
			i++
		}
	}
	arr[i], arr[high] = arr[high], arr[i]
	return i
}