排序算法之快速排序

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
步骤为：
1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

快速排序分析

排序算法之快速排序

代码实现：

# coding = utf-8
# 记录排序次数
i = 0

def quick_sort(alist, start=None, end=None):
if start is None and end is None:
start = 0
end = len(alist) - 1
global i

# 终止条件
if start >= end:
return

# 保留基准元素
base_value = alist[start]
# 定义左右两个游标
left = start
right = end

while left < right:
# 移动右边游标，若基本元素大则继续移动，小则停止
while alist[right] > base_value and left < right:
right -= 1
# print("移动右边游标, left:{}".format(left))
# print("移动右边游标, right:{}".format(right))
else:
# 移动当元素到左边
alist[left] = alist[right]
# 移动左边游标，若基本元素小则继续移动，大则停止
while alist[left] < base_value and left < right:
left += 1
# print("移动右边游标, left:{}".format(left))
# print("移动右边游标, right:{}".format(right))
else:
# 移动当元素到右边
alist[right] = alist[left]
else:
alist[left] = base_value
i += 1
print("第{}次排序：".format(i), alist)
# 递归调用处理左边序列
quick_sort(alist, start, left - 1)
quick_sort(alist, right + 1, end)

# 最坏时间复杂度：n-1 + n-2 + ...+1 次数n O(n^2)
# 最优的时间复杂度：次数logn 每次执行n O(nlogn)
# 稳定性：稳定

if __name__ == "__main__":
alist = [54, 36, 93, 17, 77, 31, 44, 55, 20]
print("原始列表： ", alist)
quick_sort(alist)
print("最终列表: ", alist)

程序运行结果：

原始列表： [54, 36, 93, 17, 77, 31, 44, 55, 20]
第1次排序： [20, 36, 44, 17, 31, 54, 77, 55, 93]
第2次排序： [17, 20, 44, 36, 31, 54, 77, 55, 93]
第3次排序： [17, 20, 31, 36, 44, 54, 77, 55, 93]
第4次排序： [17, 20, 31, 36, 44, 54, 77, 55, 93]
第5次排序： [17, 20, 31, 36, 44, 54, 55, 77, 93]
最终列表： [17, 20, 31, 36, 44, 54, 55, 77, 93]

排序算法之快速排序

相关推荐