Python实现快速排序算法及去重的快速排序的简单示例
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用。
该方法的基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
现在通过一个实例来说明快排。
比如有一个数组:
62453
第一步:选取一个基准数,不要被这个名词吓到了,你可以把它看作是一个比较大小的数,因为排序就是比较大小,
比如我选取最后一个数3为基准数,依次把数组的数和3比较,比3小的放左边,比3大的放右边,这样有如下结果:
23645
第二步:判断区间个数,经过第一步后左边区间只有一个数了,没有数字再和它比较了,因此不需要重复操作,右边区间还有:
645
重复第一步,选取5作为基准数,得到比较结果:
456
这样左右两边区间都只有一个数了,这就标志着排序完成,最后把所有区间合并就得到排序结果:
23456
defquick_sort(array): less=[];greater=[] iflen(array)<=1: returnarray pivot=array.pop() forxinarray: ifx<=pivot:less.append(x) else:greater.append(x) returnquick_sort(less)+[pivot]+quick_sort(greater) list=[2,4,2,6,7,8,1]
printquick_sort(list)
[1,2,2,4,6,7,8]
相比C、C#、JAVA之类的是不是简单多了^.^
TIP:去重的快速排序
如下,只需要把集合修改为单值元素,这里我们使用Python3来演示:
#-*-coding:utf-8-*- importrandom L=[2,3,8,4,9,5,6,5,6,10,17,11,2] defqsort(L): iflen(L)<2:returnL pivot_element=random.choice(L) small=[iforiinLifi<pivot_element] #medium=[iforiinLifi==pivot_element] large=[iforiinLifi>pivot_element] returnqsort(small)+[pivot_element]+qsort(large) print(qsort(L))
输出:
[2,3,4,5,6,8,9,10,11,17]
也可以直接使用,集合(set)进行排序和去重.
mylist=list(set(L))#集合自动排序字符串