常见6种排序算法的PYTHON实现

常用排序算法的Python实现

相关代码如下（直接拷贝就可以用了）：

import random

import math

'''冒泡排序'''

'''多次比较相邻的两个元素

若第一个比第二个大则交换

持续进行比较直到没有需要交换的元素为止'''

def bubbleSort(num):

length=len(num)

while length>0:

for i in range(length-1):

if num[i]>num[i+1]:

num[i],num[i+1]=num[i+1],num[i]

length=length-1

pass

print(num)

return num

'''选择排序'''

'''每一次从待排序的数据元素中选出最小（或最大）的一个元素

存放在序列的起始位置

直到全部待排序的数据元素排完'''

def selectSort(num):

length=len(num)

for i in range(length):

tmpNum=i

for j in range(i,length):

if num[tmpNum]>num[j]:

num[tmpNum],num[j]=num[j],num[tmpNum] print(num)

return num

'''插入排序'''

'''将一个数据插入到已经排好序的有序数据中

从而得到一个新的、个数加一的有序数据'''

'''实现方法一'''

def insertSort(num):

length=len(num)

for i in range(1,length):

tmp=num[i]

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

if num[j]>tmp:

num[j+1],num[j]=num[j],num[j+1] print(num)

return num

'''实现方法二'''

def insertSort2(num):

length=len(num)

for i in range(1,length):

tmp=num[i]

tmpi=i-1

while tmpi>=0and num[tmpi]>tmp:

num[tmpi],num[tmpi+1]=num[tmpi+1],num[tmpi]

tmpi=tmpi-1

pass

print(num)

return num

'''快速排序'''

'''通过一趟排序将要排序的数据分割成独立的两部分

其中一部分的所有数据都比另外一部分的所有数据都要小

然后再按此方法对这两部分数据分别进行快速排序'''

def quickSort(num):

length=len(num)

if length<=1:

return num

tmpi=random.randint(0,length-1)

tmp=num[tmpi]

left=[]

right=[]

for i in range(0,length):

if num[i]>tmp:

right.append(num[i])

else:

left.append(num[i])

return quickSort(left)+quickSort(right)

'''归并排序'''

'''归并排序采用的分治法，

将有序的序列合成一个序列，

反之，将当前序列分成多个序列分别排序，

依此方法类推，直到序列中只有一个元素为止，

常用的归并排序为二路归并，即分成两个序列'''

def mergerSort(num):

result=[]

length=len(num)

if length<=1:

return num

left=mergerSort(num[:math.floor(length/2)])

right=mergerSort(num[math.floor(length/2):])

while len(left)>0and len(right)>0:

if left[0]<=right[0]:

result.append(left.pop(0))

else:

result.append(right.pop(0))

if len(left)>0:

result.extend(left)

else:

result.extend(right)

return result

'''堆排序'''

'''堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，

它是选择排序的一种。

主要的过程分为建立堆、堆调整和堆排序。

建立堆：建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，

此处len是堆中元素的个数。'''

def createHeap(num):

length=len(num)

flag=1

for i in range(math.floor(length/2)-1,-1,-1):

if num[2*i+2]>num[i]and num[2*i+2]>num[2*i+1]:

num[2*i+2],num[i]=num[i],num[2*i+2]

num=handHeap(num,2*i+2)

else:

if num[2*i+1]>num[i]and num[2*i+1]>num[2*i+2]:

num[2*i+1],num[i]=num[i],num[2*i+1]

num=handHeap(num,2*i+1)

else:

num[i]=num[i]

return num

'''调整堆：利用的思想是比较节点i和它的孩子节点left(i),right(i)，

选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，

这是一个递归的过程。'''

def handHeap(num,head):

temp=2*head+1

tempHead=head

length=len(num)

while temp<length:

if num[tempHead]<num[temp]:

num[tempHead],num[temp]=num[temp],num[tempHead]

if temp+1<length and num[tempHead]<num[temp+1]:

num[tempHead],num[temp+1]=num[temp+1],num[tempHead] tempHead=temp

temp=tempHead*2+1

return num

'''堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，

将前面len-1个节点继续进行堆调整的过程，

然后再将根节点取出，这样一直到所有节点都取出。'''

def headSort(num):

length=len(num)

if length<=1:

return num

tempLength=length-1

num=createHeap(num)

while tempLength>0:

num[tempLength],num[0]=num[0],num[tempLength]

num[:tempLength]=handHeap(num[:tempLength],0)

tempLength=tempLength-1

return num

'''堆排序结束'''

if__name__=='__main__':

testlist=[34,31,35,21,43,53,37,94,54,26,51]

print(headSort(testlist))