冒泡排序(短冒泡排序)
import numpy as np
import time
def bubble_sort(alist):
for passnum in range(len(alist) - 1, 0, -1):
for i in range(passnum):
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
# 短冒泡排序,当一次遍历时,已经出现排好序的情况下,不需要再进行下面的遍历
def short_bubble_sort(alist):
need_exchange = True
passnum = len(alist) - 1
while passnum > 0 and need_exchange:
need_exchange = False
for i in range(passnum):
if alist[i] > alist[i + 1]:
need_exchange = True
alist[i], alist[i + 1] = alist[i + 1], alist[i]
passnum -= 1
if __name__ == '__main__':
alist = np.random.randint(10, size=10)
print(alist)
bubble_sort(alist)
print(alist)
blist = np.random.randint(10, size=10)
print(blist)
short_bubble_sort(blist)
print(blist)
start_time = time.time()
for i in range(10):
clist = np.random.randint(int(1e4), size=int(1e4))
bubble_sort(clist)
print(time.time() - start_time)
start_time = time.time()
for i in range(10):
dlist = np.random.randint(int(1e4), size=int(1e4))
short_bubble_sort(dlist)
print(time.time() - start_time)
# [4 8 7 5 9 9 1 1 8 9]
# [1 1 4 5 7 8 8 9 9 9]
# [1 4 0 3 7 7 8 7 2 1]
# [0 1 1 2 3 4 7 7 7 8]
# 166.6802577972412
# 168.61909222602844
选择排序
import numpy as np
import time
def selection_sort(alist,list_size):
for i in range(list_size-1):
tmp_min=i
for j in range(i+1,list_size):
if alist[j]<alist[tmp_min]:
tmp_min=j
alist[i],alist[tmp_min]=alist[tmp_min],alist[i]
if __name__=='__main__':
alist=np.random.randint(0,10,size=10)
print('before sort: ',alist)
list_length=len(alist)
selection_sort(alist, list_length)
print('after sort: ',alist)
blist=np.random.randint(0,10000,size=10000)
list_length=len(blist)
start_time=time.time()
selection_sort(blist, list_length)
print('elapsed time= ',time.time()-start_time)
# before sort: [2 8 8 8 1 4 0 4 0 3]
# after sort: [0 0 1 2 3 4 4 8 8 8]
# elapsed time= 9.69593620300293
插入排序
import numpy as np
import time
def insertion_sort(alist,list_length):
for i in range(1,list_length):
for j in range(0,i):
if alist[j]>alist[i]:
tmp=alist[i]
for k in range(i,j,-1):
alist[k]=alist[k-1]
alist[j]=tmp
break
if __name__ == '__main__':
alist = np.random.randint(10, size=10)
print(alist)
insertion_sort(alist)
print(alist)
start_time = time.time()
for i in range(10):
clist = np.random.randint(int(1e4), size=int(1e4))
insertion_sort(clist)
print(time.time() - start_time)
# [9 8 9 6 7 6 8 7 1 4]
# [1 4 6 6 7 7 8 8 9 9]
# 68.87531685829163
希尔排序
import numpy as np
import time
# This implementation is a copy version of the Java implementation in the Algorithm (4th edition)
# But its performance is very bad.
# * before sort: [7 6 6 4 9 8 4 2 0 1]
# * after sort: [0 1 2 4 4 6 6 7 8 9]
# * elapsed time= 14.546229839324951
def shell_sort_from_java(alist):
length=len(alist)
h=1
while h<length//3:
h=3*h+1
while h>=1:
for i in range(h,length):
for j in range(i,h-1,-h):
if alist[j]<alist[j-h]:
alist[j],alist[j-h]=alist[j-h],alist[j]
h=h//3
# before sort: [0 5 3 6 2 9 4 5 6 7]
# after sort: [0 2 3 4 5 5 6 6 7 9]
# elapsed time= 0.07308650016784668
def shell_sort(arr):
# Start with a big gap, then reduce the gap
n = len(arr)
gap = n//2
# Do a gapped insertion sort for this gap size.
# The first gap elements a[0..gap-1] are already in gapped
# order keep adding one more element until the entire array
# is gap sorted
while gap > 0:
for i in range(gap,n):
# add a[i] to the elements that have been gap sorted
# save a[i] in temp and make a hole at position i
temp = arr[i]
# shift earlier gap-sorted elements up until the correct
# location for a[i] is found
j = i
while j >= gap and arr[j-gap] >temp:
arr[j] = arr[j-gap]
j -= gap
# put temp (the original a[i]) in its correct location
arr[j] = temp
gap =gap//2
if __name__ == '__main__':
alist = np.random.randint(0, 10, size=10)
print('before sort: ', alist)
list_length = len(alist)
shell_sort(alist)
print('after sort: ', alist)
blist=np.random.randint(0,10000,size=10000)
list_length=len(blist)
start_time=time.time()
shell_sort(blist)
print('elapsed time= ',time.time()-start_time)
归并排序
import numpy as np
import time
from copy import deepcopy
def merge_sort(alist):
if len(alist) > 1:
mid = len(alist) // 2
left_half = deepcopy(alist[:mid])
right_half = deepcopy(alist[mid:])
merge_sort(left_half)
merge_sort(right_half)
_merge(alist, left_half, right_half)
def _merge(alist, left_half, right_half):
i, j, k = 0, 0, 0
#print('merge alist: ', alist)
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
alist[k] = left_half[i]
i += 1
else:
alist[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
alist[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
alist[k] = right_half[j]
j += 1
k += 1
if __name__ == '__main__':
alist = np.random.randint(0, 10, size=10)
print('before sort: ', alist)
list_length = len(alist)
merge_sort(alist)
print('after sort: ', alist)
blist=np.random.randint(0,10000,size=10000)
list_length=len(blist)
start_time=time.time()
merge_sort(blist)
print('elapsed time= ',time.time()-start_time)
# before sort: [9 1 7 1 6 6 4 0 6 8]
# after sort: [0 1 1 4 6 6 6 7 8 9]
# elapsed time= 0.08119559288024902
快速排序
import numpy as np
import time
from copy import deepcopy
def quick_sort(arr,l,r):
if l >= r: return
i,j = l,r
while i < j:
while i < j and arr[j] >= arr[l]:
j -= 1
while i < j and arr[i] <= arr[l]:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[l], arr[i] = arr[i], arr[l]
quick_sort(arr, l, i-1)
quick_sort(arr, i+1, r)
def quick_sort_implementation_two(array_):
if len(array_)<2:
return array_
else:
pivot=array_[0]
less=[i for i in array_[1:] if i<=pivot]
greater=[i for i in array_[1:] if i>pivot]
return quicksort(less)+[pivot]+quicksort(greater)
print(quicksort([5,8,2,1,4,2,7]))
if __name__ == '__main__':
alist = np.random.randint(0, 10, size=10)
print('before sort: ', alist)
list_length = len(alist)
quick_sort(alist)
print('after sort: ', alist)
blist=np.random.randint(0,10000,size=10000)
list_length=len(blist)
start_time=time.time()
quick_sort(blist)
print('elapsed time= ',time.time()-start_time)
# before sort: [8 0 7 2 6 4 1 2 0 2]
# after sort: [0 0 1 2 2 2 4 6 7 8]
# elapsed time= 0.08011627197265625

评论(0)
您还未登录,请登录后发表或查看评论