冒泡排序运行的时间和归并排序运行时间的比较

- 日理万妓 2024-02-17 14:26 6阅读 0赞

下面是一万个随机数据采用冒泡排序所用的时间（由于老师给的一百万个数据太大，我在等了半小时后没有结果，），具体代码如下；

冒泡排序：

运行结果： ![SouthEast][]

归并排序：

package three.suanfa.whp;
    
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileOutputStream;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.ArrayList;
    
    public class mergeSort {
    
    	/**
    	 * @王海平
    	 */
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		double start_all = System.currentTimeMillis();
    		String path = "txt/largeW.txt";
    		ArrayList<Integer> list=read(path); 
    		double start = System.currentTimeMillis();
    		mergeSort(list);
    		double end = System.currentTimeMillis();
    		System.out.println("归并排序时间为: " + (end - start)+"毫秒");
    		// 写入txt文件
    		write(list);
    		System.out.println("写入完成");
    		double end_all = System.currentTimeMillis();
    		System.out.println("总运行时间为: " + (end_all - start_all)+"毫秒");
    	}
    	//创建并写入largeW_merge.txt文件
    	public static void write(ArrayList<Integer> list) {
    		File f = new File("txt/largeW_merge.txt");
    		FileOutputStream fou = null;
    		try {
    
    			fou = new FileOutputStream(f, true);// true,设置可追加
    
    			for (int i = 0; i < list.size(); i++) {
    				String s = String.valueOf(list.get(i));
    				String a = "" + s + "\t\n";
    				// byte []bytes=new byte[1024];
    				// 如何把string转换byte数组
    				fou.write(a.getBytes());
    
    			}
    		} catch (Exception e) {
    			// TODO: handle exception
    			e.printStackTrace();
    		} finally {
    			try {
    				fou.close();
    			} catch (Exception e) {
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    	}
    	
    	//归并排序
    	public static void mergeSort(ArrayList<Integer> data) {  
            sort(data, 0, data.size() - 1);  
        }  
      
        public static void sort(ArrayList<Integer> data, int left, int right) {  
            if (left >= right)  
                return;  
            // 找出中间索引  
            int center = (left + right) / 2;  
            // 对左边数组进行递归  
            sort(data, left, center);  
            // 对右边数组进行递归  
            sort(data, center + 1, right);  
            // 合并  
            merge(data, left, center, right);  
          
        }  
      
      
        public static void merge(ArrayList<Integer> data, int left, int center, int right) {  
            // 临时数组  
            int[] tmpArr = new int[data.size()];  
            // 右数组第一个元素索引  
            int mid = center + 1;  
            // third 记录临时数组的索引  
            int third = left;  
            // 缓存左数组第一个元素的索引  
            int tmp = left;  
            while (left <= center && mid <= right) {  
                // 从两个数组中取出最小的放入临时数组  
                if (data.get(left) <= data.get(mid)) {  
                    tmpArr[third++] = data.get(left++);  
                } else {  
                    tmpArr[third++] = data.get(mid++);  
                }  
            }  
            // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）  
            while (mid <= right) {  
                tmpArr[third++] = data.get(mid++);  
            }  
            while (left <= center) {  
                tmpArr[third++] = data.get(left++);  
            }  
            // 将临时数组中的内容拷贝回原数组中  
            // （原left-right范围的内容被复制回原数组）  
            while (tmp <= right) {
            data.set(tmp, tmpArr[tmp++]);
            }  
        }  
    	
    	
    	//读取文件到int数组
    	public static ArrayList read(String path) {
    		ArrayList<Integer> list = new ArrayList<Integer>();
    		BufferedReader input = null;
    		try {
    			FileReader in = new FileReader(path);
    			input = new BufferedReader(in);
    			String ss;
    			try {
    				while ((ss = input.readLine()) != null) {
    					String[] s = ss.split("\r\n");
    					for (int i = 0; i < s.length; i++) {
    						list.add(Integer.parseInt(s[i].trim())); // 将String s中的内容添加到动态数组中
    					}
    				}
    			} catch (IOException e) {
    				// TODO 自动生成的 catch 块
    				e.printStackTrace();
    			}
    			in.close();
    			input.close();
    		} catch (Exception e) {
    			// TODO 自动生成的 catch 块
    			e.printStackTrace();
    		}
    
    		return list;
    	}
    
    }

运行结果：

![SouthEast 1][]

排序结果一样：

![SouthEast 2][]

总结：从上面的排序时间来说，归并排序的时间明显比冒泡排序用的时间少！经查资料（数据结构）得知，归并排序是一种比较稳定的排序方法！

总的时间代价是O(nlog2n),而冒泡排序的时间是O(n的二次方)

[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/6db7553f31664c7391ad2e3da87d0eba.png
[SouthEast 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/0db1a21fd8c546c5b9db65af64014330.png
[SouthEast 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/97fd37e3f04446abb05a515f5f8df48b.png