归并排序----java实现

旧城等待， 2022-09-24 05:25 197阅读 0赞

归并排序

归并排序是将两个有序的序列合并成一个新的有序序列。

归并排序：

（1）递归分解数组；

将数组每次折半划分，直到把数组划分为n个长度为1的有序序列。

（2）合并排序数组；

先做两两合并，得到2/n 个有序序列，再两两合并，不断重复这个过程，直到得到一个长度为n的数组。

合并两个排序数组：

（1）先依次比较两个数组中的元素，把较小的那个元素放在辅助数组的对应位置。

（2）如果比较完成，两个数组中还有元素，就依次放在辅助数组的后面。

（3）完成合并后，将辅助数组中的元素复制到原数组中。

public void mergeSort(int array[])
       {
    	   if(array.length == 0 || array == null)
    	   {
    		   return;
    	   }
    	   subMergeSort(array,0,array.length-1);
       }
       private void subMergeSort(int[]array,int left,int right)
       {
    	   if(left < right)
    	   {
    		   //将数组折半划分
    		   int mid = (left + right) / 2;//先拆分数组
    		   subMergeSort(array,left,mid);//将拆分的子数组先排序
    		   subMergeSort(array,mid+1,right);
    		   merge(array,left,mid,right);//合并排序数组
    	   }
    	  
       }
       //合并两个已经排序的数组
       private void merge(int[]array,int left,int mid,int right)
       {
    	   int[]temp = new int[array.length];//辅助数组
    	   int low = left;
    	   int high = mid + 1;
    	   int tmp =left;//辅助数组的索引
    	   //比较两个数组取较小的值放入辅助数组
    	   while(low <= mid && high <= right)
    	   {
    		   if(array[low] < array[high])
    		   {
    			   temp[tmp++] = array[low++];
    		   }
    		   else
    		   {
    			   temp[tmp++] = array[high++];
    		   }
    	   }
    	   //如果上一步比较完，两个数组其中一个依然有剩余的，将剩余的部分放入辅助数组，
    	   while(low <= mid)
    	   {
    		   temp[tmp++] = array[low++];
    	   }
    	   while(high <= right)
    	   {
    		   temp[tmp++] = array[high++];
    	   }
    	   //将辅助数组中的值拷贝到原数组中
    	  for (int i = left; i <= right; i++)
    	{
    		array[i] = temp[i];
    	}
       }