快速排序算法。
重复循环处理的步骤可以用循环或递归实现。
简介
- 从一个数列中挑选一个元素作为基准
- 开始排序，把所有小于该基准的数字放到它的左边，大于的放到它的右边
- 递归的把该基准左右的数字排序
快速排序
快速排序使用分开比较的方法获得与合并排序的同样的优势，而不是使用额外的存储空间。作为一个折中的方案，列表可能不会被分为两半。发生这种情况的时候，我们会看到性能下降。
快速排序会选择一个值，我们称为基准值，尽管有很多不同的方法去选择这个值，但我们只需选择列表中的第一个值。基准值的作用是分隔这个列表。在最终排序列表中，基准值所属的实际位置，通常被称为分割点，将用于将列表分隔为后续调用，即快速排序。
图12显示54作为我们的第一个基准值，即使我们已经看到这个例子几次了。我们知道54最终会在31的结束处。分隔过程将会在下一步发生。它会找到分割点，同时将其他项目移动到列表的适当一侧，小于或大于基准值。
分区首先定义两个位置标记，我们称为左基准和右基准，在列表中剩余数字的开始和结束处。(位置1和8)图。分区过程的目标是将相对于主元值偏移错误的项移动到分割点上。图13显示了我们找到54的位置时的这个过程。
我们首先递增左标记值直到找到一个大于基准值的值，我们递减右标记，直到找到一个值小于基准值。在这一点上，我们发现了两个与最终分割点不同的项目上。对于我们的例子，这里发生在93和20.现在我们交换这两个值，然后再次重复这个过程。
在右标记变得小于左标记的时候，我们停止。右标记现在就是分割点。基准值和分割点的值互相交换。基准值就在这个位置上，图14。此外，分割点左侧的所有项目都小于基准值，并且分割点所有右边的值都大于基准值。该列表可以在分割点分隔，并且可以在两边递归的调用快速排序。
quickSort函数调用递归函数quickSortHelper。quickSortHelper从与合并排序相同的基本情况开始。如果这个列表的长度小于或大于1，则它已经被排序，如果它更大，那么就会被分区和递归排序。分区函数实现前面描述的过程。
# -*- coding:utf-8 -*-
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1) #调用quickSortHelper
def quickSortHelper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last) #寻找分割点
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1 #左标记位置
rightmark = last #右标记
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue: #左标记递增
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >= leftmark: #右标记的递减
rightmark = rightmark - 1
if rightmark < leftmark: #右边的位置小于左边的位置时
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)
打断点，首先执行。
s1
跳到quickSortHelper。
s2
s3 寻找分割点
s4 跳到寻找分割点的函数
s5 左标记 leftmark=1
s6右标记 rightmark=8
s7 done=False
s8 while not False: True
s9 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: #左标记递增
s10 leftmark+=1
s11 又执行 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: #左标记递增
这个时候，alist[2]=93>54。 这个while条件为假，下面的leftmark+=1就不执行了，下一步执行下面的一个while
s12 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: #右标记的递减
此时 alist[8]=20<54 所以该条件下的rightmark = rightmark - 1就不执行了。
s13 if rightmark < leftmark: #右边的位置小于左边的位置时 为假 8<2
下一步执行else
s14 temp = alist[leftmark]=93
s15 alist[leftmark] = alist[rightmark]=20
s16 alist[rightmark] = temp=93
这个时候就将左边大于基准的值和右边小于基准的值进行替换。
s17 又跳到了while not done循环
s18 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: #左标记递增为真。执行循环下面的 leftmark = leftmark + 1
s19 leftmark = leftmark + 1 4
s20 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: #左标记递增这个时候为假，跳出这个循环 77<=54 假
s21 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 真
s22 rightmark = rightmark - 1 7
s23 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 真 55>54
s24 rightmark = rightmark - 1 6
s25 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 假 44>=54
s26 判断 if rightmark < leftmark: 6>4 假
s27-29 进入 else的值的替换 左边的77和右边的44替换
s30 while not done 真
s31 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 44<54 真
s32 leftmark = leftmark + 1 5
s33 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 31<54 真
s34 leftmark = leftmark + 1 6
s35 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 77<54 假 跳出循环
s36 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 真
s37 rightmark = rightmark - 1 5
s38 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 5>=6 假
s39 if rightmark < leftmark: 5<6 真
s40 done=True else就不执行了
s41 跳到 while not done 假，跳出这个大循环
s42 temp = alist[first]= 54 基准值
s43 alist[first] = alist[rightmark]=31
s44 alist[rightmark] = temp=54
s45 return rightmark 5
s46 跳到 quickSortHelper中的splitpoint = partition(alist,first,last) #寻找分割点 。 splitpoint=rightmark=5 寻找到的第一个分割点，然后对分割点左边的进行分隔
s46 quickSortHelper(alist,first,splitpoint-1)
[31, 26, 20, 17, 44]
[54, 77, 55, 93]`
s47 if first<last: 递归 first=0,last=4
s48 splitpoint = partition(alist,first,last) #寻找分割点 调用
s48 pivotvalue = alist[first] <class 'list'>: [31, 26, 20, 17, 44, 54, 77, 55, 93]
s49 leftmark = first+1 1 1-4之间找分隔点
s50 rightmark = last=4
s51 done = False
s52 while not done: 真
s53 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 26<31 真
s54 leftmark = leftmark + 1 2
s55 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 20<31 真
s56 leftmark = leftmark + 1 3
s57 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 17<31 真
s58 leftmark = leftmark + 1 4
s59 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 44<31 假 跳出循环
s60 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 真
s61 rightmark = rightmark - 1 3
s62 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 3>4 假
s63 if rightmark < leftmark: 3<4 真
s64 true
s65 while not done 假 跳出大循环
s66 temp = alist[first] 31
s67 alist[first]=alist[rightmark]
s68 alist[tighrmark] = temp 31
s69 rightmark 3
s70 splitpoint = partition(alist, first, last) =3
s71 if first < last: 0<2
s72 splitpoint = partition(alist, first, last) 寻找分割点
s73 pivotvalue = alist[first] <class 'list'>: [17, 26, 20, 31, 44, 54, 77, 55, 93]
s74 leftmark =1
s75 rightmark =2
s76 done = False
s77 while not done [17,26,20]
s78 while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 26<17 假
s79 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 20>17 真
s80 rightmark = rightmark-1 = 1
s81 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 真
s82 rightmark = rightmark-1 = 0
s83 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 假 0>1
s84 if rightmark < leftmark: 真
s85 done = True
s86 while not done 假
s87 temp = alist[first] 17
s88 list[first] = alist[rightmark]=17
s89 alist[rightmark] = temp 17
s90 rightmark 0
<class 'list'>: [17, 26, 20, 31, 44, 54, 77, 55, 93]
s91 splitpoint = partition(alist, first, last) =0
s92 quickSortHelper(alist, first, splitpoint - 1)
s93 if first < last: first 0 last -1 假，就不执行splitpoint = partition(alist, first, last)这个了，跳这个语句。
s94 quickSortHelper(alist, first, splitpoint - 1) 假了，执行完了，该考虑分割点右边的了。
s95 quickSortHelper(alist, splitpoint + 1, last) first 1, last 2
要分析quickSort函数，请注意，对于长度为n的列表，如果分区始终出现在列表的中间，则会出现log n次分区。为了找到分割点，需要根据基准值检测n个项目中的每一个值。结果是n log n。另外，在合并排序过程中不需要额外的内存。
不幸的是，在最坏的情况下，分割点可能不在中间，可能会在最左端或最右端，从而导致分隔不均匀。在这种情况下，对n个项目列表进行排序分为0个项目和一个n-1个项目的列表。然后，将n-1分隔为一个大小为0和一个大小为n-2的列表，依此类推，结果是一个
O(n^2)。
双路快速排序
把等于基准值的项目分散到左右的两个部分。有大量重复的值时，可以平分开。
# -*- coding:utf-8 -*-
import timeit
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1) #调用quickSortHelper
def quickSortHelper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last) #寻找分割点
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1 #左标记位置
rightmark = last #右标记
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue: #左标记递增
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >= leftmark: #右标记的递减
rightmark = rightmark - 1
if rightmark < leftmark: #右边的位置小于左边的位置时
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
alist = [54,54,54,17,77,31,31,31,20]
quickSort(alist)
print(alist)
t2=timeit.Timer('quickSort(alist)','from __main__ import quickSort,alist')
print('快速排序: %s s' % t2.timeit(number=1))
三路快速排序
小于基准值，等于基准值，大于基准值。不需要对等于基准值的元素进行重复的操作。
代码
代码1
#!/usr/bin/python
# -*- coding:utf-8 -*-
def QuickSort(arr):
less = []
privotList = []
more = []
if len(arr) <= 1:
return arr
else:
privot = arr[0] #将第一个值作为基准
for i in arr:
if i < privot:
less.append(i) #将小于第一个基准的放到less列表里面
elif i > privot:
more.append(i) #将大于第一个基准的放到more列表里面
else:
privotList.append(i)
less = QuickSort(less)
more = QuickSort(more)
return less + privotList + more
if __name__ == '__main__':
a = [9,2,4,6,7,8,1,5]
print QuickSort(a)
2：
#!/usr/bin/python
# -*- coding:utf-8 -*-
def quicksort(nums):
if len(nums) <= 1:
return nums
#小于基准的列表
less = []
#大于基准的列表
more = []
#基准数
base = nums.pop()
#对原始数组划分
for x in nums:
if x < base:
less.append(x)
else:
more.append(x)
#递归调用
return quicksort(less) + [base] + quicksort(more)
if __name__ == '__main__':
nums = [9,2,4,6,7,8,1,5]
print quicksort(nums)
基准的这个数可以是随机的。