[ C++ std::sort python implement ] C++std::sort Python實作

最近有一個很靠北的課需要用python寫一些C++很容易做到的東西。
這次我們被要求寫一個quick sort，但是他要求的做法實在太糟糕了，於是我就參考了C++ std::sort來實做了一個quick sort(不包含heap sort的部分)：

	import random
	def quick_sort_implace(s):
	'''C++ std::sort implement without heap_sort'''
	first=0
	last=len(s)
	if(first!=last):
	__introsort_loop(s,first,last)
	__final_insertion_sort(s,first,last)
	def __final_insertion_sort(s,first,last):
	if(last-first>16):
	__insertion_sort(s,first,first+16)
	__unguarded_insertion_sort(s,first+16,last);
	else:
	__insertion_sort(s,first,last)
	def __insertion_sort(s,first,last):
	if(first==last):
	return
	for i in range(first+1,last):
	if(s[i]<s[first]):
	val=s[i]
	copy_backward(s,first,i,i+1)
	s[first]=val
	else:
	__unguarded_linear_insert(s,i)
	def copy_backward(s,first,last,result):
	while(first!=last):
	result-=1
	last-=1
	s[result]=s[last]
	return result
	def __unguarded_insertion_sort(s,first,last):
	for i in range(first,last):
	__unguarded_linear_insert(s,i)
	def __unguarded_linear_insert(s,last):
	val=s[last]
	__next=last
	__next-=1
	while(val<s[__next]):
	s[last]=s[__next]
	last=__next
	__next-=1
	s[last]=val
	def __introsort_loop(s,first,last):
	while(last-first>16):
	cut=__unguarded_partition_pivot(s,first,last)
	__introsort_loop(s,cut,last)
	last=cut
	def __unguarded_partition_pivot(s,first,last):
	mid=random.randint(first,last-1)
	__move_median_first(s,first,mid,last-1)
	return __unguarded_partition(s,first+1,last,s[first])
	def __move_median_first(s,a,b,c):
	if(s[a]<s[b]):
	if(s[b]<s[c]):
	s[a],s[b]=s[b],s[a]
	elif(s[a]<s[c]):
	s[a],s[c]=s[c],s[a]
	elif(s[a]<s[c]):
	return
	elif(s[b]<s[c]):
	s[a],s[c]=s[c],s[a]
	else:
	s[a],s[b]=s[b],s[a]
	def __unguarded_partition(s,first,last,pivot):
	while(True):
	while(s[first]<pivot):
	first+=1
	last-=1
	while(pivot<s[last]):
	last-=1
	if(not(first<last)):
	return first
	s[first],s[last]=s[last],s[first]
	first+=1
	# 以下為測試程式的部分
	def is_sorted(s):
	'''檢測序列s是否已排序'''
	n=len(s)
	i=1
	while(i<n):
	if(s[i]<s[i-1]):
	return False
	i+=1
	return True
	if __name__ == '__main__':
	import time
	s=[3 for n in range(1000000)]
	start=time.time()
	quick_sort_implace(s)
	end=time.time()
	print(is_sorted(s),end-start)
	s=[random.randint(0,1000000) for n in range(1000000)]
	start=time.time()
	quick_sort_implace(s)
	end=time.time()
	print(is_sorted(s),end-start)
	s=[random.randint(0,100) for n in range(1000000)]
	start=time.time()
	quick_sort_implace(s)
	end=time.time()
	print(is_sorted(s),end-start)
	s=[n for n in range(1000000)]
	start=time.time()
	quick_sort_implace(s)
	end=time.time()
	print(is_sorted(s),end-start)

view raw quick_sort.py hosted with ❤ by GitHub