# 排序算法python实现

+关注继续查看

Bubble Sort



1 def bubbleSort(data):
2 if len(data) < 2: return data
3 for i in range(0, len(data)-1):
4 m = i
5 for j in range(i+1, len(data)):
6 if data[m] > data[j]: m =j
7
8 if m != i:
9 data[i], data[m] = data[m], data[i]
10 return data

Insert Sort

1 def insertSort(data):
2 if len(data) < 2: return data
3 for i in range(1,len(data)):
4 print data
5 key = data[i]
6 j = i-1
7 while j >= 0 and key < data[j]:
8 data[j+1] = data[j]
9 j = j-1
10 data[j+1]= key
11 return data

Merge Sort

1 def mergeSort(data):
2 length = len(data)
3 if length < 2: return data
4 l = data[:length/2]
5 r = data[length/2:]
6
7 outL = mergeSort(l)
8 outR = mergeSort(r)
9
10 return merge(outL, outR)
11
12  def merge(l,r):
13 print l,r
14 data = []
15 while len(l)>0 and len(r)>0:
16 if l[0] > r[0]:
17 data.append(l.pop(0))
18 else:
19 data.append(r.pop(0))
20
21 if len(l) >0:
22 data.extend(l)
23 else:
24 data.extend(r)
25 return data

Heap Sort

1 def heapSort(input):
2 output = []
3 buildHeap(input)
4 print input
5 while input:
6 i = len(input)-1
7 input[0],input[i] = input[i],input[0]
8 output.append(input.pop())
9 if input:
10 maxHeapify(input,0)
11 return output
12
13  def maxHeapify(input, i):
14 if i <0:
15 return
16 left = 2*i+1 # because the i from 0, not 1
17   right = 2*i+2
18 largest = i
19 length = len(input)
20 if left < length:
21 if input[i]< input[left]: largest = left
22 if right < length:
23 if input[largest]< input[right]: largest = right
24 if largest != i:
25 input[i], input[largest] = input[largest], input[i]
26 maxHeapify(input,largest)
27
28 def buildHeap(input):
29 length = len(input)
30 if length < 2: return
31 nonLeaf = length/2
32 for i in range(nonLeaf,-1,-1):
33 maxHeapify(input,i)

Quick Sort

1 def partition(data, p, r):
2 i = p-1
3 cmp = data[r]
4 for j in range(p,r):
5 if data[j] < cmp:
6 i = i+1
7 if i <> j: data[i],data[j] = data[j],data[i]
8
9 if (i+1) <> r: data[i+1],data[r] = data[r],data[i+1]
10 return i+1
11 def randomPartition(data, p, r):
12 import random
13 i = random.randint(p,r)
14 data[i], data[r] = data[r], data[i]
15 return partition(data, p, r)
16
17 def quickSort(data, p, r):
18 if p < r:
19 q = partition(data, p, r)
20 #q = randomPartition(data, p, r)
21 quickSort(data, p, q-1)
22 quickSort(data, q+1, r)

1月重磅新书，Python、算法大咖升级，总有1本你爱的

2120 0
Python算法题解：动态规划解0-1背包问题
Python算法题解：动态规划解0-1背包问题
1041 0

1733 0
python链表冒泡排序、二叉树顺序递归遍历、顺序表的快排

1347 0
python实现插入排序算法

838 0
python实现DES加密算法和3DES加密算法
pyDes.py ############################################################################# # Documentation # #####...
1605 0
《数据结构与算法：Python语言描述》一导读

1616 0
【大创_社区划分】——PageRank算法的解析与Python实现

1102 0
+关注
5854

223

《2021云上架构与运维峰会演讲合集》

《零基础CSS入门教程》

《零基础HTML入门教程》