python如何实现常用的五种排序算法详解

 alist = [3, 5, 9, 2, 1, 7, 8, 6, 4] def bubble_sort(alist): # 找最大值的方式是通过对列表中的元素进行两两比较，值大的元素逐步向后移动 # 序列中有n个元素，两两比较的话，需要比较n-1次 for i in range(len(alist) - 1):  # 循环n-1次，控制两两比较的次数 if alist[i] > alist[i + 1]: # 如果前面的元素大于后面的元素，交换两个元素的位置，否则不做任何操作 alist[i], alist[i + 1] = alist[i + 1], alist[i] return alist print(bubble_sort(alist)) # 输出：最大值已经移动到最右边了 [3, 5, 2, 1, 6, 7, 8, 4, 9] 

 alist = [3, 5, 9, 2, 1, 7, 8, 6, 4] def bubble_sort(alist): for j in range(len(alist)-1):   # 外层循环次数递增，内层循环次数递减 for i in range(len(alist) - 1-j):  # 循环次数需要递减-j，控制两两比较的次数 if alist[i] > alist[i + 1]: # 如果前面的元素大于后面的元素，交换两个元素的位置，否则不做任何操作 alist[i], alist[i + 1] = alist[i + 1], alist[i] return alist print(bubble_sort(alist)) # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9] 

 def select_sort(alist): max_index = 0  # 最大值元素的下标，一开始假设下标为0的元素为最大值 for i in range(len(alist) - 1):  # 循环控制两两比较的次数 # 如果在比较的过程中发现，下标为max_index不是最大值，那么就改变max_index if alist[max_index] 

 def select_sort(alist): for j in range(len(alist) - 1):# 外层循环递增n-1次 max_index = 0  # 最大值元素的下标，一开始假设下标为0的元素为最大值 for i in range(len(alist) - 1 - j):  # 内层循环递减，循环控制两两比较的次数 # 如果在比较的过程中发现，下标为max_index不是最大值，那么就改变max_index if alist[max_index] 

 # 乱序序列：[8,3,5,7,6] [8,    3,5,7,6] # 8就是初始的有序部分，3、5、7、6就是初始的无序部分 [3,8,    5,7,6] [3,5,8,    7,6] [3,5,7,8,    6] [3,5,7,6,8,   ] 

 alist = [8, 3, 1, 6, 7] i = 1  # i 就是有序部分元素的个数和无序部分第一个元素下标 # alist[i-1]：有序部分最后一个元素下标 # alist[i]：无序部分第一个元素下标 if alist[i - 1] > alist[i]: alist[i], alist[i - 1] = alist[i - 1], alist[i] # [3, 8,    1, 6, 7] 

 alist = [8, 3, 1, 6, 7] i = 2 # alist[i-1]：有序部分最后一个元素下标 # alist[i]：无序部分第一个元素下标 while i > 0: if alist[i - 1] > alist[i]: # 循环第一次时[3,1,8,   6,7] alist[i], alist[i - 1] = alist[i - 1], alist[i] i -= 1 # 循环继续 # [1,3,8,   6，7] else: break 

 for i in range(1, len(alist)): # i = [1,2,3,4] # alist[i-1]：有序部分最后一个元素下标 # alist[i]：无序部分第一个元素下标 while i > 0: if alist[i - 1] > alist[i]: alist[i], alist[i - 1] = alist[i - 1], alist[i] i -= 1 else: break 

 def insert_sort(alist): for i in range(1, len(alist)): while i > 0: if alist[i - 1] > alist[i]: alist[i - 1], alist[i] = alist[i], alist[i - 1] i -= 1 else: break return alist 

 def hill_sort(alist): for i in range(1, len(alist)): while i > 0: if alist[i - 1] > alist[i]: alist[i - 1], alist[i] = alist[i], alist[i - 1] i -= 1 else: break return alist 

 def hill_sort(alist): gap = len(alist) // 2  # 初识增量 # 将插入排序中的增量1替换成gap # 由增量1变成了增量为gap了 for i in range(gap, len(alist)): while i > 0: if alist[i - gap] > alist[i]: alist[i - gap], alist[i] = alist[i], alist[i - gap] i -= gap else: break return alist 

 def hill_sort(alist): gap = len(alist) // 2  # 初识增量 while gap >= 1: for i in range(gap, len(alist)): while i > 0: if alist[i - gap] > alist[i]: alist[i - gap], alist[i] = alist[i], alist[i - gap] i -= gap else: break gap //= 2  # 缩减增量 return alist 

 def quick_sort(alist): low = 0  # 第一个元素下标 high = len(alist) - 1  # 最后一个元素下标 mid = alist[low]  # 基数：初始值为序列中的第一个数值 while low != high: # 先移动high while low  alist[low]:  # 下标low对应的值小于mid，low就向左偏移1 low = low + 1 else: # 否则，就把将low指向的数值放置到左侧下标为high对应的空位 alist[high] = alist[low] break  # 并结束 # 最后当low和high相等的时候，那么就把mid传给下标为low或high的位置 alist[low] = mid return alist alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8] print(quick_sort(alist)) # 输出――>6左边都是比6小的，右边都是比6大的 [5, 1, 2, 4, 3,    6,    9, 7, 10, 8] 

 # 那么如何区分根据基数拆分出的左右子序列呢？可以通过传入指定的left和right来指定不同的子序列 def quick_sort(alist, left, right): low = left  # 第一个元素下标 high = right  # 最后一个元素下标 if low > high:  # 递归结束条件，low是不能大于high的 return mid = alist[low]  # 基数：初始值为序列中的第一个数值 while low != high: # 先移动high while low = alist[low]:  # 下标low对应的值小于mid，low就向左偏移1 low += 1 else: # 否则，就把将low指向的数值放置到左侧下标为high对应的空位 alist[high] = alist[low] break  # 并结束 # 最后当low和high相等的时候，那么就把mid传给下标为low或high的位置 if low == high: alist[low] = mid # 上述为核心操作，需要将核心操作递归作用到左右子序列中 quick_sort(alist, left, low - 1)  # 递归到左侧序列中 quick_sort(alist, high + 1, right)  # 递归到右侧序列中 return alist alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8] print(quick_sort(alist, 0, len(alist) - 1)) # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]