Python Python实现的排序算法    

下面是几种常用的排序算法的Python实现

冒泡排序

多次比较相邻的两个元素，若第一个比第二个大则交换，持续进行比较直到没有需要交换的元素为止

def bubbleSort(lists):

length = len(lists)

while length > 0:

i = 0

while i < (length-1):

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

lists[i],lists[i+1] = lists[i+1],lists[i]

i += 1

length = length - 1

print(lists)

#给出一个列表

ls = [1,9,2,8,3,7,4,6,5]

#调用函数

bubbleSort(ls)

运行结果：

选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素存放在序列的起始位置，直到全部待排序的数据元素排完

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)

ls = [91,99,92,98,93,97,94,96,95]

selectSort(ls)

运行结果

插入排序

将一个数据插入到已经排好序的有序数据中从而得到一个新的、个数加一的有序数据

实现方法一

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)

ls = [11,19,12,18,13,17,14,16,15]

insertSort(ls)

运行结果：

实现方法二

def insertSort2(num):

length = len(num)

for i in range(1,length):

tmp = num[i]

tmpi = i -1

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

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

tmpi = tmpi - 1

print(num)

ls = [21,29,22,28,23,27,24,26,25]

insertSort2(ls)

运行结果：

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序

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)

ls = [31,39,32,38,33,37,34,36,35]

result = quickSort(ls)

print(result)

运行结果：

归并排序

归并排序采用的分治法，将有序的序列合成一个序列，反之，将当前序列分成多个序列分别排序，依此方法类推，直到序列中只有一个元素为止，常用的归并排序为二路归并，即分成两个序列

import math

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) > 0 and 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

ls = [41,49,42,48,43,47,44,46,45]

result = mergerSort(ls)

print(result)

运行结果：