网站开发的目的意义特色创新,无忧传媒在短视频领域的成就,最好的品牌设计网站建设,移动端产品冒泡排序以及改进方案
介绍#xff1a;
冒泡排序属于一种典型的交换排序#xff08;两两比较#xff09;。冒泡排序就像是把一杯子里的气泡一个个往上冒一样。它不断比较相邻的元素#xff0c;如果顺序不对就像水泡一样交换它们的位置#xff0c;直到整个序列像水泡一样…冒泡排序以及改进方案
介绍
冒泡排序属于一种典型的交换排序两两比较。冒泡排序就像是把一杯子里的气泡一个个往上冒一样。它不断比较相邻的元素如果顺序不对就像水泡一样交换它们的位置直到整个序列像水泡一样按照大小顺序排列好。当它发现一轮遍历中没有发生交换就像是水泡都冒完了一样就知道排序完成了。
图示 冒泡排序性能
算法最好时间最坏时间平均时间额外空间稳定性冒泡O(nO(n2)O(n2)1稳定
普通版本的冒泡排序
通过简单的两层遍历就可以实现了
for (int i 0; i array.length; 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;}}
}第一次改进
当一个数组大小不是很混乱的时候我们没必要每次都去交换
例如2,1,3,4,6 这样的数组我们在第一次交换的时候就已经排好序了1,2,3,4,6,我们无需再基于1,2,3,4,6排序改进如下
for (int i 0; i array.length; i) {int flag false; // 是否发生交换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;flag true; // 发生了交换}if(!flag) { // 如果没有发生交换跳出循环,无需比对后面的break;}}}第二次改进
最后一次交换位置将整个数组分为了两部分之前是未排序部分之后是已排序部分。如此一来下一次冒泡排序就只需在未排序部分进行冒泡排序即可。 根据这个思路再进行代码改进
public class BubbleSort {// 冒泡排序算法实现public static void bubbleSort(int[] array) {if (array null || array.length 0) {return;}int sortIndex array.length - 1; // 初始排序边界为数组末尾int lastChange 0; // 记录最后一次交换的位置for (int i 0; i array.length; i) {boolean flag false; // 标记是否发生交换for (int j 0; j sortIndex; j) {if (array[j] array[j 1]) {int temp array[j];array[j] array[j 1];array[j 1] temp;flag true;lastChange j; // 更新最后一次交换的位置}}sortIndex lastChange; // 更新排序边界if (!flag) { // 若未发生交换说明数组已排序结束排序break;}}}public static void main(String[] args) {int[] arr {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println(排序后的数组:);for (int i : arr) {System.out.print(i );}}
}
