数组排序——从荷兰国旗问题到快速排序

Python爬虫与算法

共 2983字,需浏览 6分钟

 ·

2023-05-31 18:25

  本文首先将会介绍荷兰国旗问题,再讲述如何从该问题过渡到快速排序。

荷兰国旗问题

  荷兰国旗问题(Dutch National Flag Problem)是由荷兰计算机科学家Edsger Dijkstra所提出,该问题的描述如下:

给定n个红、白、蓝三种颜色的小球,无序地排列在一起。对这些小球进行排序,使得所有相同颜色的球在一起,且颜色顺序依次为红、白、蓝。

因荷兰国旗的颜色从上到下分别为红、白、蓝,故该问题被称为荷兰国旗问题
  事实上,在Leetcode中,该问题又被描述为:

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。要求使用的空间复杂度为常数空间。

因此,荷兰国旗问题又被称为颜色分类问题
  针对该问题,其解决的算法采用双指针法。我们采用两个指针lowhigh,分别指向0和2,再使用变量mid对数量进行遍历。具体的步骤如下:

  • 若mid遍历到的位置为0,则和low处的元素交换,同时向右移动low和mid。

  • 若mid遍历到的位置为1,则不需要处理,只需向右移动mid。

  • 若mid遍历到的位置为2,则和high处的元素交换,交换后只把high向左移动,mid仍然指向原位置。

整个算法的示意图如下:

34cd67c72d6458bd5fb502ad967e7116.webp荷兰国旗问题的算法示意图
上述算法的Python代码如下:
def sort_colors(nums):
    low, high, mid = 0, len(nums)-10
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 2:
            nums[high], nums[mid] = nums[mid], nums[high]
            high -= 1
        else:
            mid += 1
    return nums


if __name__ == '__main__':
    numbers = [10102021]
    result = sort_colors(numbers)
    print(result)

输出结果如下:

[00011122

快速排序

  对于上述的荷兰国旗问题,我们可以将思路拓宽,用它来实现快速排序。
  对于数组array,我们取其切片,即从位置low到high的数组片段(包括位置low和high),我们使用类似于荷兰国旗问题的思路,先选择一个数字作为枢纽(pivot),再找到合适的位置,使其作为小于pivot的数字排列和等于pivot的数字排列的分割点(类似于荷兰国旗问题中的数字0和1的分割点位置low)。
  接着,我们再循环调用上述算法,实现整个数组(从位置0到长度-1的数组切片)的排序。
  上述算法的Python实现代码如下:

def partition(array, low, high):
    pivot = array[low]
    a, b, c = low, high, low
    while c <= b:
        if array[c] < pivot:
            array[a], array[c] = array[c], array[a]
            a += 1
            c += 1
        elif array[c] > pivot:
            array[b], array[c] = array[c], array[b]
            b -= 1
        else:
            c += 1
    return a


def quick_sort(array, low, high):
    if low < high:
        pi = partition(array, low, high)
        # Recursive call on the left of pivot
        quick_sort(array, low, pi - 1)
        # Recursive call on the right of pivot
        quick_sort(array, pi + 1, high)
    return array


if __name__ == '__main__':
    n = 13
    my_list = list(range(n))
    from random import shuffle
    shuffle(my_list)
    print('排序前:', my_list)
    result = quick_sort(my_list, 0, len(my_list)-1)
    print('排序后:', result)

输出结果如下:

排序前: [12, 8, 7, 3, 1, 0, 4, 2, 9, 6, 11, 10, 5]
排序后: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

注意,该算法的时间复杂度为O(nlogn),空间复杂度为O(1).
  另外,还有其它的快速排序的实现代码,如下:

def quick_sort(array):
    n = len(array)
    if n <= 1:
        return array
    pivot = array[n//2]
    left = [x for x in array if x < pivot]
    middle = [x for x in array if x == pivot]
    right = [x for x in array if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

但显然,该实现代码在空间复杂度上不如上一种。

总结

  近来ChatGPT大火,我们也尝试着用ChatGPT来实现快速排序,如下:

8612ac031399d2d5bb98ee16bebc5a66.webpChatGPT实现快速排序
  本文介绍了荷兰国旗问题,并将其扩展快速排序,并介绍了两种快速排序的算法,最后再用ChatGPT来实现快速排序。


参考文献

  1. 荷兰国旗问题: https://juejin.cn/post/6890141987988340749

  2. 颜色分类: https://leetcode.cn/problems/sort-colors/description/

  3. QuickSort:https://www.geeksforgeeks.org/quick-sort/


浏览 47
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报