排序–冒泡排序

目录

时间复杂度

    ：降序转为升序时的双for循环

空间复杂度

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

思路

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

    使用外循环来挑选范围

    使用内循环两两比对交换

基本实现

    升序

    降序

问题

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

改进一

问题

    每次内循环的范围只能一步一步缩小，对于如下待排数组[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，发现无交换发生，此时排序结束

改进二