快速排序、二分法以及一些变形的思考

Posted on Edited on In Views:
在golang源码中，用的比较多的排序算法是快速排序，快速排序的思想是将一个数组分割成两个数组，然后分别排序。查找方法中比较常用性能高的是二分法。这两个算法是必须很熟练掌握的。

快速排序

快排的时间复杂度不稳定，因为默认将第一个数字作为分割，大于这个数字放右边进行排序，小于这个数组放左边进行排序，将左边的循环，右边的循环，最后将左边，中间，右边加起来就得到结果，第一个数字的大小决定了排序的时间。最差的情况是o(n^2)最好的情况是o(nlogn)

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
func quickOrder(arr []int) []int {
    length := len(arr)
    if length < 2 {
        return arr
    }
    res := []int{}
    flag := arr[0]
    mid := []int{}
    right := []int{}
    left := []int{}
    mid = append(mid, flag)
    for i := 1; i < length; i++ {
        if arr[i] > flag {
            right = append(right, arr[i])
        } else if arr[i] < flag {
            left = append(left, arr[i])
        } else {
            mid = append(mid, arr[i])
        }
    }
    right = quickOrder(right)
    left = quickOrder(left)
    res = append(append(left, mid...), right...)
    return res
}

二分法查找

二分法查找可以快速的在一个数组中查询到某个数字的位置，思路是对半缩小区间，左边区间是0，右边区间是-1，比较中间值和目标值，如果大于目标值，则左边区间改为中值，如果小于目标值，则右边区间改为中值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func midsearch(arr []int, target int) int {
    length := len(arr)
    if length < 1 {
        return -1
    }
    left := 0            
    right := length
    for left < right {  // 必须满足的条件是左边小于右边
        mid := (left + right) / 2
        if arr[mid] > target {
            right = mid - 1          // 注意这里需要-1，该位置不等于就往后退一格
        } else if arr[mid] < target {
            left = mid + 1           // 注意这里需要+1，该位置不等于就往前走一格
        } else {
            return mid
        }
    }
    return -1
}

当没有元素时，则查找不到。

优化当查找不到元素，返回该元素如果在位置值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func midsearchBetter(arr []int, target int) int {
    length := len(arr)
    if length < 1 {
        return -1
    }
    left := 0
    right := length
    for left <= right {
        mid := (left + right) / 2
        if left == right {
            return mid
        }
        if arr[mid] > target {
            right = mid - 1
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            return mid
        }
    }
    return left + 1
}

二分法查找边界

变形：当有多个元素重复，如何找到左边界和右边界。思想是二分法的变形。

查找左边界的过程中，中值大于或等于目标值，将这个中值定位右侧，不减1，左侧方案不变，往前走一位，直到左边不小于右边，此时右边就是左边界。

查找右边界的过程中，由于中值计算会往下取整，所以中值需要加1，将中值往前移，当中值小于或者等于目标值，左侧等于中值，右侧方案不变，往后减一位，直到左侧不小于右侧，此时左侧就是右边界。

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
func midsearchmany(arr []int, target int) (firstleft int, lastright int) {
    length := len(arr)
    if length < 1 {
        return -1, -1
    }
    left := 0
    right := length
    for left < right {
        mid := (left + right) / 2
        if arr[mid] >= target {
            right = mid
        } else if arr[mid] < target {
            left = mid + 1
        }
    }
    firstleft = right

    left = 0
    right = length
    for left < right {
        mid := (left+right)/2 + 1
        if arr[mid] > target {
            right = mid - 1
        } else if arr[mid] <= target {
            left = mid
        }
    }
    lastright = left
    return
}

排序和查找的思想，可以用于快速查找定位某个数。

一般大量文件情况下，例如一亿个数字，大约占磁盘2G，一行一行读出来放到数组里面，大约占5G，可以通过号码排序，然后二分法查找，获取到index，获取到查询的结果。这个查询过程相比读到数组，一个一个便利查询快得多。这个过程需要注意提前分配好数组的长度。

二分法查找距离最大或者最小的数字

查找距离最大的数字，在很多地方会用到，例如在二维数组中，或者在MySQL的树的枝干节点中，保存的是叶子节点或者子节点的最小值，此时需要先通过二分法查找到具体的子节点，然后再到子节点中通过二分法查找。

例如一个二维数组模拟

1
[[1,2,3,4,5,6,7],[11,12,13,14,15,16,17],[22,23,24,27,28,29],[30,32,34,35,37,38,39]]

从中找到24这个数字，先找到一维数组，[22,23,24,27,28,29]，其实也就是在 [1,11,22,30]中找到离24最大的数字，也就是22

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
nums := []int{1, 10, 20, 30, 40, 50, 60, 70}
target := 0

if target > nums[len(nums)-1] {
    fmt.Println("find the number.", len(nums)-1)
}
length := len(nums)
start, end := 0, length-1
for start < end {
    mid := (start + end) >> 1
    if nums[mid] < target {
        start = mid + 1
    } else if nums[mid] > target {
        end = mid
    } else {
        fmt.Println("find the number.", mid)
        return
    }
    fmt.Println(start, end)
}
fmt.Println("find the number.", end-1)

同理，返回距离目标值的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func main() {
    nums := []int{1, 10, 20, 30, 40, 50, 60, 70}
    target := 75

    if target > nums[len(nums)-1] {
        fmt.Println("can not find the number.")
    }
    length := len(nums)
    start, end := 0, length-1
    for start < end {
        mid := (start + end) >> 1
        if nums[mid] < target {
            start = mid +1
        } else if nums[mid] > target {
            end = mid
        } else {
            fmt.Println("find the number.", mid)
            return
        }
        fmt.Println(start, end)
    }
    fmt.Println("find the number.", end)
}