百度网站地图制作,WordPress 文章编辑,seo 整站优化,分销系统解决方案冒泡排序–时间复杂度n^2
对数组序列从前向后依次比较相邻两个元素的大小,若逆序则两个元素交换位置如果一趟下来没有发生交换,则说明序列有序,可以在序列中设置一个标志flag判断元素是否发生交换,从而来减少不必要的比较(在写完排序算法后再写)小结:一共进行数组大小-1次的外…冒泡排序–时间复杂度n^2
对数组序列从前向后依次比较相邻两个元素的大小,若逆序则两个元素交换位置如果一趟下来没有发生交换,则说明序列有序,可以在序列中设置一个标志flag判断元素是否发生交换,从而来减少不必要的比较(在写完排序算法后再写)小结:一共进行数组大小-1次的外部循环每一趟排序的次数在逐渐地减少在一趟排序中,没有发生一次交换,则可以提前结束冒泡排序第一趟排序,将最大的数排在最后,第2趟把第二大的数排在倒数第二个 演变过程:
int arr[]{3,9,-1,10,-2};
第1次排序结果[3, -1, 9, -2, 10]
第2次排序结果[-1, 3, -2, 9, 10]
第3次排序结果[-1, -2, 3, 9, 10]
第4次排序结果[-2, -1, 3, 9, 10]
代码实现:
import java.util.Arrays;
public class BubbleSort {public static void main(String[] args) {int arr[] {3, 9, -1, 10, -2};//第一趟排序,将最大的数排在最后int temp 0;//临时变量//外部循环控制整个的循环次数for (int i 0; i arr.length - 1; i) {//控制相邻元素的交换次数for (int j 0; j arr.length - 1 - i; j) {//如果前面的数比后面的数大则交换if (arr[j] arr[j 1]) {temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}System.out.println(第 (i1) 次排序结果 Arrays.toString(arr));}}
}
优化:在排序循环完成之前就已经有序了,使用标志flag 优化之前: int arr[] {3, 9, -1, 10, 20};
第1次排序结果[3, -1, 9, 10, 20]
第2次排序结果[-1, 3, 9, 10, 20]
第3次排序结果[-1, 3, 9, 10, 20]
第4次排序结果[-1, 3, 9, 10, 20]
优化之后: int arr[] {3, 9, -1, 10, 20};
第1次排序结果[3, -1, 9, 10, 20]
第2次排序结果[-1, 3, 9, 10, 20]实现代码: 在每一次排序完后,进行判断是否有过交换
import java.util.Arrays;public class BubbleSort {public static void main(String[] args) {int arr[] {3, 9, -1, 10, 20};boolean flag false;//标志变量,表示是否进行过交换//第一趟排序,将最大的数排在最后int temp 0;//临时变量//外部循环控制整个的循环次数for (int i 0; i arr.length - 1; i) {//控制相邻元素的交换次数for (int j 0; j arr.length - 1 - i; j) {//如果前面的数比后面的数大则交换if (arr[j] arr[j 1]) {flagtrue;//交换过temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}if (!flag){//在一趟排序中,一次交换都没有发生过break;}else {flagfalse;//重置flag,进行下一次交换}System.out.println(第 (i 1) 次排序结果 Arrays.toString(arr));}}
}
时间测试:
实现思路: //测试时间Date date2 new Date();//格式化时间SimpleDateFormat simpleDateFormat2 new SimpleDateFormat(yyyy-MM-dd HH:mm:ss);String dateStr2 simpleDateFormat2.format(date2);System.out.println(排序后的时间: dateStr2);排序前的时间: 2020-12-09 16:43:12
排序后的时间: 2020-12-09 16:43:22代码实现:
import java.text.SimpleDateFormat;
import java.util.Date;public class BubbleSort {public static void main(String[] args) {int arr[] new int[80000];for (int i 0; i 80000; i) {arr[i] (int) (Math.random() * 80000);//生成[0,80000)的随机数}//测试时间Date date1 new Date();//格式化时间SimpleDateFormat simpleDateFormat new SimpleDateFormat(yyyy-MM-dd HH:mm:ss);String dateStr simpleDateFormat.format(date1);System.out.println(排序前的时间: dateStr);boolean flag false;//标志变量,表示是否进行过交换//第一趟排序,将最大的数排在最后int temp 0;//临时变量//外部循环控制整个的循环次数for (int i 0; i arr.length - 1; i) {//控制相邻元素的交换次数for (int j 0; j arr.length - 1 - i; j) {//如果前面的数比后面的数大则交换if (arr[j] arr[j 1]) {flag true;//交换过temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}if (!flag) {//在一趟排序中,一次交换都没有发生过break;} else {flag false;//重置flag,进行下一次交换}}//测试时间Date date2 new Date();//格式化时间SimpleDateFormat simpleDateFormat2 new SimpleDateFormat(yyyy-MM-dd HH:mm:ss);String dateStr2 simpleDateFormat2.format(date2);System.out.println(排序后的时间: dateStr2);}
}
参考B站尚硅谷视频–冒泡排序
