伏龙阁资源网

Python实现快速排序算法及去重的快速排序的简单示例
站长资源 2024/11/25 佚名
2 0

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

现在通过一个实例来说明快排。

比如有一个数组：

6 2 4 5 3

第一步：选取一个基准数，不要被这个名词吓到了，你可以把它看作是一个比较大小的数，因为排序就是比较大小，

比如我选取最后一个数3为基准数，依次把数组的数和3比较，比3小的放左边，比3大的放右边，这样有如下结果：

2 3 6 4 5

第二步：判断区间个数，经过第一步后左边区间只有一个数了，没有数字再和它比较了，因此不需要重复操作，右边区间还有：

6 4 5

重复第一步，选取5作为基准数，得到比较结果：

4 5 6

这样左右两边区间都只有一个数了，这就标志着排序完成，最后把所有区间合并就得到排序结果：

2 3 4 5 6


def quick_sort(array):
  less = []; greater = []
  if len(array) <= 1:
    return array
  pivot = array.pop()
  for x in array:
    if x <= pivot: less.append(x)
    else: greater.append(x)
  return quick_sort(less) + [pivot] + quick_sort(greater)
list = [2,4,2,6,7,8,1]

print quick_sort(list)

[1, 2, 2, 4, 6, 7, 8]

相比C、C#、JAVA之类的是不是简单多了^.^

TIP：去重的快速排序
如下, 只需要把集合修改为单值元素,这里我们使用Python3来演示:

# -*- coding: utf-8 -*- 
  
import random 
 
L = [2, 3, 8, 4, 9, 5, 6, 5, 6, 10, 17, 11, 2] 
 
def qsort(L): 
  if len(L)<2: return L 
  pivot_element = random.choice(L) 
  small = [i for i in L if i< pivot_element] 
  #medium = [i for i in L if i==pivot_element] 
  large = [i for i in L if i> pivot_element] 
  return qsort(small) + [pivot_element] + qsort(large) 
 
print(qsort(L))

输出:

[2, 3, 4, 5, 6, 8, 9, 10, 11, 17]

也可以直接使用, 集合(set)进行排序和去重.

mylist = list(set(L)) #集合自动排序字符串

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
www.wwsws.com 伏龙阁资源网
39,976影音资源
44,792技术资源
21,817软件资源
651,128站长资源

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接