冒泡排序算法实现及优化

一时失言乱红尘 2023-05-22 22:05 75阅读 0赞

相信冒泡排序算法大家都不陌生，今天说一下如何进行优化  
正常的一组数据进行冒泡排序如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU5OTM3Nw_size_16_color_FFFFFF_t_70]  
但是如果一组数据本身就是已经排序好的，如1，2，3，4，5，6，那么它还是会像上面那样的顺序进行排序，通过下面的改变可以很好的优化这一点

直接上代码：

import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    //冒泡排序
    public class MaoPaoSort {
    	public static void main(String[] args) {
    		//int arr[] = { 3, 9, -1, 10, 20 };
    		// 测试一下冒泡排序的速度O(n^2), 给80000个数据，测试
    		// 创建要给80000个的随机的数组
    		int[] arr = new int[80000];
    		for (int i = 0; i < 80000; i++) {
    			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
    		}
    
    		Date data1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String date1Str = simpleDateFormat.format(data1);
    		System.out.println("排序前的时间是=" + date1Str);
    
    		// 测试冒泡排序
    		sort(arr);
    
    		Date data2 = new Date();
    		String date2Str = simpleDateFormat.format(data2);
    		System.out.println("排序后的时间是=" + date2Str);
    
    	}
    
    	// 冒泡排序--已经进行过优化的函数
    	public static void sort(int[] arr) {
    		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;
    				}
    			}
    			//System.out.println("第" + (i + 1) + "趟排序后的数组");
    			//System.out.println(Arrays.toString(arr));
    			if (!flag) { // 在一趟排序中，一次交换都没有发生过
    				break;
    			} else {
    				flag = false; // 重置flag!!!, 进行下次判断
    			}
    		}
    	}
    }

备注：参考视频资料：https://www.bilibili.com/video/BV1E4411H73v?p=56

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU5OTM3Nw_size_16_color_FFFFFF_t_70]: /images/20230521/23795094defc4d0aa8f3d150e0684b7d.png