Python实现快速排序算法及去重的快速排序的简单示例-Python Tutorial-php.cn

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

该方法的基本思想是：

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

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

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

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

比如有一个数组：

6 2 4 5 3

Copy after login

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

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

2 3 6 4 5

Copy after login

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

6 4 5

Copy after login

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

4 5 6

Copy after login

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

2 3 4 5 6

Copy after login

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]

Copy after login

print quick_sort(list)

Copy after login

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

Copy after login

相比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))

Copy after login

输出:

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

Copy after login

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

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

Copy after login

Related labels：

python Quick sort sort algorithm

source：php.cn

Previous article：Linux上安装Python的PIL和Pillow库处理图片的实例教程 Next article：Python中的字符串查找操作方法总结

Statement of this Website

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn