快速排序Python版

175 27天之前 Python 算法

答案

def quick_sort(arr, low, high):
    if low < high:
        part_index = partition(arr, low, high)

        quick_sort(arr, low, part_index - 1)
        quick_sort(arr, part_index + 1, high)


def partition(arr, low, high):
    i = low - 1
    pivot = arr[high]

    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            arr[j], arr[i] = arr[i], arr[j]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]

    return i + 1

时间复杂度:

  • 最坏:O(n^2)
  • 平均:O(nlgn)
  • 最好:O(n)

答案解析

# coding: utf-8


def quick_sort(arr, low, high):
    # 继续排序的条件是low小于high
    if low < high:
        # 将数组分成左右两个区,并返回分区的位置
        part_index = partition(arr, low, high)

        # 递归排序左边的数组
        # 这里直接在arr上原地排序,所以不占用额外空间
        quick_sort(arr, low, part_index - 1)

        # 递归排序右边的数组
        quick_sort(arr, part_index + 1, high)


# 将数组按照基准值分割成两部分
def partition(arr, low, high):
    # 小于基准元素值的下标
    i = low - 1

    # 基准值取最后一个元素
    pivot = arr[high]

    # 从low到high范围内扫描数组
    for j in range(low, high):
        # 如果元素的值小于或等于基准值,
        # i下标增1,并且交换i和j为下标的元素值
        # 这样可保证下标小于等于i的所有元素值都小于pivot
        if arr[j] <= pivot:
            i = i + 1
            arr[j], arr[i] = arr[i], arr[j]

    # 扫描完成后,交换i+1元素与基准元素的位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]

    # 返回分割点位置
    # 上面的步骤完成后,元素值分布就变成:
    #  下标     | 值
    #  <= i    |  <= pivot
    #  i + 1   |  =  pivot
    #  > i + 1 |  >  pivot
    return i + 1


arr = [1, 5, 3, 9, 6, 7, 8, 2, 3]
quick_sort(arr, 0, len(arr) - 1)

# 打印:[1, 2, 3, 3, 5, 6, 7, 8, 9]
print(arr)