快速排序
算法思想
快速排序算法首先会在序列中随机选择一个基准值(pivot),然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别,再将其排列成以下形式:
[ 比基准值小] 基准值 [比基准值大]
接着,对两个“[ ]”中的数据进行排序之后,整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序,即使用递归的思想。
时间复杂度
时间复杂度
不稳定
https://www.cnblogs.com/onepixel/articles/7674659.html
栗子
代码实现
def quick_sort(data):
"""快速排序"""
if len(data) >= 2:
mid = data[len(data)//2]
left, right = [], []
data.remove(mid)
for num in data:
if num >= mid:
right.append(num)
else:
left.append(num)
return quick_sort(left) + [mid] + quick_sort(right)
else:
return data
def quick_sort(alist, first ,last):
if first >= last:
return
mid_value = alist[first]
low = first
high = last
while low < high:
while low < high and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]
while low < high and alist[low] < mid_value:
low += 1
alist[high] = alist[low]
alist[low] = mid_value
quick_sort(alist,first, low-1)
quick_sort(alist,low+1, last)
if __name__ == "__main__":
li = [1, 9, 6, 3, 8, 4, 7, 5, 2]
print(li)
quick_sort(li, 0, len(li)-1)
print(li)
《算法图解》这本书上的代码很好理解
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print (quicksort([10, 5, 2, 9, 3, 8, 5]))