昨天看网易公开课中可汗学院的视频实现排序，就想着写一下排序，暑假上课也没时间弄其他的，
乘着午休来码一码，积累自己的代码笔记。
插入排序是指有一个有序的列表，往这个列表里插入一个数，插入后列表依旧有序
它的时间复杂度平均为O(n^2) 不适合数据量特别大的 数据量很小是个不错的选择
1 #插入排序 2 a = [7, 1, 3, 2, 8, 6] 3 4 def insert_sort(list): 5 for i in range(1,len(list)): 6 tmp = a[i] 7 j = i - 1 8 while j >= 0: 9 if a[j] > tmp: 10 a[j+1] = a[j] 11 a[j] = tmp 12 j -= 1 13 return list 14 15 a = insert_sort(a) 16 17 print(a)
接下来是最经典的冒泡排序 比较两个相邻的列表中的元素
最好时间复杂度为O(n) 最坏时间复杂度为O(N^2) 总的平均时间复杂度为O(N^2)
1 #冒泡排序 2 a = [7, 1, 3, 2, 8, 6] 3 4 def bubble_sort(list): 5 for i in range(len(list)-1): 6 for j in range(i+1,len(list)): 7 if list[i] > list[j]: 8 list[i], list[j] = list[j], list[i] 9 return list 10 11 a = bubble_sort(a) 12 13 print(a)
直接选择排序：
第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕
1 #直接选择排序 2 a = [7, 1, 3, 2, 8, 6] 3 4 def select_sort(list): 5 for i in range(0,len(list)): 6 min = i 7 for j in range(i+1,len(list)): 8 if a[min] > a[j]: 9 min = j 10 list[min], list[i] = list[i], list[min] 11 return list 12 13 a = select_sort(a) 14 15 print(a)
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
