1.冒泡排序：
概念：冒泡排序的思想：依次比较相邻的两个记录的关键字，若两个记录是反序的(即前一个记录的关键字大于后前一个记录的关键字)，则进行交换，直到没有反序的记录为止。假定数据放在一个列表lst中。
① 首先将lst[1]与lst[2]的关键字进行比较，若为反序(lst[1]的关键字大于lst[2]的关键字)，则交换两个记录；然后比较lst[2]与lst[3]的关键字，依此类推，直到lst[n-1]与lst[n]的关键字比较后为止，称为一趟冒泡排序，lst[n]为关键字最大的记录。
② 然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作。
一般地，第i趟冒泡排序是对lst[1 … n-i+1]中的记录进行的，因此，若待排序的记录有n个，则要经过n-1趟冒泡排序才能使所有的记录有序。
def bubble_sort(lst): length = len(lst) for i in range(length-1): #共有length -1趟排序 flag = True #falg用于记录一趟冒泡排序中，是否有逆序发生 for j in range(1,length-i): if lst[j-1]>lst[j]: flag = False #有逆序发生 lst[j-1],lst[j]=lst[j],lst[j-1] if flag == True: break def main(): list1 = [23, 38, 22, 45, 67, 31, 15, 41] print(list1) bubble_sort(list1) print(list1) main()
运行结果：
2.选择排序
概念：每次从当前待排序的记录中选取关键字最小的记录表，然后与待排序的记录序列中的第一个记录进行交换，直到整个记录序列有序为止。
def select_sort(lst): n = len(lst) for i in range(0,n): min = i #最小元素下标标记 for j in range(i+1,n): if lst[j] < lst[min]: min = j #找到最小值的下标 lst[i],lst[min] = lst[min],lst[i] #将找到的最小值与待排序的第一个记录交换 def main(): list1 = [9, 6, -2, 21, 15, 8] select_sort(list1) print(list1) main() #调用main函数
运行结果：
3.插入排序
概念：将待排序的记录插入到已排好序的记录表中，得到一个新的、记录数增加1的有序表，选择下一个待排序的记录重复前面的操作，直到所有的记录都插入完为止。假设有n个元素需要排序，则需要n-1趟插入就可排好序。
def insertion_sort(lst): lst_length=len(lst) if lst_length<2: return lst for i in range(1,lst_length): key=lst[i] j=i-1 while j>=0 and key<lst[j]: lst[j+1]=lst[j] j=j-1 lst[j+1]=key return lst def main(): list1 = [7, 4, 2, 19, 13, 6] print(list1) list2=insertion_sort(list1) print(list2) main()
运行结果：
4.归并排序：
概念：①初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列； ②对所有有序子序列进行两两归并，得到n/2个长度为2或1的有序子序列——一趟归并； ③重复②，直到得到长度为n的有序序列为止。 上述排序过程中，子序列总是两两归并，称为2-路归并排序，其核心是将相邻的两个子序列归并成一个子序列。
def merge_sort(lst): if len(lst)<2: return lst sorted_list=[] #用于存放两个列表有序合并后的结果 left_list=merge_sort(lst[:len(lst)//2]) right_list=merge_sort(lst[len(lst)//2:]) while len(left_list)>0 and len(right_list)>0: if left_list[0]<right_list[0]: sorted_list.append(left_list.pop(0)) else: sorted_list.append(right_list.pop(0)) sorted_list += left_list sorted_list += right_list return sorted_list def main(): list1 = [23, 38, 22, 45, 24, 67, 31, 15, 41] print(list1) list2=merge_sort(list1) print(list2) main()
运行结果：
5.快速排序
概念：快速排序是对冒泡排序的一种改进，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
因快速排序较难，我们试着列出他的过程：
设待排序的数据序列放在列表lst中，可描述为lst[s…t]，快速排序是在数据序列中任取一个数据(一般取lst[s])作为参照(又称为基准或枢轴)，以lst[s]为基准重新排列其余的所有数据，方法是：
所有关键字比基准小的放lst[s]之前；
所有关键字比基准大的放lst[s]之后。
设置两个下标索引变量low，high，初值为列表的第1个和最后一个数据元素的位置。设两个变量i，j，初始时令i=low，j=high，以lst[low]作为基准，将lst[low]保存在变量k中。
（1）从j所指位置向前搜索：将lst[low]与lst[j]进行比较： ◆若lst[low] ≤ lst[j]：令j=j-1，然后继续进行比较，直到i=j或k > lst[j]为止； ◆若lst[low] > lst[j]：将lst [j]放进lst [i]，腾空lst [j]， 且令i=i+1； （2）从i位置起向后搜索：将k与lst[i]进行比较： ◆ 若k ≥ lst[i]：令i=i+1，然后继续进行比较，直到i=j或k < lst[i]为止； ◆ 若k < lst[i]：将lst [i]放进lst[j]，腾空lst[i]，且令j=j-1； （3）重复（1）、（2），直至i=j为止，i就是k(基准)所应放置的位置。
def quick_sort(lst, low, high): i = low j = high if i >= j: #递归终止的条件 return lst k = lst[i] while i < j: while i < j and lst[j] >= k: j = j-1 lst[i] = lst[j] #将lst[j]放进lst[i],腾空lst[j] while i < j and lst[i] <= k: i = i+1 lst[j] = lst[i] #将lst[i]放进lst[j],腾空lst[i] lst[i] = k #将基准k放入应放置的位置 quick_sort(lst, low, i-1) quick_sort(lst, i+1, high) return lst def main(): list1 = [55, 66, 22, 444, 24, 67, 31, 15, 41] print(list1) high = len(list1)-1 list2=quick_sort(list1, 0, high) print(list2) main()
运行结果：
