冒泡排序
1 # 思想就是相邻两数比较交换顺序,每一轮排序可以选出最大或最小值 2 list = [26, 4, 2, 52, 34, 234, 35, 23] 3 # print(list[0]) 4 x = 0 5 y = 1 6 z = len(list) 7 while z >= 1: 8 for i in range(1, z): # 这样一趟排序可以把列表的最小值排出，排length - 1趟就可以排完 9 if list[x] < list[y]: 10 temp = list[x] 11 list[x] = list[y] 12 list[y] = temp 13 else: 14 pass 15 x += 1 16 y += 1 17 i += 1 18 # 每完成一次快速排序就重置xy的值 19 x = 0 20 y = 1 21 z -= 1 22 23 print(list)
选择排序
1 # 选择排序 2 # 思想就是每次选出组内的最值，放到最后或者最前面，排序长度依次减少 3 list = [26, 4, 2, 52, 34, 234, 35, 23] 4 n = 0 5 # min = list[n] #这里选择变量代替列表元素就不行，因为交换值的时候修改的是变量值，而不是列表元素 6 while n < len(list): 7 for i in range(n+1,len(list)): 8 if list[i] < list[n]: 9 temp = list[n] 10 list[n] = list[i] 11 list[i] = temp 12 n += 1 13 14 15 print(list)
插入排序
1 # 插入排序 这个时间复杂度不确定，会根据原始的顺序程度来决定，最差情况是n^2 2 # 思想就是把还没有排序的元素插入到已经拍好序的列表中 把列表排序想象为新列表元素由少到多的插入，关键就是key和i下标的移动， 3 test = [26, 4, 2, 52, 34, 234, 35, 23] 4 5 list = [] 6 for i in range(0, len(test)): 7 list.append(test[i]) 8 key = list[i] 9 if i > 0: #如果列表只有一个元素，那他肯定是有序的，从第二个元素开始插入 10 while list[i] < list[i - 1]: 11 list[i] = list[i - 1] 12 i -= 1 13 list[i] = key 14 if i == 0: 15 break 16 17 print(list)
快速排序
# 快速排序 思想就是分治法，把大于的放一边，小于的放一边，然后递归的对大的列表、小的列表进行快速排序
1 # 快排的工作过程分为三步： 2 # 选择基准值pivot，将列表划分为两个子列表：小于基准值和大于基准值。 3 # 然后对着两个列表进行快速排序 4 # 合并结果 5 6 def quicksort(arr): 7 if len(arr) < 2: 8 return arr 9 else: 10 pivot_index = 0 11 pivot = arr[pivot_index] 12 pivot_less = [i for i in arr[pivot_index + 1:] if i <= pivot] 13 pivot_more = [i for i in arr[pivot_index + 1:] if i > pivot] 14 return quicksort(pivot_less) + [pivot] + quicksort(pivot_more) # 递归的对子列进行快速排序 15 16 17 def testquicksort(): 18 import random 19 seq = list(range(10)) 20 21 random.shuffle(seq) # 对列表进行随机排序 22 print(seq) 23 sortseq = quicksort(seq) 24 print(sortseq) 25 26 27 testquicksort()
看一个排序是否稳定主要是看他排序完成后，值相同的元素是否可能交换顺序。
选择排序，希尔排序，快速排序，是不稳定的