为什么经典快排先从右往左找 | LIXI.FUN

LIXI.FUN

做个有趣的人

0%

为什么经典快排先从右往左找

发表于

教科书的经典做法，总是选择 lo 作为基准点，lo 在 [lo, hi] 区间的左边，当跳出大的 while i < j 的时候，交换分界点 arr[x] 和 arr[lo] 的值，让基准点落在左右的分界点上，因为 arr[x] 要交换到左边，那就要求 arr[x] < arr[lo]，在这种情况下，只能选择，先从右往左找，具体原因，下面分析。

先从右往左找

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
def qsort(arr, lo, hi):

    if lo >= hi:
        return

    i = lo
    j = hi

    # 选择 lo 为基准点
    pivot = arr[lo]

    while i < j:

        while i < j and arr[j] >= pivot:
            j -= 1
        
        while i < j and arr[i] <= pivot:
            i += 1
        
        arr[i], arr[j] = arr[j], arr[i]
    
    arr[lo], arr[j] = arr[j], arr[lo]

    qsort(arr, lo, i - 1)
    qsort(arr, i + 1, hi)

代码里，L22 就是让基准点 arr[lo] 交换到分界点上。

在这里面，跳出 L12 的 while i < j 可以推出 i = j，即左右指针相遇点即为分界点。

1
arr[lo], arr[x] = arr[x], arr[lo]

其中的 x 就是 i 或 j 的最终值。

主要分析 arr[x] < arr[lo] ?。

L12 要跳出，真实跳出点为 L14 或 L17，因为只有 L14 和 L17 中才有对 i 和 j 的值的更新，下面各自进行讨论。

若在 L14 跳出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while i < j:

    # 上一次循环的结果
    # arr[i] < pivot, arr[j] > pivot
    while i < j and arr[j] >= pivot:
        j -= 1 # 若 j 进行自减后 等于 i，跳出大循环，根据上一次循环结果，则 arr[j] = arr[i] < pivot
    # 若不跳出大循环，仅上面顺利执行下来，则 arr[j] < pivot
    
    while i < j and arr[i] <= pivot:
        i += 1
    # 若不跳出大循环，仅上面顺利执行下来，则 arr[i] > pivot
    
    # arr[i] > pivot, arr[j] < pivot
    arr[i], arr[j] = arr[j], arr[i]
    # 交换过后，转到下一次循环的结果
    # arr[i] < pivot, arr[j] > pivot

根据上面代码块的 L4，L6 可知，arr[j] < pivot 符合 arr[x] < arr[lo] 的条件，可进行交换。

若在 L17 跳出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while i < j:

    while i < j and arr[j] >= pivot:
        j -= 1
    # 若不跳出大循环，仅上面顺利执行下来，则 arr[j] < pivot
    
    # 若在 L17 跳出，则说明上面两行可顺利执行
    while i < j and arr[i] <= pivot:
        i += 1 # 若 i 进行自增后 等于 j，跳出大循环，根据上面顺利执行的结果，则 arr[i] = arr[j] < pivot
    # 若不跳出大循环，仅上面顺利执行下来，则 arr[i] > pivot
    
    # arr[i] > pivot, arr[j] < pivot
    arr[i], arr[j] = arr[j], arr[i]
    # 交换过后，转到下一次循环的结果
    # arr[i] < pivot, arr[j] > pivot

根据上面代码块的 L5，L9 可知，arr[i] < pivot 符合 arr[x] < arr[lo] 的条件，可进行交换。

先从左往右找

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
def qsort(arr, lo, hi):

    if lo >= hi:
        return

    i = lo
    j = hi

    # 选择 lo 为基准点
    pivot = arr[lo]

    while i < j:

        while i < j and arr[i] <= pivot:
            i += 1

        while i < j and arr[j] >= pivot:
            j -= 1
        
        arr[i], arr[j] = arr[j], arr[i]
    
    arr[lo], arr[j] = arr[j], arr[lo]

    qsort(arr, lo, i - 1)
    qsort(arr, i + 1, hi)

首先说明，在基准点选择 lo 的情况下，先从左往右找，最终结果是不对的。

同样进行分析，主要还是跳出 L12 的 while i < j，真实跳出点为 L14 或 L17，各自进行讨论。

若在 L14 跳出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while i < j:

    # 上一次循环的结果
    # arr[i] < pivot, arr[j] > pivot
    while i < j and arr[i] <= pivot:
        i += 1 # 若 i 进行自增后 等于 j，跳出大循环，根据上一次循环结果，则 arr[i] = arr[j] > pivot
    # 若不跳出大循环，仅上面顺利执行下来，则 arr[i] > pivot

    while i < j and arr[j] >= pivot:
        j -= 1 
    # 若不跳出大循环，仅上面顺利执行下来，则 arr[j] < pivot
    
    # arr[i] > pivot, arr[j] < pivot
    arr[i], arr[j] = arr[j], arr[i]
    # 交换过后，转到下一次循环的结果
    # arr[i] < pivot, arr[j] > pivot

根据上面代码块的 L4，L6 可知，arr[i] > pivot 不符合 arr[x] < arr[lo] 的条件，不可进行交换。

若在 L17 跳出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while i < j:

    while i < j and arr[i] <= pivot:
        i += 1
    # 若不跳出大循环，仅上面顺利执行下来，则 arr[i] > pivot

    # 若在 L17 跳出，则说明上面两行可顺利执行
    while i < j and arr[j] >= pivot:
        j -= 1 # 若 j 进行自减后 等于 i，跳出大循环，根据上面顺序执行的结果，arr[j] = arr[i] > pivot
    # 若不跳出大循环，仅上面顺利执行下来，则 arr[j] < pivot
    
    # arr[i] > pivot, arr[j] < pivot
    arr[i], arr[j] = arr[j], arr[i]
    # 交换过后，转到下一次循环的结果
    # arr[i] < pivot, arr[j] > pivot

根据上面代码块的 L5，L9 可知，arr[j] > pivot 不符合 arr[x] < arr[lo] 的条件，不可进行交换。

观察可发现，先从左往右，得到的跳出点的值 arr[x] > pivot，如果交换的话可以往右交换，也就是说，基准点可以选择 arr[hi]，这样结果就是对的了。

关于随机基准点

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
def qsort(arr, lo, hi):

    if lo >= hi:
        return

    i = lo
    j = hi

    # 以此方式先随机选一个下标，再交换到 lo(hi)
    # 数值随机了，下面程序还是相当于使用 lo(hi)，无需进行改动
    rand = random.randint(lo, hi)
    arr[lo], arr[rand] = arr[rand], arr[lo]

    # 选择 lo 为基准点
    pivot = arr[lo]

    while i < j:

        while i < j and arr[i] <= pivot:
            i += 1

        while i < j and arr[j] >= pivot:
            j -= 1
        
        arr[i], arr[j] = arr[j], arr[i]
    
    arr[lo], arr[j] = arr[j], arr[lo]

    qsort(arr, lo, i - 1)
    qsort(arr, i + 1, hi)

结论

基准点 交换条件 顺序
arr[lo] arr[x] < arr[lo] 先从右往左找
arr[hi] arr[x] > arr[hi] 先从左往右找
觉得有收获就鼓励下作者吧