数据分析师

您的位置:首页 > 技术干货 > Python实现快速排序算法及去重的快速排序的简单示例

Python实现快速排序算法及去重的快速排序的简单示例

收藏

来源: CDA数据分析师 | 发布时间:2017-12-07 12:48:25

Python实现快速排序算法及去重的快速排序的简单示例

quick sort快速排序是一种再基础不过的排序算法,使用Python代码写起来相当简洁,这里我们就来看一下Python实现快速排序算法及去重的快速排序的简单示例:

快速排序由于排序效率在同为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)) #集合自动排序字符串


数据分析师 Python

  CDA大数据分析圈是国内第一个汇聚大数据全面资源、数据人必备的APP。CDA整合了近千个大数据相关专业网站及媒体来源,汇聚了数百场国内大数据活动与会议,数千名名技术大牛、行业领袖,以及总结了最系统的优质学习课程资源。在这里,你可每天接触到最新行业资讯、前沿技术干货等信息;你可参与CDA俱乐部活动、各类大型会议,亲身与大牛接触,获得实务经验。你也可在专业课堂上与国内顶尖讲师进行交流切磋,最有效规划自身大数据职业发展。
  CDA大数据分析圈是数据人的家园,圈子里,资源流通,共享智慧,合作发展。CDA以“创新、开放、分享”的理念,期待你的加入!

分享到:

CDA数据分析师周边