冒泡排序 小白学demo_day2

冒泡排序的过程：

重复地走访要排序的元素，依次比计较两个相邻的元素，如果他们的顺序错误就把他们交换过来。走访元素的工作室重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

简单说，就是比较相邻的两个元素，将值大的元素交换到右边

是否稳定

如果遇到相等的值不进行交换，那这种排序方式是稳定的排序方式，因此，冒泡排序是一种稳定排序算法

算法

N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为（N-i）次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数

时间复杂度

1，如果我们的数据正序，只需要走一趟即可完成排序，所需的比较次数C和记录移动次数M均达到最小值，即：C min=n-1; M min = 0;所以，最好的时间复杂度为O(n)

2，如果很不幸，我们的数据是反序的，则需要进行n-1趟排序，每趟排序要进行n-i次比较（1<=i<=n-1），且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

所以，最终的时间复杂度为：O(n^2)

冒泡排序的示例

[2  4  3  1  6  5]         初始状态序列   
[2  3  1  4  5][6]         第一次冒泡结束
[2  1  3  4][5  6]         第二次冒泡结束
[1  2  3][4  5  6]         第三次冒泡结束
[1  2][3  4  5  6]         第四次冒泡结束
[1  2  3  4  5  6]         第五次冒泡结束

冒泡排序常规代码

void bubble_sort(int[] arr,int len) {//一定要记住判断边界条件if(arr == null || len < 2) {return;}for(int i = 0;i < len-1; i++) {//第i趟比较for(int j = 0; j < len -1 -i; i++){//开始进行比较，如果前面值比后面值大，那就交换位置if (arr[j] > arr[j+1]) {int t = arr[j];arr[j] = arr[j+1];arr[j+1] = t;}}}System.out.println("最终得到的数组是：")for (int k = 0; k< arr.length;k++) {System.out.println(arr[k]+"");}
}

如果，设置一个标志位，不再进行数据交换，说明已经排序完成，则无需再进行交换

冒泡排序的简单优化代码:

void bubble_sort(int[] arr) {if(arr == null || arr.length < 2) {return;}int flag = 0;for(int i = 0; i < arr.length; i++) {for( int j = 0; j < arr.length -1 -i; j++) {if(arr[j] > arr[j+1]) {int t = arr[j];arr[j] = arr[j+1];arr[j+1] = t;flag = 0; //发生交换，标志位置为0}}}System.out.println("第%d遍最终结果：",i+1);for(int count : list) {System.out.println(count);}System.out.println("");if (flag == 1) {return;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！