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

yipeiwu_com6年前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实现微信自动好友验证,自动回复,发送群聊链接方法

Python实现微信自动好友验证,自动回复,发送群聊链接方法

引言: 一开始二维码加群,但是呢,这个东西隔一段时间会过期,我需要 每隔一段时间去更新二维码,然后当群人数超过100人了,只能邀请进群, 这个时候就需要别人添加我为好友,然后我通过,打开...

Python实现网页截图(PyQT5)过程解析

方案说明 功能要求:实现网页加载后将页面截取成长图片 涉及模块:PyQT5 PIL 逻辑说明: 1:完成窗口设置,利用PyQT5 QWebEngineView加载网页地址,待网页加...

Python的log日志功能及设置方法

引入:Python中有个logging模块可以完成相关信息的记录,在debug时用它往往事半功倍 一、日志级别(从低到高): DEBUG :详细的信息,通常只出现在诊断问题上 INFO:...

Django中的Signal代码详解

Django中的Signal代码详解

本文研究的主要是Django开发中的signal 的相关内容,具体如下。 前言 在web开发中, 你可能会遇到下面这种场景: 在用户完成某个操作后, 自动去执行一些后续的操作. 譬如用...

python之PyQt按钮右键菜单功能的实现代码

python之PyQt按钮右键菜单功能的实现代码

实现效果如下图: 这篇文字主要写了两方面的内容: 第一是按钮的自定义,第二是右键菜单的使用,不仅是按钮的右键菜单,其他一些控件的右键菜单也可以类似创建和使用。 关于右键菜单则是QMe...