各种排序方法

```#author: Jiang Hongfei <jianghongfei@gmail.com>

import random
import time
import logging

def isSorted(ml):
for i in range(len(ml) - 1):
if ml[i] > ml[i + 1]:
return False
return True

def swap(ml, m, n):
t = ml[m]
ml[m] = ml[n]
ml[n] = t

def bubbleSort(ml):
for m in range(len(ml) - 1):
for n in range(len(ml) - m - 1):
if ml[n] > ml[n + 1]:
swap(ml, n, n + 1)

def selectSort(ml):
for m in range(len(ml) - 1):
minIndex = m
for n in range(m + 1, len(ml)):
if ml[n] < ml[minIndex]:
minIndex = n
if minIndex != m:
swap(ml, minIndex, m)

def quickSort(ml, left = None, right = None):
def partition(ml, left, right):
counter = left
for m in range(left, right):
if ml[m] < ml[right]:
swap(ml, counter, m)
counter += 1
swap(ml, counter, right)
return counter

if left == None or right == None:
quickSort(ml, 0, len(ml) - 1)
elif left < right:
p = partition(ml, left, right)
quickSort(ml, left, p - 1)
quickSort(ml, p + 1, right)

def insertSort(ml):
for n in range(1, len(ml)):
temp = ml[n]
index = n
while index > 0 and ml[index - 1] > temp:
ml[index] = ml[index - 1]
index -= 1
ml[index] = temp

def ciuraShellSort(ml):
'''It says this is fast,
but it seems it's not as fast as it's supposed to be'''
op, n = 0, len(ml)
incs = [2331004, 1036002, 460445, 204643, 90952, 40423, 17965, 7985,
3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1]
for t in range(18):
h = incs[t]
if h > n * 4 / 9:
continue
for i in range(h, n):
temp = ml[i]
j = i - h
while j >= 0 and ml[j] > temp:
ml[j + h] = ml[j]
op += 1
j -= h
ml[j + h] = temp
op += 1

def shellSort(seq):
'''This shell sort use the nature of python'''
inc = len(seq) // 2
while inc:
for i, el in enumerate(seq):
while i >= inc and seq[i - inc] > el:
seq[i] = seq[i - inc]
i -= inc
seq[i] = el
inc = round(inc / 2.2)

def shell(data):
'''This is tranlsated from java version from wiki,
not using python feature, it's a little bit slower than previous one'''
inc = len(data) // 2
while inc:
for i in range(inc, len(data)):
tmp = data[i]
j = i
while j >= inc and data[j - inc] > tmp:
data[j] = data[j - inc]
j -= inc
data[j] = tmp
inc = round(inc / 2.2)

def mergesort(n):
"""Recursively merge sort a list. Returns the sorted list."""
def merge(front, back):
"""Merge two sorted lists together. Returns the merged list."""
result = []
while front and back:
# pick the smaller one from the front and stick it on
# note that list.pop(0) is a linear operation, so this gives quadratic running time...
result.append(front.pop(0) if front[0]<=back[0] else back.pop(0))
# add the remaining end
result.extend(front or back)
return result

mid = len(n) // 2
front = n[:mid]
back = n[mid:]

if len(front) > 1:
front = mergesort(front)
if len(back) > 1:
back = mergesort(back)

def HeapSort(A):
def heapify(A):
start = (len(A) - 2) // 2
while start >= 0:
siftDown(A, start, len(A) - 1)
start -= 1

def siftDown(A, start, end):
root = start
while root * 2 + 1 <= end:
child = root * 2 + 1
if child + 1 <= end and A[child] < A[child + 1]:
child += 1
if child <= end and A[root] < A[child]:
A[root], A[child] = A[child], A[root]
root = child
else:
return

heapify(A)
end = len(A) - 1
while end > 0:
A[end], A[0] = A[0], A[end]
siftDown(A, 0, end - 1)
end -= 1

if __name__ == '__main__':
mt = [random.randint(1, 100) for i in range(9999)]
#print(' '.join(map(str, mt)))
print(isSorted(mt))

def out(visit):
if visit != None:
print(visit.__name__ + ':')
l = mt[:]
t1 = time.time()
visit(l)
t2 = time.time()
#print(' '.join(map(str, l)))
print(isSorted(l))
print((t2 - t1) * 1000.0)

out(insertSort)
out(bubbleSort)
out(selectSort)
out(quickSort)
out(ciuraShellSort)
out(shellSort)
out(shell)
out(mergesort)
out(HeapSort)
#该片段来自于http://outofmemory.cn
```

0人收藏

0

0

1. rainy 发表 2015-11-25 03:05:26 图像主题色提取算法
2. 0X55AA 发表 2014-03-19 08:43:30 sqlalchemy orm create_engine 设置数据库连接timeout
3. admin 发表 2014-08-15 02:43:19 【算法&数据结构】再次学算法之栈
4. 小数点 发表 2017-04-18 02:43:37 python学习之路——python切片模拟LRU算法
5. 0X55AA 发表 2015-01-31 13:54:10 python contextlib
6. 博主 发表 2014-12-22 16:18:37 经典排序算法总结与实现
7. fox64194167 发表 2018-05-27 00:12:22 python 搜索插入位置
8. 姚 广远 发表 2015-06-19 00:23:25 用Python实现各种排序算法
9. fox64194167 发表 2018-05-26 23:53:35 python 寻找重复的数
10. Yushneng 发表 2016-04-25 13:51:00 可视化图的基本算法
11. Yusheng 发表 2016-06-29 20:16:49 哈夫曼编码 —— Lisp 与 Python 实现
12. fox64194167 发表 2018-05-26 23:35:27 python 两个数组的交集 intersection of two arrays