算法之冒泡排序学习
冒泡排序算法重新学习。
交换排序算法有以下几种:
- 冒泡排序
- 快速排序
冒泡排序算法
冒泡排序算法描述:比较相邻两个元素大小,如果是反序,就将两个元素进行交换。
冒泡排序代码示例
/**
* 冒泡排序
*/
public class BubbleSort {
/**
* 冒泡排序
* @param source 待排序数组
* @param asc 是否升序 true:升序(从小到大)false:降序(从大到小)
*/
public void bubbleSort(Integer[] source, boolean asc) {
for (int i = 1; i < source.length; i++) {
for (int j = 0; j < source.length - i; j++) {
if (asc ? source[j] > source[j + 1] : source[j] < source[j + 1]) {
int temp = source[j];
source[j] = source[j + 1];
source[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
System.out.println("before: " + Arrays.asList(array));
new BubbleSort().bubbleSort(array, true);
System.out.println("after: " + Arrays.asList(array));
}
}
算法改进
原始冒泡排序,如果在中间某一趟就已经排序完成了,后续的每一趟比较都不会有任何变化,后面这些都是多余的,可以使用一个标志位来进行控制。如果某一趟没有交换元素,说明已经排好序,下次循环判断标志位就可以直接结束。优化后代码如下:
/**
* 冒泡排序
*/
public class BubbleSort {
/**
* 冒泡排序
* @param source 待排序数组
* @param asc 是否升序 true:升序(从小到大)false:降序(从大到小)
*/
public void bubbleSort(Integer[] source, boolean asc) {
// 标志位
boolean exchange = true;
for (int i = 1; i < source.length && exchange; i++) {
exchange = false;
for (int j = 0; j < source.length - i; j++) {
if (asc ? source[j] > source[j + 1] : source[j] < source[j + 1]) {
Integer temp = source[j];
source[j] = source[j + 1];
source[j + 1] = temp;
exchange = true;
}
}
}
}
public static void main(String[] args) {
Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
System.out.println("before: " + Arrays.asList(array));
new BubbleSort().bubbleSort(array, true);
System.out.println("after: " + Arrays.asList(array));
}
}
冒泡排序算法分析
时间复杂度
- 最好情况,数据已经排好序,只需要一趟扫描,比较n次,没有数据移动,时间复杂度O(n)
- 最坏情况,数据是随机排列或者反序排列,需要n-1趟扫描,比较和移动次数都是$n^2$,时间复杂度$O(n^2)$
进行冒泡排序的序列,序列越接近有序,效率越高。
空间复杂度
算法中使用一个temp变量占用一个存储单元,用于交换两个元素,空间复杂度为O(1)
算法的稳定性
冒泡排序算法中两两元素之间进行排序,相等记录之间经过排序后,次序保持不变,因此冒泡排序是稳定的。
适用场景
- 数据规模较小,元素基本有序,可以使用冒泡排序。
需要优化的地方
冒泡排序中,假设元素是按照反序排列,则一趟中,一个元素每次比较都需要交换,元素数据每次都要移动,存在重复移动数据的问题。可以使用快速排序来减少重复数据移动问题。
参考内容
- 《数据结构(Java版)》