冒泡排序
#
# 冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
#
# 步骤：
#
# 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
# 对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。
# 针对所有的元素重复以上的步骤，除了最后一个。
# 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
def bubble(alist):
#print(alist)
length=len(alist)
for i in range(length-1,0,-1):
exchange = False
for j in range(0,i):
if(alist[j]>alist[j+1]):
alist[j],alist[j+1]=alist[j+1],alist[j]
exchange=True
if not exchange:
break
return alist
if __name__ == '__main__':
re=bubble([1, 3, 4, 7, 83, 4])
print(re)
else:
print(__name__)
选择排序
# 介绍：
#
# 选择排序无疑是最简单直观的排序。它的工作原理如下。
# 步骤：
# 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
# 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
# 以此类推，直到所有元素均排序完毕。
def choosesoft(alist):
length=len(alist)
for i in range(length):
min=i
for j in range(i+1,length):
if(alist[j]<alist[i]):
min=j
alist[i],alist[min]=alist[min],alist[i]
return alist
if __name__=='__main__':
re=choosesoft([1, 3, 4, 7, 83, 4])
print(re)
插入排序
# 插入排序的工作原理是，对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
# 步骤：
# 从第一个元素开始，该元素可以认为已经被排序
# 取出下一个元素，在已经排序的元素序列中从后向前扫描
# 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
# 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
# 将新元素插入到该位置后
# 重复步骤2~5
def insert(alist):
length=len(alist)
for i in range(1,length):
if alist[i] < alist[i-1]:
temp=alist[i]
flag=i
for j in range(i-1,-1,-1):#从i-1 循环到 0 (包括0) i-1元素满足条件就ok
# print(alist[j])
if(temp<alist[j]):
alist[j+1]=alist[j]
flag=j
else:
break
alist[flag]=temp
return alist
if __name__=='__main__':
re=insert([5, 3, 4, 7, 83, 4])
print(re)
快排
# 从数列中挑出一个元素作为基准数。
# 分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。
# 再对左右区间递归执行第二步，直至各区间只有一个数。
def Quicksort(arr):
return quicksort(arr,0,len(arr)-1)
def quicksort(arr,left,right):
if left>=right: return arr
key=arr[left]
lp=left
rp=right
while(lp<rp):
while(arr[rp]>=key and lp<rp):
rp-=1
while(arr[lp]<=key and lp<rp):
lp+=1
arr[lp],arr[rp]=arr[rp],arr[lp]
arr[left],arr[lp]=arr[lp],arr[left]
quicksort(arr,left,lp-1)
quicksort(arr,rp+1,right)
return arr
if __name__=='__main__':
re = Quicksort([1, 3, 4, 7, 83, 4])
print(re)
希尔排序
def shell_sort(arr):
num=len(arr)
gap=round(num/2)
while gap>0:
for i in range(gap,num):
temp=arr[i]
index=i
while(index>=gap and arr [index-gap]>temp):
arr[index]=arr[index-gap]
index = index-gap
arr[index]=temp
gap=round(gap/2)
return arr
if __name__=='__main__':
re=shell_sort([1,2,5,7,3,8,9])
print(re)
归并排序
# 介绍：
# 归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
# 先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。
# 然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
# 再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法
# 将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该
# 小组内部已有序。然后合并排序相邻二个小组即可。
def merge_sort(arr):
if(len(arr)<=1):return arr
num=int(len(arr)/2)
left=merge_sort(arr[:num])
right=merge_sort(arr[num:])
return merge(left,right)
def merge(left,right):
l,r=0,0
result=[]
while(l<len(left) and r< len(right)):
if(left[l]<right[r]):
result.append(left[l])
l+=1
else:
result.append(right[r])
r+=1
result+=left[l:]
result+=right[r:]
return result
if __name__=='__main__':
re = merge_sort([1, 3, 4, 7, 83,3,4,5,8, 88,4])
print(re)
