注册

冒泡排序的进化过程

基础版本


所有情况下时间复杂度都为O(n2n^2n2)


public static void bob(int[] array) {
// 总共比较n-1轮
for (int i = 0; i < array.length - 1; i++) {
// 因为每次都能确定一个最大元素,所以每次都能少比较一次
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}

上述算法简单粗暴,对任意数组上来就是两层for套着猛干。


如果现在有个有序数组,比如{1,2,3,4,5,6,7,8},也会白费力气去浪费cpu,这是不必要的。怎么避免呢?


我们看到,如果元素整体有序,那么上述代码中的


if (arr[j] > arr[j + 1])

就永远不会满足,那么就不会发生元素的交换,所以我们可以添加个布尔值,来判断是否发生了元素交换,如果没发生,则认为已经整体有序了,直接跳出即可。如下:


1 进阶版本


这里添加了一个boolean来判断本次是否有元素交换,没有则提前结束。


private static void bob2(int[] arr) {
int length = arr.length;
for (int i = 0; i < length; i++) {
boolean swap = false;
for (int j = 0; j < length - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

swap = true;
}
}
if (!swap) break;
}
}

上述代码可以避免对整体有序的数组瞎排序。但是,如果一个数组不是整体有序,而是局部有序呢,比如{4,3,2,1,5,6,7,8},我们观察到后半部分是不需要参加排序的,也就是说,只需要将前半部分排序即可。


所以,我们就要确定从哪开始的元素是有序的,也就是确定有序区开始的下标


那么,怎么确定这个下标呢?


我们可以想一下,对于冒泡排序,如果后面的元素比前面的大,才交换,否则就不交换,也就是说,最后一次发生交换的位置,其后面一定是有序的。比如在位置i发生了交换,i后面没有发生过交换,那么i后面一定是有序的,否则i后面就还会发生交换。


所以,每次元素最后一次交换的位置,就是有序区下标的起点,也是无序区下标的终点。


定义一个下标,每次有元素交换就更新下标,下标后面的元素就是有序的,每次比较只比较下标前面的元素即可


代码如下:


2 高阶版本


private static void bob3(int[] arr) {
int length = arr.length;
int lastSwapIndex = 0;
// 定义有序区起始点,也就是无序区终点
int sortedBorder = length - 1;
for (int i = 0; i < length; i++) {
boolean swap = false;
// 只比较无序区
for (int j = 0; j < sortedBorder; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap = true;
// 发生了交换,就更新下标
lastSwapIndex = j;
}
}
// 更新下标
sortedBorder = lastSwapIndex;
if (!swap) break;
}
}

上述代码就可以解决局部有序但整体无序的情况。


但是我们发现,上面的代码,都是从左向右比较的,如果数组是{2,3,4,5,6,7,8,1}这样呢,也是局部有序,但是,如果从左往右比,则很费时间,而从右往左比,则一轮就能结束。


但是!如果从右往左比的话,遇见{8,1,2,3,4,5,6,7}这样的又跪了,怎么办呢?我们可以采用双向比较法,也就是一次从左向右比,一次从右向左比,这就叫鸡尾酒排序


现在我们使用鸡尾酒排序(双向排序),每次排序后交换方向,代码如下:


3 最终版本(鸡尾酒排序)


private static void bob4(int[] arr) {
int length = arr.length;
for (int i = 0; i < (length >>> 1); i++) {
boolean swap = false;
// 从左到右
for (int j = 0; j < length - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
swap = true;
}
}

if (!swap) break;

// 从右到左
swap = false;
for (int j = length - 1; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
swap = true;
}
}

if (!swap) break;
}
}

// 交换元素
private static void swap(int[] arr, int i, int j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}

总结


我们虽然针对冒泡排序进行了多次优化,但是它的时间复杂度还是O(n2),这是无法避免的,因为冒泡排序每次只是交换相邻元素,也就是只消除了一个逆序对,凡是通过交换相邻元素进行的排序,其时间复杂度都是O(n2)


为什么呢?因为交换相邻元素每次只消除了一个逆序对。我们来证明下。


学过<线性代数>的应该知道逆序这个定义。



在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。



证明: 凡是通过交换相邻元素进行的排序,其时间复杂度都是O(n2n^2n2)


假设现有任意序列L,其共有n个元素,则其共能组成Cn2C_n^2Cn2个数对(从n个元素中,挑出2个元素组成的数对),也就是(n(n−1)2)(\frac{n(n-1)}{2})(2n(n−1))个, 其中逆序数为a;然后取其反序列Lr,其逆序数为b,而且b=(n(n−1)2)(\frac{n(n-1)}{2})(2n(n−1))-a,因为原来L中的顺序对,在Lr中全变成了逆序对,而且对于任意的数对,要么是顺序,要么是逆序(相同的可以认为是顺序),所以a+b=(n(n−1)2)(\frac{n(n-1)}{2})(2n(n−1))


所以,L和Lr的总逆序对就是(n(n−1)2)(\frac{n(n-1)}{2})(2n(n−1)),那么单个L的逆序对就是(n(n−1)4)(\frac{n(n-1)}{4})(4n(n−1)),当n趋近于+∞时,就是n2n^2n2,而通过交换相邻元素每次只能消除一个逆序对,所以总共需要交换n2n^2n2次,所以相应算法的时间复杂度就是O(n2n^2n2)。


为什么交换相邻元素只能消除一个逆序对呢,因为只改变了相邻俩元素的位置,它俩前后的该比它大还是比它大,该比它小还是比它小。比如{5,4,3,2,1},我们交换了3和2,变为{5,4,2,3,1},我们发现,只是消除了{1,2}这个逆序对,前面的5和4,还是比它俩大,后面的1,还是比它俩小,所以只消除了一个逆序对,这里不再废话。


证明完毕。


其实,我们可以扩展一下,凡是每次只能消除一个逆序对的算法,其时间复杂度都是O(n2n^2n2)。也不再废话。


作者:奔波儿灞取经
链接:https://juejin.cn/post/7018816132815519757
来源:稀土掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

0 个评论

要回复文章请先登录注册