0

关于这段快排代码,一直想不明白partition这个分区函数中的 a[low], a[j] = a[j], a[low]这段是什么意思。好像不用这句就可以分好区。

from typing import List
import random


def quick_sort(a: List[int]):
    _quick_sort_between(a, 0, len(a) - 1)


def _quick_sort_between(a: List[int], low: int, high: int):
    if low < high:
        # get a random position as the pivot
        k = random.randint(low, high)
        a[low], a[k] = a[k], a[low]

        m = _partition(a, low, high)  # a[m] is in final position
        _quick_sort_between(a, low, m - 1)
        _quick_sort_between(a, m + 1, high)


def _partition(a: List[int], low: int, high: int):
    pivot, j = a[low], low
    for i in range(low + 1, high + 1):
        if a[i] <= pivot:
            j += 1
            a[j], a[i] = a[i], a[j]  # swap
    a[low], a[j] = a[j], a[low]
return j
coolxc 2
2019-06-14 提问
1 个回答
1

已采纳

你这段代码的主元 pivot 是选择的第一个元素即 a[low],整理一下:

def partition(a, low, high):
    pivot, i = a[low], low
    
    for j in range(i + 1, high + 1):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    
    # 最后索引小于等于 i 的元素都是小于等于主元的(主元左边是小于等于主元),所以要交换并返回主元的索引
    a[low], a[i] = a[i], a[low]
    return i

具体循环不变式的证明可以看算法导论的相关章节。

撰写答案

推广链接