笔记

学习了Go的语法之后上洛谷熟练一下，发现快排其实也有讲究

Quicksort

普通快排

随机选值或者选择最左边的值，设i、j两指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func quicksort(num []int, left, right int) {

    if  left >= right {
        return 
    }

    randIndex := left + rand.Intn(right-left+1)
    num[randIndex], num[left] = num[left], num[randIndex]

    pivot := num[left]
    i := left + 1
    for j := left + 1; j <= right; j++ {
        if num[j] < pivot {
            num[i], num[j] = num[j], num[i]
            i++
        }
    }

    num[i-1], num[left] = num[left], num[i-1]
    quicksort(num, left, i-1)
    quicksort(num, i, right)
}

双路快排

双路快排的重点就在于解决在相等元素众多时导致的复杂度退化的问题，可以减少递归纵深，是课堂上的常见版本

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
void quicksort(vector<int>& num, int left, int right) {
    if (left >= right) {
        return;
    }

    int randomIndex = left + rand() % (right - left + 1);
    swap(num[left], num[randomIndex]);

    int pivot = num[left];
    int i = left + 1;

    // 写法2，三路快排
    int j = right;
    while (true){
        while (i <= right && num[i] < pivot) i++; // 不能是num[i] <= pivot，保证两子树平衡，否则超时
        while (j >= left + 1 && num[j] > pivot) j--; // 详见http://coding.imooc.com/learn/questiondetail/4920.html
        if (i > j) break;
        swap(num[i], num[j]);
        i++;
        j--;
    }
    swap(num[left], num[j]); // j位置必然小于等于pivot
    
    quicksort(num, left, j - 1);
    quicksort(num, j+1, right);
}

三路快排

算法让[lt,gt]都等于pivot，在双路快排基础上再进一步减少了重复元素比对的复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void threeWayQuickSort(vector<int>& arr, int low, int high) {
    if (low >= high) return;

    int pivot = arr[low];
    int lt = low;    
    int gt = high;   
    int i = low + 1; 

    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr[lt], arr[i]);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            swap(arr[gt], arr[i]);
            gt--;
        } else {
            i++;
        }
    }

    threeWayQuickSort(arr, low, lt - 1);  
    threeWayQuickSort(arr, gt + 1, high); 
}

第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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package main

import (
	"bufio"
	"fmt"
	"math/rand"
	"os"
)

var (
	reader *bufio.Reader
)

func readInt() int {
	sign, result := 1, 0
	ch, _ := reader.ReadByte()

	for (ch < '0' || ch > '9') && ch != '-' {
		ch, _ = reader.ReadByte()
	}

	if ch == '-' {
		sign = -1
		ch, _ = reader.ReadByte()
	}

	for ch >= '0' && ch <= '9' {
		result = result*10 + int(ch-'0')
		ch, _ = reader.ReadByte()
	}

	return sign * result
}

func main() {
	var n, k int
	reader = bufio.NewReaderSize(os.Stdin, 1<<20)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	n = readInt()
	k = readInt()
	num := make([]int, n)
	for i := 0; i < n; i++ {
		var temp int
		temp = readInt()
		num[i] = temp
	}

	fmt.Fprintln(writer, quickSelect(num, 0, n-1, k))

}

func divide(num []int, left, right int) int {

	// 这里随机选择pivot之后，将pivot放到最左边，下面的i指针从left+1开始
	randIndex := left + rand.Intn(right-left+1)
	num[randIndex], num[left] = num[left], num[randIndex]

	// 这里选择使用for循环，相较于三路快排的写法更简短
	pivot := num[left]
	i := left + 1
	for j := left + 1; j <= right; j++ {
		if num[j] < pivot {
			num[i], num[j] = num[j], num[i]
			i++
		}
	}

	// 这里交换pivot到中间位置，i-1是最后一个小于pivot的位置，区间[i, right]
	// 是大于等于pivot的区间，因此交换到i-1位置，这样保证左边都是小于pivot的
	num[i-1], num[left] = num[left], num[i-1]
	return i - 1
}

func quickSelect(num []int, left, right, k int) int {
	if left == right {
		return num[left]
	}
	pivotIndex := divide(num, left, right)
	if pivotIndex == k {
		return num[pivotIndex]
	} else if pivotIndex > k {
		return quickSelect(num, left, pivotIndex-1, k)
	} else {
		return quickSelect(num, pivotIndex+1, right, k) // 这里不需要k-pivotIndex-1，因为左右区间取值未变
	}
}

说些什么吧！

gitalk