冒泡，选择，插入，快排，希尔，归并，堆排序，并且画出时间性能对比曲线，画图部分可以改用循环，不用这么麻烦～
import math
import random
import time
import matplotlib.pyplot as plt
import sys
sys.setrecursionlimit(100000000)
def selectSort(L):
assert(type(L)== type(['']))
length = len(L)
if length == 0 or length ==1:
return L
for i in range(length):
min = i
for j in range(min, length):
if L[j] < L[min]:
min = j
temp = L[i]
L[i] = L[min]
L[min] = temp
return L
def insertSort(L):
assert(type(L)== type(['']))
length = len(L)
if length == 0 or length ==1:
return L
for i in range(length):
key = L[i]
j = i - 1
while j>= 0:
if L[j] > key:
L[j+1] = L[j]
L[j] = key
j -= 1
return L
def quick_sort(ary):
return qsort1(ary,0,len(ary)-1)
def qsort1(ary,left,right):
if left >= right : return ary
key = ary[left]
lp = left
rp = right
while lp < rp :
while ary[rp] >= key and lp < rp :
rp -= 1
while ary[lp] <= key and lp < rp :
lp += 1
ary[lp],ary[rp] = ary[rp],ary[lp]
ary[left],ary[lp] = ary[lp],ary[left]
qsort1(ary,left,lp-1)
qsort1(ary,rp+1,right)
return ary
'''
def quickSort(L):
assert(type(L)== type(['']))
less = []
pivotL = []
more = []
if len(L) <= 1:
return L
else:
pivot = L[0]
for i in L:
if i < pivot:
less.append(i)
elif i > pivot:
more.append(i)
else:
pivotL.append(i)
less = quickSort(less)
more = quickSort(more)
return less + pivotL + more
def qsort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
return qsort([x for x in arr[1:] if x < pivot]) + \
[pivot] + \
qsort([x for x in arr[1:] if x >= pivot])
'''
def shellSort(L):
count = len(L)
step = 2
group = int(count/step)
while group>0:
for i in range(group):
j = i+group
while j<count:
key = L[j]
k = j-group
while k>=0:
if L[k]>key:
L[k+group]=L[k]
L[k]=key
k=k-group
j=j+group
group=int(group/step)
return L
def merge_sort(table, left=0, right=None):
if right == None:
right = len(table) - 1
if right-left < 1:
return
middle = (left+right)//2
merge_sort(table, left, middle)
merge_sort(table, middle+1, right)
i = left
j = middle + 1
current = left
sortedTable = []
while current <= right:
if j > right or (table[i]<table[j]):
sortedTable.append(table[i])
i += 1
else:
sortedTable.append(table[j])
j += 1
current += 1
table[left:right+1] = sortedTable
'''
def heapSort(array):
def heap_adjust(parent):
child = 2 * parent + 1 # left child
while child < len(heap):
if child + 1 < len(heap):
if heap[child + 1] > heap[child]:
child += 1 # right child
if heap[parent] >= heap[child]:
break
heap[parent], heap[child] = \
heap[child], heap[parent]
parent, child = child, 2 * child + 1
heap, array = array.copy(), []
for i in range(len(heap) // 2, -1, -1):
heap_adjust(i)
while len(heap) != 0:
heap[0], heap[-1] = heap[-1], heap[0]
array.insert(0, heap.pop())
heap_adjust(0)
return array
'''
def heapSort(ary) :
n = len(ary)
first = int(n/2-1)
for start in range(first,-1,-1) :
max_heapify(ary,start,n-1)
for end in range(n-1,0,-1):
ary[end],ary[0] = ary[0],ary[end]
max_heapify(ary,0,end-1)
return ary
def max_heapify(ary,start,end):
root = start
while True :
child = root*2 +1
if child > end : break
if child+1 <= end and ary[child] < ary[child+1] :
child = child+1
if ary[root] < ary[child] :
ary[root],ary[child] = ary[child],ary[root]
root = child
else :
break
def bubble_sort(array):
for i in range(len(array)):
for j in range(i, len(array)):
if array[i] > array[j]:
array[i], array[j] = array[j], array[i]
#print(array)
return array
def check(n):
print("# size ", n, "\n")
print("# {0:<16}{1:<7}".format("sort algo", "time"))
l = [random.randint(0, n) for _ in range(n)]
cl = l[:]
t0 = time.time()
bubble_sort(cl)
t1 = time.time()
bs=[]
bs.append(t1-t0)
print("{0:<20}{1:<7.5f}s".format('bubble_sort', t1-t0))
plt.plot([n],[t1-t0], 'ro')
t0 = time.time()
selectSort(cl)
t1 = time.time()
print("{0:<20}{1:<7.5f}s".format('selectSort', t1-t0))
plt.plot([n],[t1-t0], 'go')
t0 = time.time()
shellSort(cl)
t1 = time.time()
print("{0:<20}{1:<7.5f}s".format('shellSort', t1-t0))
plt.plot([n],[t1-t0], 'b-')
t0 = time.time()
quick_sort(cl)
t1 = time.time()
print("{0:<20}{1:<7.5f}s".format('quickSort', t1-t0))
plt.plot([n],[t1-t0], color = 'brown', marker='o')
t0 = time.time()
merge_sort(cl)
t1 = time.time()
print("{0:<20}{1:<7.5f}s".format('merge_sort', t1-t0))
plt.plot([n],[t1-t0], color = 'red', marker='x')
t0 = time.time()
heapSort(cl)
t1 = time.time()
print("{0:<20}{1:<7.5f}s".format('heapSort', t1-t0))
plt.plot([n],[t1-t0],color = 'orange', marker='o')
t0 = time.time()
insertSort(cl)
t1 = time.time()
print("{0:<20}{1:<7.5f}s".format('insertSort', t1-t0))
plt.plot([n],[t1-t0],color = 'black',marker = 'o')
'''
i = 0
for sort in sorts:
cl = l[:]
t0 = time.time()
sort(cl)
t1 = time.time()
print("{0:<20}{1:<7.5f}s".format(sort.__name__, t1-t0))
plt.plot([n],[t1-t0], 'ro')
i += 1
'''
t2 = time.time()
sl = sorted(l)
t3 = time.time()
print("{0:<20}{1:<7.5f}s".format('tim_sort', t3-t2))
plt.plot([n],[t3-t2],color = 'pink', marker='o')
for n in range(600,1400,200):
check(n)
#check(100)
bs=[]
ss=[]
ss1=[]
qs=[]
ms =[]
hs=[]
iis=[]
s=[]
for n in range(600,1400,200):
l = [random.randint(0, n) for _ in range(n)]
cl = l[:]
t0 = time.time()
bubble_sort(cl)
t1 = time.time()
bs.append(t1-t0)
t0 = time.time()
selectSort(cl)
t1 = time.time()
ss.append(t1-t0)
t0 = time.time()
shellSort(cl)
t1 = time.time()
ss1.append(t1-t0)
t0 = time.time()
quick_sort(cl)
t1 = time.time()
qs.append(t1-t0)
t0 = time.time()
merge_sort(cl)
t1 = time.time()
ms.append(t1-t0)
t0 = time.time()
heapSort(cl)
t1 = time.time()
hs.append(t1-t0)
t0 = time.time()
insertSort(cl)
t1 = time.time()
iis.append(t1-t0)
t2 = time.time()
sl = sorted(l)
t3 = time.time()
s.append(t3-t2)
n = range(600,1400,200)
plt.plot(n,bs,'ro-')
plt.plot(n,ss,'bo-')
plt.plot(n,ss1,'go-')
plt.plot(n,qs,'b-')
plt.plot(n,ms,'r-')
plt.plot(n,hs,'g-')
plt.plot(n,iis,'yo-')
plt.plot(n,s,'o-')
plt.show()
for n in range(600,1400,200):
check(n)
