基本思想:从第一个元素开始，与下一个元素比较，如果比后一个小，不交换继续往后走；如果比下一个大，则交换，到最后选出的是最大的数字。从每次从头开始遍历，选出一个最大的。
def bubble(alist): """冒泡排序""" n = len(alist) for i in range(0, n - 1): count = 0 for j in range(0, n - 1 - i): if alist[j] > alist[j + 1]: alist[j], alist[j + 1] = alist[j + 1], alist[j] count += 1 if count == 0: break return alist if __name__ == "__main__": slist = [33, 78, 43, 65, 7, 34, 87, 34, 99, 45] print(bubble(slist)) def bubble_sort(alist): """第二种""" n = len(alist) for i in range(n-1, 0 , -1): count = 0 for j in range(i): if alist[j] > alist[j+1]: alist[j], alist[j+1] = alist[j+1],alist[j] if count == 0: return时间复杂度： 最优时间复杂度：O(n) 最坏时间复杂度：O(n^2) 稳定性：稳定
基本思想：每次选择一个最小的，第二次选择一个次小的，直到第n-1趟序列有序。
def select_sort(): """选择排序""" n = len(alist) for j in range(n-1): # 0~n-2 min_index = [j] for i in range(j+1, n): if alist[min_index] > alist[i]: min_index = i alist[0], alist[min_index] = alist[min_index], alist[0]时间复杂度： 最优时间复杂度：O(n^2) 最坏时间复杂度：O(n^2) **稳定性：**不稳定
将列表的前一部分当作一个有序列表，没往后走一步，就将它插入到它对应的正确位置。使用i 和i-1不会存在最后一个列表元素访问不到的问题。 是稳定的排序算法。
def insert_sort(alist): """插入排序""" for j in range(1, len(alist)): i = j while i > 0: if alist[i] < alist[i-1]: alist[i-1], alist[i] = alist[i], alist[i-1] i -= 1 else: # 插入算法的优化 break def insert_sort(alist): """插入排序""" for i in range(1, len(alist)): for j in range(j, 0 , -1) if alist[j] < alist[j-1]: alist[j-1], alist[j] = alist[j], alist[j-1] else: break实际上是插入排序的改进版 基本思想：将一个无序序列当成是多个无序序列组成的。取一个间距值gap。 以gap=4为例 一个原有序列分为了四个无序序列，对每个子序列进行插入排序。 gap决定了子序列的个数，可以将子序列分为两部分，gap之前的序列和gap之前的部分和gap之后的部分。
def shell_sort(alist): """希尔排序""" n = len(alist) gap = n//2 # 按照折半 while gap > 0: # 与普通插入算法的区别就是步长 for j in range(gap, n): # j = [gap, gap+1, gap+2, gap+3, ..., n-1] i = j while i > 0: if alist[i] < alist[i-gap]: alist[i-gap], alist[i] = alist[i], alist[i-gap] i -= gap else: break # 缩短gap步长 gap //= 2时间复杂度： 最优时间复杂度：根据步长的不同而不同 最坏时间复杂度：O(n^2) 稳定性：不稳定
将整个序列进行拆分，最开始将列表从中间拆分成两个部分，然后将左右两部分在进行拆分，递归直到每一部分只有一个元素。然后两两进行合并，合并时小的在前，大的在后，借助左右两个指针进行合并。使用递归实现
当有奇数个数字时，数字从那部分拆分的就合并到那部分。例如【44、55、66】，首先拆分成[44]和[55,66],然后再将【55，66】拆分成【55】【66】，合并的时候先合并到【55，66】再与【44】合并
def merge_sort(alist): """归并排序""" # 首先拆分列表 n = len(alist) if n <= 1: # 控制递归返回,执行到只有一个元素的时候一定是一个有序集合，所以直接返回自身 return alist mid = n//2 # left 采用归并排序后形成的新的列表 left_li = merge_sort(alist[:mid]) # right 采用归并排序后形成的新列表 right_li = merge_sort(alist[mid:]) # 将两个有序子序列合并成一个新的列表 # merge(left, right) left_pointer, right_pointer = 0, 0 # 用于存放结果值的新列表 result = [] while left_pointer < len(left_li) and right_pointer < len(right_li): if left_li[left_pointer] <= right_li[right_pointer]: result.append(left_li[left_pointer]) left_pointer += 1 elif: result.append(right_li[right_pointer]) right_pointer += 1 result += right_li[right_pointer:] result += left _li[left_pointer:] return result**快排的思想：**首先找一个标记数字，一般都是列表的第一个，然后双面夹击，找到标记数字的正确位置，即比标记数字小的都在标记数字的左边，比比较数字大的都在标记数字的右边。 **实现方式：**设计两个游标，low指向除标记数字之外的第一个位置，high指向最后一个位置。首先让low走，如果low指向数字比标记数字小，low往后走；如果low指向的数字比标记数字大，low停止。然后看high，如果high指向元素比标记数字大，high往前走，否则high停止。此时将low与high的位置交换。接下来重复上述步骤，即让low在开始往后走。直到low和high交汇。 此过程不断递归重复。 复杂度： 最优时间复杂度：O(nlogn) 最坏时间复杂度：O(n^2) 不稳定
def quick_sort(alist, first, last): """快速排序""" if first >= last: return mid_value = alist[first] low = first high = last # 里面部分的排序过程 while low < high: # high的游标左移,相等的元素放到一边处理 while low < high and alist[high] >= mid_value: high -= 1 alist[low] = alist[high] # low += 1 # low的游标右移 while low < high and alist[low] < mid_value: low += 1 alist[high] = alist[low] # high -= 1 # 从循环退出的时候，high=low alist[low] = mid_value # sort始终是对源列表进行排序，所以不能使用切片 # quick_sort(alist[:low-1]) # quick_sort(alist[low+1:]) quick_sort(alist, first, low-1) quick_sort(alist, low+1, last) if __name__ == "__main__": li = [54, 26, 93, 17, 31, 44, 55, 20] print(li) quick_sort(li, 0, len(li)-1) print(li)