啊,因为每次相邻交换不管是什么排序,最多都减少一个逆序对。
而冒泡排序能保证每次交换都能减少一个逆序对。
因此冒泡排序的次数一定最少。
by yummy @ 2023-01-16 08:06:22
相邻两个交换,逆序对个数的变化是 $\pm1$
冒泡排序恰好是每一次交换都使逆序对个数 $-1$,所以最优
by yukimianyan @ 2023-01-16 08:07:04
@[yukimianyan](/user/509229) 谢谢大佬
by p31415 @ 2023-01-16 08:24:14
@[yummy](/user/101694) 谢谢您
by p31415 @ 2023-01-16 08:24:30
选择也行。
https://www.luogu.com.cn/record/104574482
by liujiayao @ 2023-03-13 11:42:32