堆排序
def heap_sort(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
#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
#start为当前需要调整最大堆的位置，end为调整边界
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
快速排序(simple)
# 快排
def quickSort(arr):
if len(arr)<=1:return arr
low,pi,high = partition(arr)
return quickSort(low)+[pi]+quickSort(high)
# 分区
def partition(arr):
pi , arr = arr[0],arr[1:]
low = [x for x in arr if x<=pi]
high = [x for x in arr if x>pi]
return low,pi,high
快速排序(regular)
def quick_sort(ary):
return qsort(ary,0,len(ary)-1)
def qsort(ary,left,right):
#快排函数，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]
qsort(ary,left,lp-1)
qsort(ary,rp+1,right)
return ary
归并排序
# MergeSort
def mergeSort(arr):
mid = len(arr)/2
left ,right = arr[:mid],arr[mid:]
if len(left)>1:
left = mergeSort(left)
if len(right)>1:
right = mergeSort(right)
res = []
while left and right:
if left[-1]>=right[-1]:
res.append(left.pop())
else:
res.append(right.pop())
res.reverse()
return (left or right)+res
Shell排序
def shell_sort(ary):
n = len(ary)
gap = round(n/2) #初始步长 , 用round四舍五入取整
while gap > 0 :
for i in range(gap,n): #每一列进行插入排序 , 从gap 到 n-1
temp = ary[i]
j = i
while ( j >= gap and ary[j-gap] > temp ): #插入排序
ary[j] = ary[j-gap]
j = j - gap
ary[j] = temp
gap = round(gap/2) #重新设置步长
return ary
插入排序
def insert_sort(lists):
# 插入排序
count = len(lists)
for i in range(1, count):
key = lists[i]
j = i - 1
while j >= 0:
if lists[j] > key:
lists[j + 1] = lists[j]
lists[j] = key
j -= 1
return lists
选择排序
def select_sort(ary):
n = len(ary)
for i in range(0,n):
min = i #最小元素下标标记
for j in range(i+1,n):
if ary[j] < ary[min] :
min = j #找到最小值的下标
ary[min],ary[i] = ary[i],ary[min] #交换两者
return ary
冒泡排序
def bubble_sort(arry):
n = len(arry) #获得数组的长度
for i in range(n):
for j in range(1,n-i):
if arry[j-1] > arry[j] : #如果前者比后者大
arry[j-1],arry[j] = arry[j],arry[j-1] #则交换两者
return arry
