数组排序——从荷兰国旗问题到快速排序
共 2983字,需浏览 6分钟
·
2023-05-31 18:25
本文首先将会介绍荷兰国旗问题,再讲述如何从该问题过渡到快速排序。
荷兰国旗问题
荷兰国旗问题
(Dutch National Flag Problem)是由荷兰计算机科学家Edsger Dijkstra
所提出,该问题的描述如下:
给定n个红、白、蓝三种颜色的小球,无序地排列在一起。对这些小球进行排序,使得所有相同颜色的球在一起,且颜色顺序依次为红、白、蓝。
因荷兰国旗的颜色从上到下分别为红、白、蓝,故该问题被称为荷兰国旗问题
。
事实上,在Leetcode中,该问题又被描述为:
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。要求使用的空间复杂度为常数空间。
因此,荷兰国旗问题
又被称为颜色分类问题
。
针对该问题,其解决的算法采用双指针法。我们采用两个指针low
和high
,分别指向0和2,再使用变量mid
对数量进行遍历。具体的步骤如下:
若mid遍历到的位置为0,则和low处的元素交换,同时向右移动low和mid。
若mid遍历到的位置为1,则不需要处理,只需向右移动mid。
若mid遍历到的位置为2,则和high处的元素交换,交换后只把high向左移动,mid仍然指向原位置。
整个算法的示意图如下:
上述算法的Python代码如下:
def sort_colors(nums):
low, high, mid = 0, len(nums)-1, 0
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 = [1, 0, 1, 0, 2, 0, 2, 1]
result = sort_colors(numbers)
print(result)
输出结果如下:
[0, 0, 0, 1, 1, 1, 2, 2
快速排序
对于上述的荷兰国旗问题
,我们可以将思路拓宽,用它来实现快速排序。
对于数组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来实现快速排序,如下:
ChatGPT实现快速排序本文介绍了荷兰国旗问题,并将其扩展快速排序,并介绍了两种快速排序的算法,最后再用ChatGPT来实现快速排序。
参考文献
荷兰国旗问题: https://juejin.cn/post/6890141987988340749
颜色分类: https://leetcode.cn/problems/sort-colors/description/
QuickSort:https://www.geeksforgeeks.org/quick-sort/