pythonSortTest.py

'''
# Create by LokiSharp(loki.sharp#gmail) at 2017-1-22
'''

TOTAL=5000


defsortTest(func, total=1000):
importrandom, copy, operator, math, time
arrList= [iforiinrange(-math.floor(total/2), math.ceil(total/2))]
arrListR=copy.deepcopy(arrList)
whileoperator.eq(arrList, arrListR):
random.shuffle(arrListR)
# print("--- [Origin List]", arrList, "Use", func.__name__,"with Total:", len(arrList))
# print("--> [Random List]", arrListR, "Use", func.__name__,"with Total:", len(arrList))
start=time.clock()
arrListR=func(arrListR)
end=time.clock()
runtime=end-start
# print("--> [Sorted List]", arrListR, "Use", func.__name__,"with Total:", len(arrList))
ifoperator.eq(arrList, arrListR):
print("[Success]", func.__name__, "with Total:", len(arrList), "in %.5fs"%runtime)
returnTrue
else:
print("[Fail]", func.__name__, "with Total:", len(arrList), "in %.5fs"%runtime)
returnFalse


defbubbleSort(arr):
foriinrange(1, len(arr)):
forjinrange(0, len(arr) -i):
ifarr[j] >arr[j+1]:
arr[j], arr[j+1] =arr[j+1], arr[j]
returnarr


defselectionSort(arr):
foriinrange(len(arr) -1):
# 记录最小数的索引
minIndex=i
forjinrange(i+1, len(arr)):
ifarr[j] <arr[minIndex]:
minIndex=j
# i 不是最小数时，将 i 和最小数进行交换
ifi!=minIndex:
arr[i], arr[minIndex] =arr[minIndex], arr[i]
returnarr


definsertionSort(arr):
foriinrange(len(arr)):
preIndex=i-1
current=arr[i]
whilepreIndex>=0andarr[preIndex] >current:
arr[preIndex+1] =arr[preIndex]
preIndex-=1
arr[preIndex+1] =current
returnarr


defshellSort(arr):
importmath
gap=1
while (gap<len(arr) /3):
gap=gap*3+1
whilegap>0:
foriinrange(gap, len(arr)):
temp=arr[i]
j=i-gap
whilej>=0andarr[j] >temp:
arr[j+gap] =arr[j]
j-=gap
arr[j+gap] =temp
gap=math.floor(gap/3)
returnarr


defmergeSort(arr):
importmath
if (len(arr) <2):
returnarr
middle=math.floor(len(arr) /2)
left, right=arr[0:middle], arr[middle:]
returnmerge(mergeSort(left), mergeSort(right))


defmerge(left, right):
result= []
whileleftandright:
ifleft[0] <=right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
whileleft:
result.append(left.pop(0));
whileright:
result.append(right.pop(0));
returnresult


defquickSort(arr, left=None, right=None):
left=0ifnotisinstance(left, (int, float)) elseleft
right=len(arr) -1ifnotisinstance(right, (int, float)) elseright
ifleft<right:
partitionIndex=partition(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex+1, right)
returnarr


defpartition(arr, left, right):
pivot=left
index=pivot+1
i=index
whilei<=right:
ifarr[i] <arr[pivot]:
swap(arr, i, index)
index+=1
i+=1
swap(arr, pivot, index-1)
returnindex-1


defswap(arr, i, j):
arr[i], arr[j] =arr[j], arr[i]


defbuildMaxHeap(arr):
importmath
foriinrange(math.floor(len(arr) /2), -1, -1):
heapify(arr, i)


defheapify(arr, i):
left=2*i+1
right=2*i+2
largest=i
ifleft<arrLenandarr[left] >arr[largest]:
largest=left
ifright<arrLenandarr[right] >arr[largest]:
largest=right

iflargest!=i:
swap(arr, i, largest)
heapify(arr, largest)


defswap(arr, i, j):
arr[i], arr[j] =arr[j], arr[i]


defheapSort(arr):
globalarrLen
arrLen=len(arr)
buildMaxHeap(arr)
foriinrange(len(arr) -1, 0, -1):
swap(arr, 0, i)
arrLen-=1
heapify(arr, 0)
returnarr


defcountingSort(arr, maxValue=None):
bucketLen=maxValue+1
bucket= [0] *bucketLen
sortedIndex=0
arrLen=len(arr)
foriinrange(arrLen):
ifnotbucket[arr[i]]:
bucket[arr[i]] =0
bucket[arr[i]] +=1
forjinrange(bucketLen):
whilebucket[j] >0:
arr[sortedIndex] =j
sortedIndex+=1
bucket[j] -=1
returnarr

defradix_count(exp1):
globallist
n=len(list)
output= [0] * (n)
count= [0] * (10)
foriinrange(0, n):
index= (list[i] /exp1)
count[(index) %10] +=1
foriinrange(1,10):
count[i] +=count[i-1]
i=n-1
whilei>=0:
index= (list[i]/exp1)
output[count[(index) %10] -1] =list[i]
count[(index) %10] -=1
i-=1
i=0
foriinrange(0,len(list)):
list[i] =output[i]

defradixSort():
globallist
max1=max(list)
exp=1
whilemax1/exp>0:
radix_count(exp)
exp*=10


if__name__=='__main__':
sortTest(bubbleSort, TOTAL)
sortTest(selectionSort, TOTAL)
sortTest(insertionSort, TOTAL)
sortTest(shellSort, TOTAL)
sortTest(mergeSort, TOTAL)
sortTest(quickSort, TOTAL)
sortTest(heapSort, TOTAL)
sortTest(radixSort, TOTAL)