超级大牛用最简单的方法实现python全部八大排序算法

1.冒泡排序

比较相邻的元素大小,将小的前移,大的后移,就像水中的气泡一样,最小的元素经过几次移动,会最终浮到水面上。

def bubble(list):

for i in range(len(list)):

for j in range(0,len(list)-1-i):

if list[j] > list[j+1]:

list[j],list[j+1]=list[j+1],list[j]

if name == 'main':

list1 = [2,3,5,7,8,9,6,54,1,42]

bubble(list1)

print(list1)

2.插入排序

将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。

def insertsort(list):

if list != None:

if len(list) == 1:

pass

else:

for i in range(1,len(list)):#start with second item.

temp = list[i]

for j in range(i):

if list[j]>list[i]:

for k in range(i,j,-1):#

list[k]= list[k-1]

list[j] = temp

if name == 'main':

list1 = [3,2,7,5,8,9,6,54,1,42]

insertsort(list1)

print(list1)

3.归并排序

归并排序也称合并排序,是分治法的典型应用。分治思想是将每个问题分解成个个小问题,将每个小问题解决,然后合并。

具体的归并排序就是,将一组无序数按n/2递归分解成只有一个元素的子项,一个元素就是已经排好序的了。然后将这些有序的子元素进行合并。python有趣吗?好玩吗?想学吗?这里小编创建了一个python学习交流群:308754087 里面也会不定时分享关于Python的免费学习资料,欢迎想学习的小伙伴的加入,python有你更精彩!!嘿嘿!

合并的过程就是 对 两个已经排好序的子序列,先选取两个子序列中最小的元素进行比较,选取两个元素中最小的那个子序列并将其从子序列中

去掉添加到最终的结果集中,直到两个子序列归并完成。

代码如下:

4.快速排序

(1)这里实现第一轮排序,不妨称第一个元素为锚

(2)i,j分别指向待排序序列的第一和最后一个元素

(3)j与锚比较,若大于锚则左移,直到小于锚的元素停下,与i指向元素交换,i后移

(4)接着,i与锚比较,若小于则右移,直到大于锚的元素停下,与j指向的元素交换,j前移,

(5)i,j交替移动,i==j时,锚temp到达最终位置。

L = [90,89,78,67,56,45,34,23,12,0]

def first_sort(numbers,i,j):

temp = numbers[i]

while i!=j:

while itemp:

j = j - 1

numbers[i] = numbers[j]

i = i + 1

while i

i = i + 1

numbers[j] = numbers[i]

j = j - 1

numbers[i] = temp

return i

def quick_sort(numbers,i,j):

middle = first_sort(numbers,i,j)

quick_sort(numbers,i,middle-1)

quick_sort(numbers,middle+1,j)

if name=='main':

quick_sort(L,0,len(L)-1)

print

5.选择排序

从所有序列中先找到最小的,然后放到第一个位置。之后再看剩余元素中最小的,放到第二个位置……以此类推,就可以完成整个的排序工作。

def selectionsort(list):

if list != None:

for i in range(len(list)):

min = i

for j in range(i+1,len(list)):

if list[min] > list[j]:

min = j

if min != i:

list[min],list[i] = list[i],list[min]

if name == 'main':

list1 = [2,3,5,7,8,9,6,54,1,42]

selectionsort(list1)

print(list1)

6.基数排序

描述

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。代码实现:

7.希尔排序

先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。

test=[9,2,3,5,7]

def ShellSort(data,flag):

'''

data: list,to be sorted

flag: 0->asc,1->desc

return a new sorted list

'''

retData=[]

#copy data to retData

for item in data:

retData.append(item)

#sort retData

count=len(retData)

step=count/2;

while step>0:

i=0

while i

j=i+step

while j

t=retData.pop(j)

k=j-step

#asc

if flag==0:

while k>=0:

if t>=retData[k]:

retData.insert(k+1, t)

break

k=k-step

if k < 0:

retData.insert(0, t)

#desc

elif flag==1:

while k>=0:

if t

retData.insert(k+1, t)

break

k=k-step

if k

retData.insert(0, t)

j=j+step

i=i+1

step=step/2

return retData

data=ShellSort(test,0)

print 'Asc:',data

data=ShellSort(test,1)

print 'Desc:',data

8.堆排序 ( Heap Sort )

“堆”的定义:在起始索引为 0 的“堆”中:

节点 i 的右子节点在位置 2 * i + 24) 节点 i 的父节点在位置 floor( (i – 1) / 2 ) : 注 floor 表示“取整”操作

堆的特性:

每个节点的键值一定总是大于(或小于)它的父节点

“最大堆”:

“堆”的根节点保存的是键值最大的节点。即“堆”中每个节点的键值都总是大于它的子节点。

上移,下移 :

当某节点的键值大于它的父节点时,这时我们就要进行“上移”操作,即我们把该节点移动到它的父节点的位置,而让它的父节点到它的位置上,然后我们继续判断该节点,直到该节点不再大于它的父节点为止才停止“上移”。

现在我们再来了解一下“下移”操作。当我们把某节点的键值改小了之后,我们就要对其进行“下移”操作。

方法:

我们首先建立一个最大堆(时间复杂度O(n)),然后每次我们只需要把根节点与最后一个位置的节点交换,然后把最后一个位置排除之外,然后把交换后根节点的堆进行调整(时间复杂度 O(lgn) ),即对根节点进行“下移”操作即可。 堆排序的总的时间复杂度为O(nlgn).

代码如下:

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180105A0ZX6400?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券