Leetcode 215 Kth Largest Element in an Array & 912 Sort an Array

Quick Select and Quick Sort

原题

解答思路

这两道题都涉及到一个重要的排序思想：快速排序。而快速排序的核心就是快速选择算法。

对于一个无序的数组，我们要如何找到第k大的元素呢？

对于一个递增的数组，第k大的元素的下标应该是n-k。那么我们的想法就是，通过调整数组，对于下标为n-k处的值，左部的数都比它小，右部的数都比它大，这样的话，自然就找到了第k大的数。根据以上的思路，我们可以得到一个基于分治思想的快速选择算法：

那么对于数组nums，我们首先随机选择一个数pivot，然后进行调整，将那些<= pivot的元素都放在pivot左侧，将>= pivot的元素都放在pivot右侧，从而确定pivot的位置idx。

然后根据idx与n-k的关系进行讨论

如果idx == n-k，那么说明pivot即为第k大的元素
如果idx > n-k，那么说明pivot要比目标元素更大，目标元素应该是在idx的左部[left,idx-1]
如果idx < n-k，那么说明pivot要比目标元素更小，目标元素应该是在idx的右部[idx+1, right]

下面给出快速选择算法的代码

func partition(nums[]int, left, right int) int {
    /* 
        rand.Intn(n int) int
        返回一个[0, n-1]的随机int
    */
    // 随机指定一个pivot 问题点#[1]
    idx := left + rand.Intn(right-left+1)
    pivot := nums[idx]

    // 为了方便遍历，交换nums[idx]和nums[left]
    nums[idx], nums[left] = nums[left], nums[idx]

	// 需要判明这个范围内的数字与pivot的大小关系从而确定pivot位置
    i, j := left+1, right  
    for {
        // 问题点#[2] #[3]
        for i <= j && nums[i] < pivot {
            i++
        }

        for i <= j && nums[j] > pivot {
            j--
        }

        if i > j {
            break
        }

        // 此时nums[i] >= pivot >= nums[j]
        // 进行交换并移动到新位置
        nums[i], nums[j] = nums[j], nums[i]
        i++
        j--
    }
	
    // 问题点#[4]
    nums[left], nums[j] = nums[j], nums[left]

    return j
}

func findKthLargest(nums []int, k int) int {
    n := len(nums)
    
    targetIdx := n-k    // 递增顺序下，第K大元素的位置

    left, right := 0, n-1 // 闭区间[0, n-1]
    for {
        pivotIdx := partition(nums, left, right)
        // 进行一次划分，左部是<=pivot的元素，右部是>=pivot的元素

        if pivotIdx == targetIdx {
            // 找到了对应位置的元素
            return nums[pivotIdx]
        } else if pivotIdx > targetIdx {
            // 此时pivot大于n-k处的元素
            // 目标元素在左部区间内
            right = pivotIdx-1
        } else {
            left = pivotIdx+1
        }
    }
}

接下来，说明几个细节问题。

1. 为什么要随机指定pivot元素，而不是固定以第一个或者最后一个元素作为pivot呢？

这就涉及到划分均匀性的问题。如果说原数组本身就是有序的，我们假设是一个升序数组，此时选择第一个元素作为pivot，进行遍历时就会出现其左部没有更小的元素，其余元素全部都聚集在右部（类似的，如果选择最后一个元素作为pivot就会出现其余元素全都聚集在左部的问题）。此时再继续进行划分，每次分治的数据量并没有显著减少，复杂度相当于$n+(n-1)+(n-2)+\dots=O(n^2)$，出现了退化。而通过随机选择元素，能够保证相对均匀的划分，从而实现复杂度为$n+\frac{n}{2}+\frac{n}{4}+\dots = O(n)$

2. 为什么要判定nums[i] < pivot和nums[j] > pivot而非nums[i] <= pivot和nums[j] >= pivot？

这也是涉及到划分均匀性的问题。倘若原数组是由完全相同的元素组成的，采用后一种判定方式，在检查左部元素时会导致i直接移动到j+1的位置，进而导致j在最右的位置，从而导致pivot的位置也被判定在了最右的部分，其余元素全部集中在左部，导致了最不均匀的划分，算法退化为$O(n^2)$。而采用原本的nums[i] < pivot和nums[j] > pivot判定方式，则是会两个指针同时向中间移动，最后实现二分。

3. 为什么要判定 i <= j 而不是 i < j

这就涉及到正确性的问题了。对于nums = [2, 1, 3], 假设随机的pivot = nums[2] = 3，那么遍历前数组为[3, 1, 2]，此时i = 1, j = 2。

在第一个循环内，因为1 < 2 && nums[1] < 3所以i自增为2，随后因为2 < 2不成立而跳出循环。

在第二个循环内，因为2 < 2不成立，所以j没有变化，同时没有跳出循环（2 > 2不成立）。交换nums[2]和nums[2]，没有变化，移动到新位置后i = 3, j = 1，此时会跳出循环。交换nums[left]和nums[j]得到[1, 3, 2]，此时pivot右侧有元素小于pivot，结果是错误的。

如果使用i <= j的话，第一个循环在i=2 j=2时仍然可以进行，得到i=3 j=2跳出循环，交换nums[left]和nums[j]得到[2, 1, 3]，此时pivot左侧元素全部小于pivot，右侧无元素，是正确的划分。

4. 为什么要选择j的位置来交换放置pivot而不是i？

这是因为i有可能在[left+1, right+1]的位置，出现了越界问题（比如上面问题点3中j没有移动过的情况就会出现这一问题），而j只会在[left, right]之间，即使j=left交换也不会出错。

快速排序

在上述快速选择算法的基础上，就是快速排序算法。

了解了快速选择的思想之后，快速排序就很简单了。也就是每次我们随机的去从nums中选择的一个pivot，将pivot放置在正确的位置上后，再递归地去排序nums[:pivot]和nums[pivot+1:]。边界条件即为nums中仅有一个数字或者nums已经有序，即

func quickSort(nums []int) []int {
	if slices.IsSorted(nums) {
		return nums
	}
	
	i := partition(nums)
	quickSort(nums[:i])
	quickSort(nums[i+1:])
	
	return nums
}

其中partition()即为快速选择算法，只不过这里的left和right是0和len(nums)-1。

完整的快排代码如下

func partition(nums []int) int {
    n := len(nums)
    left, right := 0, n-1

    idx := left + rand.Intn(right-left+1)
    pivot := nums[idx]

    nums[idx], nums[left] = nums[left], nums[idx]
    
    i, j := left+1, right
    for {
        for i <= j && nums[i] < pivot {
            i++
        }

        for i <= j && nums[j] > pivot {
            j--
        }

        if i > j {
            break
        }

        nums[i], nums[j] = nums[j], nums[i]
        i++
        j--
    }

    nums[left], nums[j] = nums[j], nums[left]
    return j
}

func sortArray(nums []int) []int {
    if slices.IsSorted(nums) {
        return nums
    }

    i := partition(nums)
    sortArray(nums[:i])
    sortArray(nums[i+1:])

    return nums
}

快速选择与快速排序

快速排序

CATALOG

FEATURED TAGS