python实现排序

# # # 1.冒泡排序

# # # 将相邻的两个数两两比较，每次外循环都将最大的数移到最后，

# # # 每次内循环比较两个数，如果后一个数小于前一个数，两个数交换。

#

# # # 冒泡排序是最慢的排序算法，实际运用中效率最低，

# # # 当数列为由小到大的有序数列时为最好情况，当由大到小时为为最坏情况。

#

def Bubble_sort(alist):

count = 0

# 遍历每一趟比较的次数，每走一趟能得出右边的一个最大值，比较的次数就递减

for j in range(len(alist)-1,0,-1):

flag = False #flag运用于冒泡出现最优情况的时候，如果第一趟没有交换任何数，那么就不需要后面的趟数

# 遍历当前趟从索引0开始比较完当前次数

for i in range(j):

if alist[i] > alist[i+1]:

alist[i],alist[i+1] = alist[i+1],alist[i]

flag = True

count+=1

if flag == False:

break

print(alist,count)

list = [54,26,93,17,77,31,44,55,20] #打乱 时间复杂度：O(n^2)

# list = [99,88,77,66,55,44,33,22,11] #最坏的情况 时间复杂度：O(n^2)

list = [11,22,33,44,55,66,77,88,99] #最优情况 时间复杂度：O(n)
Bubble_sort(list)

2.选择排序
def select_sort(alist):
#以游标初始处开始向后遍历，结束一次遍历为一趟，要走len(alist)-1趟
for j in range(len(alist)-1):
min_index = j #给一个最小游标，放在未排序的第一个元素上

    #以初始游标值为标准，把游标初始值和其后面的值依次比较，
    # 碰到更小的数将游标放入该值索引处，
    # 全比较完后将最终游标指向的值和初始游标值位置调换
    for i in range(j+1,len(alist)):
        if alist[min_index] > alist[i]:
            min_index = i
    # 假如当前游标位置与初始游标位置不一样，说明发生了变化
    # 将初始游标值与当前游标值调换
    if min_index != j:
        alist[j],alist[min_index] = alist[min_index],alist[j]
print(alist)

list = [54,226,93,17,77,31,44.55,20]
select_sort(list)

3.插入排序
def insert_sort(alist):
# 从第二个开始，和前面所有元素比，比到第0个元素算一趟
for j in range(1,len(alist)):
flag = True
# 将当前元素和前面每一个元素进行比较，比上一个元素小，两个就调换位置
for i in range(j,0,-1):
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
flag = False
if flag == True:
break
print(alist)
list = [54,26,93,17,77,31,44,55,20]
insert_sort(list)