1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

func findKthLargest(nums []int, k int) int {
    
    var quickSelect func(int, int, int) int
    quickSelect = func(l, r, k int) int{
        // 循环终止条件是单个元素
        if l == r{
            return nums[l]
        }

        // 采用Hoare分区，双指针
        // 同时选用中间元素作为基准值
        i, j := l, r
        pivot := nums[(l+r)/2] 

        // 整个循环是从大往小找
        for{
            // 左指针停在第一个小于等于基准的值
            for nums[i] > pivot { i ++ }
            // 右指针停在第一个大于等于基准的值
            for nums[j] < pivot { j -- }
            // 指针相遇或相错就停止
            // 此时j是明确的最后一个大于等于基准的值
            // 但是i的位置不一定是明确的
            if i >= j { break }
            // 进行交换并且移动
            nums[i], nums[j] = nums[j], nums[i]
            i, j = i + 1, j - 1
        }

        // 此时的状态是这样的
        // 左区间 [l...j] 全部大于等于基准
        // 右区间 [j+1...r] 全部小于等于基准
        // j 是分界线，左侧数量为 j-l+1
        cnt := j - l + 1

        // 如果k在左侧区间，那去左边搜
        // 如果k在右侧区间，从右边搜剩余的
        if k <= cnt{
            return quickSelect(l, j, k)
        }else{
            return quickSelect(j+1, r, k-cnt)
        }
    }

    return quickSelect(0, len(nums)-1, k)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

func sortArray(nums []int) []int {
    
    var quickSort func(int, int)
    quickSort = func(l, r int) {
        // 递归终止条件：区间长度小于等于1时无需排序
        if l >= r {
            return
        }

        // 初始化双指针
        i, j := l, r
        // 选择中间元素作为基准值
        pivot := nums[(l+r)>>1] 

        for {
            // 移动左指针：寻找第一个 >= pivot 的元素（升序排列）
            for nums[i] < pivot { i++ }
            // 移动右指针：寻找第一个 <= pivot 的元素
            for nums[j] > pivot { j-- }
            
            // 当指针相遇或交叉时，分区完成
            if i >= j {
                break
            }

            // 交换这两个不符合顺序的元素
            nums[i], nums[j] = nums[j], nums[i]
            
            // 移动指针避免死循环
            i, j = i + 1, j - 1
        }

        /* 此时分区状态：
            [l ... j] 区间：所有元素 <= pivot
            [j+1 ... r] 区间：所有元素 >= pivot
            j 是左分区的最后一个元素的索引
        */

        // 递归排序左半区（注意保持j作为分界）
        quickSort(l, j)
        // 递归排序右半区
        quickSort(j+1, r)
    }

    quickSort(0, len(nums)-1)
    return nums
}