数据结构学习笔记：冒泡排序(Java)

1.原始版本算法思想对于待排序列从左到右依次将相邻元素两两比较将更大的元素交换到右边。每遍历一次后待排序列中的最大元素将被移动到最右侧进入已排序列。同时还有若干个较大的元素被向右移动了数次。不断重复待排序列逐渐缩小直至排列完毕。当然也可以在遍历中将更小元素向左冒泡。从算法上二者效率一致但由于CPU特性正序读取数组的效率更高。以下是一次循环的图示代码public static void bubbleSort(int[] array) { // maxIndex为待排序列的右边界 for (int maxIndex array.length - 1; maxIndex 0; maxIndex--) { for (int i 0; i maxIndex; i) { if (array[i] array[i 1]) { swap(array, i , i 1); } } } } private static void swap(int[] array, int a, int b) { int temp array[a]; array[a] array[b]; array[b] temp; }2. 优化1优化思想对于长度为n的序列原方法必然要进行n-1次遍历。若在某次遍历的过程中没有出现交换操作说明整个序列已经排好了不必进行后续的循环了。可以设置flag作为标记提高效率。代码public static void bubbleSort2(int[] array) { boolean flag true; // flag为true表示还未排好 for (int maxIndex array.length - 1; maxIndex 0 flag; maxIndex--) { flag false; for (int i 0; i maxIndex; i) { if (array[i] array[i 1]) { flag true; // 发生交换说明可能还未排好设置flag为true swap(array, i , i 1); } } } }3. 优化2优化思想若当前的待排序列右侧若干个元素已经是排好的那么在一次遍历中这些元素不会被交换下次遍历可以跳过这些元素遍历更小的区间。下次遍历的右边界为本次遍历最后一次发生交换的位置。代码public static void bubbleSort3(int[] array) { int newIndex; // 用于记录下次遍历的右边界 int maxIndex array.length - 1; // 待排序列的右边界 do { newIndex 0; for (int i 0; i maxIndex; i) { if (array[i] array[i 1]) { newIndex i; // 下次遍历的区间可能为[0, i] swap(array, i, i 1); } } maxIndex newIndex 1; // 由于循环条件为imaxIndex所以要加1 } while (newIndex 0); // newIndex0说明没有交换排序完成 }PS遍历后newIndex为0说明没有交换结束循环即优化1的思想4. 时间复杂度最好情形原始数组已排好共需要经过n-1次比较时间复杂度为O(n)最坏情形原始数组倒序排序第i次循环要经历n-i次比较n-i次交换次数均为时间复杂度为