快速排序算法(quick sort):
一.基本思想(分治)
先用一趟排序将原始数组分割成两个独立部分,其中一个部分都比另一个部分小,再继续对分成的两个部分分别进行快速排序,整个过程递归进行,最后整个数组成为有序序列。
二.基本步骤
1. 从数列中挑出一个元素,作为“基准”(pivot),[随机取三个数,再取这三个数中的中值]或者[取第一,最后,中间再取中值];
2. 分区操作:重排数列,比基准值小的全部放在基准值前面,比基准值大的全部放再基准值后面(相同的数放在任意一边),分区结束后该基准值就在该数列的中间位置。
3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形是,数列的大小是0 or 1,也是最终别排序好了的。每次迭代中它至少会把一个元素摆到它的最后位置去。
三.时间复杂度和稳定性
1.时间复杂度:
若每次分裂都在列表*,将会重复分裂 log n 次。n个数都要与基准值比较大小,进行N次
所以最优时间复杂度是O(nlogn) ;
最坏的情况下,分成一个长度为 0 和(n-1)的两个数列,(n-1)数列分成 0 和(n-2),以次类推
最坏时间复杂度是O(n ^2)
2.稳定性:不稳定
四.python实现
def quick_sort(alist,start,end):
#递归的退出条件
if start >= end:
return
#设定起始元素为基准值
mid = alist[start]
#low为从左边开始移动的游标,high为从右边开始移动的游标
low = start
high = end
while low < high:
#两个游标不重合,high所指的数比基准值大,high往左移
while low < high and alist[high] >= mid:
high -= 1
# 将high指向的元素放到low的位置上
alist[low] = alist[high]
# 如果low与high未重合,low指向的元素比基准元素小,则low向右移动
while low < high and alist[low] < mid:
low += 1
# 将low指向的元素放到high的位置上
alist[high] = alist[low]
# 退出循环后,low与high重合,此时所指位置为基准元素的正确位置
# 将基准元素放到该位置
alist[low] = mid
# 对基准元素左边的子序列进行快速排序
quick_sort(alist, start, low-1)
# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low+1, end)
alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)