动图放上。
排序的核心是比较两个数的大小。两个数的排序很easy,三个数排序也只是两两比较2次,四个数排序也是两两比较两个数。
进行多次的两个数比较,无非是:获得最大值或者最小值,得出最大最小值之后,再在剩下的数里面找出最大最小值。……
冒泡排序升序排序的主要思路:
1,两两比较找到最大值,将其放到数组尾巴处,不再参与排序。
2,剩下的n-1个数继续两两比较找出最大值,放到数组倒数第二个位置。
3,一直比较……
4,直到只有最后两个数比较时,排序完成。
若有错误,请指正。
目录
答:从左往右相邻两个数两两比较。
两两比较找出最大值之后,可以把这个最大值放到一个新数组里面,但这样浪费内存空间。重点是:冒泡排序从左往右两两比较天然的将最大值移到了数组容器最后面。
答:n-1次,当有n个数需要排序,需要两两比较的轮数为n-1次,即需要找出n-1个最大值,最后一个自然为最小。
答:若当前剩下数字个数为n,则需要n-1次。很明显,他就是不停的在未排序的数字中找最大值,自然需要两两比较当前剩余数字的个数-1次。
答:最差情况下的次数为:(n-1)(n-2)(n-3)(n-4)……
1,当一个数组已经排好了顺序,我们再对其排序是毫无意义的。
2,当在排序过程中,提前出现排序完成的情况,但是算法过程还将继续,这也是无意义的。
当在一次找最大值的过程中,没有出现交换两个数情况,即:剩下未排序的数字已经是排好序的了。
设置标志位flag,当在一次找最大值的过程中,没有出现交换两个数情况,则置flag为true,结束排序。
- import random
-
-
- def Bubble_sort(arr: list):
- total_circle = len(arr) - 1
- # 将2,1进行排序,至少需要1轮;
- # 将3,2,1进行排序,第一轮:2,3,1;2,1,3;第二轮:1,2,3。至少需要两轮。
- # ……
- # 将n,n-1,n-2,……进行排序,则至少需要n-1轮
- # 每一轮循环都把当前循环轮中的最大值沉底(冒泡排序:小的数浮出水面,大的数沉到水底)
- for i in range(total_circle): # 外层循环,循环n-1次
- index = 0
- while index <= total_circle - 1: # 内层循环,每轮循环期间,需要两两比较(n-1)-1次
- if arr[index] > arr[index + 1]:
- arr[index], arr[index + 1] = arr[index + 1], arr[index] # 排序算法的核心:比较两个数的大小,进行交换
- index = index + 1 # 从左往右依次比较两个数的大小,索引+1进行移动
- total_circle = total_circle - 1 # 每一轮循环之后,当前轮的最大值会被移到最后面,这个值将不再参加排序。则总循环次数-1。
-
-
- if __name__ == '__main__':
- arr_test = [int(random.random() * 100) for i in range(10)]
- print('排序之前的列表:')
- print(arr_test)
- Bubble_sort(arr_test)
- print('排序之后的列表:')
- print(arr_test)
- import random
-
-
- def Bubble_sort(arr: list):
- total_circle = len(arr) - 1
- # 将2,1进行排序,至少需要1轮;
- # 将3,2,1进行排序,第一轮:2,3,1;2,1,3;第二轮:1,2,3。至少需要两轮。
- # ……
- # 将n,n-1,n-2,……进行排序,则至少需要n-1轮
- # 每一轮循环都把当前循环轮中的最大值沉底(冒泡排序:小的数浮出水面,大的数沉到水底)
- for i in range(total_circle): # 外层循环,循环n-1次
- index = 0
- flag = 0 # 0表示没有交换过
- while index <= total_circle - 1: # 内层循环,每轮循环期间,需要两两比较(n-1)-1次
- if arr[index] > arr[index + 1]:
- arr[index], arr[index + 1] = arr[index + 1], arr[index] # 排序算法的核心:比较两个数的大小
- flag = 1
- index = index + 1 # 从左往右依次比较两个数的大小,索引+1进行移动
- if flag == 0: # 当在一次找最大值的过程中,未交换过两个数,则直接退出排序过程,即退出外层循环。
- print('奇迹!排序过程中发现已经完成排序了')
- break
- total_circle = total_circle - 1 # 每一轮循环之后,当前轮的最大值会被移到最后面,这个值将不再参加排序。则总循环次数-1。
-
-
- if __name__ == '__main__':
- arr_test = [int(random.random() * 100) for i in range(10)]
- print('排序之前的列表:')
- print(arr_test)
- Bubble_sort(arr_test)
- print('排序之后的列表:')
- print(arr_test)
-
-
- # 多运行几次,会出现提前排好序的情况