虽然但是，隔了三天，不过我是去做正事了~
参加了一个数学建模比赛，本来有把代码和思路放上来的想法，但是因为太不成熟了，就放弃了【doge】
'''冒泡排序'''
# 在无序表中从前往后两两比较，大的在后，比较n-1轮，因为每一轮之后就会确定一个最大的在最后边
def bubbleSort(ListA):
for passNum in range(len(ListA) - 1, 0, -1):
for i in range(passNum):
if ListA[i] > ListA[i + 1]:
ListA[i], ListA[i + 1] = ListA[i + 1], ListA[i]
# return ListA
'''快速排序'''
# 在无序表中选取第一个当基准点，左码在第二个，右码在最后一个，左码向右移动找到比基准大的就停下，右码左移找到比基准小的就停下，这俩数值互换，然后接着移动，等这俩撞到一起的时候，就把这个数和基准点互换
def quickSort(ListA):
qucikSortHelper(ListA,0,len(ListA)-1)
pass
def qucikSortHelper(ListA,first,last):
if first< last:
splitpoint = partition(ListA,first,last)
qucikSortHelper(ListA,first,splitpoint-1)
qucikSortHelper(ListA,splitpoint+1,last)
pass
def partition(ListA,first,last):
pivotvalue = ListA[first]
leftmark = first+1
rightmark = last
done = False
while not done:
while leftmark <=rightmark and \
ListA[leftmark] < pivotvalue:
leftmark += 1
while leftmark <= rightmark and \
ListA[rightmark] > pivotvalue:
rightmark -= 1
if rightmark < leftmark:
done = True
else:
ListA[leftmark],ListA[rightmark] = ListA[rightmark],ListA[leftmark]
ListA[first],ListA[rightmark] = ListA[rightmark],ListA[first]
return rightmark
pass
'''堆排序'''
# 建堆，然后取出根依次排列
def sift(ListA, low, high):
'''
调整根堆
:param ListA:
:param low:
:param high:
:return:
'''
i = low # i最开始指向根节点那一层
j = 2 * i + 1 # j开始是左孩子
tmp = ListA[low] # tmp是得到了根堆的值
while j<=high: # 只要j位置有数，也就是不越界
if j+1 <=high and ListA[j + 1]>ListA[j]: # 如果右孩子比左孩子大
j = j+1 # 让j是更大的孩子那边
if ListA[j]>tmp:
ListA[i] = ListA[j]
i = j
j = 2*i + 1 #往下挪一层
else:
ListA[i] = tmp # 把tmp放到某一领导位置上
break
else:
ListA[i] = tmp # 把tmp放到叶子结点上
def heapSort(ListA):
n = len(ListA)
for i in range((n-2)//2, -1, -1):
# i表示建立根堆的时候调整的部分的根的下标
# 从小到大农村包围城市调整，所以倒着来
sift(ListA, i, n - 1)
#建好堆
for i in range(n-1,-1,-1):
# i指向当前堆的最后一个元素，把大根堆的根拿下放到最后边，
# 一般理解为大根堆在列表中第一个元素是最大的
# 通过堆排序交换出的列表就变成了最后一个是最大的升序排列
ListA[0], ListA[i] = ListA[i], ListA[0]
sift(ListA, 0, i - 1) # i-1是新的high
'''希尔排序'''
# 分组进行插入排序
def insertSortGap(li, gap):
for i in range(gap, len(li)):
tmp = li[i]
j = i-gap
while j >= 0 and li[j] > tmp:
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp
def shellSort(li):
d = len(li)//2
while d >= 1:
insertSortGap(li,d)
d //= 2
'''二叉树遍历'''
if __name__ == '__main__':
ListA = [2,1,3,5,4]
print(ListA)
# # 冒泡排序
# bubbleSort(ListA)
# # 快速排序
# quickSort(ListA)
# # 堆排序
# heapSort(ListA)
# 希尔排序
shellSort(ListA)
print(ListA)
