java记录 - 归并排序

Love The Way You Lie 2023-02-12 05:45 67阅读 0赞

### 文章目录 ###

*   *  其他排序算法

### 归并排序 ###

思想：  
![在这里插入图片描述][20201126200818242.png]  
![在这里插入图片描述][2020112620082958.png]  
代码实现：

import java.text.SimpleDateFormat; 
    import java.util.Arrays;
    import java.util.Date;
    
    public class MergetSort { 
    
    	public static void main(String[] args) { 
    
    		// 创建要给 80000 个的随机的数组
    		int[] arr = new int[80000000];
    		for (int i = 0; i < 80000000; i++) { 
    			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
    		}
    		System.out.println("排序前"); 
    		Date data1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); 
    		String date1Str = simpleDateFormat.format(data1);
    		System.out.println("排序前的时间是=" + date1Str);
    
    		int temp[] = new int[arr.length]; //归并排序需要一个额外空间
    		
    		mergeSort(arr, 0, arr.length - 1, temp);//八千万数据15秒
    
    		Date data2 = new Date();
    		String date2Str = simpleDateFormat.format(data2); 
    		System.out.println("排序前的时间是=" + date2Str);
    
    	}
    
    	//分+合方法
    	public static void mergeSort(int[] arr, int left, int right, int[] temp) { 
    
    		if(left < right) { 
    			int mid = (left + right) / 2; //中间索引
    			//向左递归进行分解
    			mergeSort(arr, left, mid, temp);
    			// 向 右 递 归 进 行 分 解 
    			mergeSort(arr, mid + 1, right, temp);
    			//合并
    			merge(arr, left, mid, right, temp);
    
    		}
    	}
    
    	//合并的方法
    	/* * * *@param arr 排序的原始数组 *@param left 左边有序序列的初始索引 *@param mid 中间索引 *@param right 右边索引 *@param temp 做中转的数组 */
    	public static void merge(int[] arr, int left, int mid, int right, int[] temp) { 
    
    		int i = left; // 初始化 i, 左边有序序列的初始索引
    		int j = mid + 1; //初始化 j, 右边有序序列的初始索引
    		int t = 0; // 指向 temp 数组的当前索引
    
    		//(一)
    		//先把左右两边(有序)的数据按照规则填充到 temp 数组
    		//直到左右两边的有序序列，有一边处理完毕为止
    		while (i <= mid && j <= right) { 
    			//继续
    			//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
    			//即将左边的当前元素，填充到 temp 数组
    			// 然 后 t++, i++ 
    			if(arr[i] <= arr[j]) { 
    				temp[t] = arr[i]; 
    				t += 1;
    				i += 1;
    			} else {  //反之,将右边有序序列的当前元素，填充到 temp 数组
    				temp[t] = arr[j]; 
    				t += 1;
    				j += 1;
    			}
    		}
    		
    		//(二)
    		//把有剩余数据的一边的数据依次全部填充到 temp
    		while( i <= mid) {  //左边的有序序列还有剩余的元素，就全部填充到 temp 
    			temp[t] = arr[i];
    			t += 1;
    			i += 1;
    
    		}
    
    		while( j <= right) {  //右边的有序序列还有剩余的元素，就全部填充到 temp 
    			temp[t] = arr[j];
    			t += 1;
    			j += 1;
    
    		}
    		
    		//(三)
    		//将 temp 数组的元素拷贝到 arr
    		//注意，并不是每次都拷贝所有
    		t = 0;
    		int tempLeft = left; //
    		
    		//第一次合并 tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3
    		//最后一次 tempLeft = 0 right = 7
    		while(tempLeft <= right) { 
    			arr[tempLeft] = temp[t];
    			t += 1;
    			tempLeft += 1;
    		}
    	}
    }

## 其他排序算法 ##

插入排序：  
[https://blog.csdn.net/bell\_love/article/details/106319609][https_blog.csdn.net_bell_love_article_details_106319609]  
快速排序：  
[https://blog.csdn.net/bell\_love/article/details/106319697][https_blog.csdn.net_bell_love_article_details_106319697]  
选择排序：  
[https://blog.csdn.net/bell\_love/article/details/106319578][https_blog.csdn.net_bell_love_article_details_106319578]  
希尔排序：  
[https://blog.csdn.net/bell\_love/article/details/106319660][https_blog.csdn.net_bell_love_article_details_106319660]  
冒泡排序：  
[https://blog.csdn.net/bell\_love/article/details/106317675][https_blog.csdn.net_bell_love_article_details_106317675]  
基数排序：  
[https://blog.csdn.net/bell\_love/article/details/106319787][https_blog.csdn.net_bell_love_article_details_106319787]  
堆排序：  
[https://blog.csdn.net/bell\_love/article/details/106319827][https_blog.csdn.net_bell_love_article_details_106319827]

[20201126200818242.png]: https://img-blog.csdnimg.cn/20201126200818242.png
[2020112620082958.png]: https://img-blog.csdnimg.cn/2020112620082958.png
[https_blog.csdn.net_bell_love_article_details_106319609]: https://blog.csdn.net/bell_love/article/details/106319609
[https_blog.csdn.net_bell_love_article_details_106319697]: https://blog.csdn.net/bell_love/article/details/106319697
[https_blog.csdn.net_bell_love_article_details_106319578]: https://blog.csdn.net/bell_love/article/details/106319578
[https_blog.csdn.net_bell_love_article_details_106319660]: https://blog.csdn.net/bell_love/article/details/106319660
[https_blog.csdn.net_bell_love_article_details_106317675]: https://blog.csdn.net/bell_love/article/details/106317675
[https_blog.csdn.net_bell_love_article_details_106319787]: https://blog.csdn.net/bell_love/article/details/106319787
[https_blog.csdn.net_bell_love_article_details_106319827]: https://blog.csdn.net/bell_love/article/details/106319827