排序--冒泡排序

2022-01-22 本文已影响0人习惯水文的前端苏

$\bullet$ 目录

$\bullet$ 时间复杂度

$O（n^2）$ ：降序转为升序时的双for循环

$\bullet$ 空间复杂度

O(1):用于交换产生的辅助空间t

$\bullet$ 思路

挑选一个范围做两两向后比对交换，并最终将目标值(最大或最小)排到尾部

使用外循环来挑选范围

使用内循环两两比对交换

$\bullet$ 基本实现

升序

降序

$\bullet$ 问题

由于内循环始终都会跑一遍，若有数组[7,1,2,3,4,5,6]，在外层第一次循环结束后，数组其实已经有序：[1,2,3,4,5,6]。则第二次对[1,2,3,4,5]的排序是不需要的

$\bullet$ 改进一

$\bullet$ 问题

每次内循环的范围只能一步一步缩小，对于如下待排数组[1,2,5,4,3,6,7,8,9],第一次排序后的结果为[1,2,4,3,5,6,7,8,9]

第一次结束后确定最后一位最大，范围缩小一位

第二次i将从0递增到7，但是对于6,7,8,9而言，实际上已经有序，故从5到7的遍历是无意义的

故我们将下一次的范围停留到上一次的最后交换位置，即4的位置

即第二次i从0到4，对应数组[1,2,4,3,5]，排序后将位置停留到3

经过上一个优化后

第三次i从0递增到3，发现无交换发生，此时排序结束

$\bullet$ 改进二