算法入门学习----2.1归并排序

痛定思痛。 2022-06-01 11:56 75阅读 0赞

# 一、归并排序的原理 #

## 对数组采用了“分治思想” ##

![SouthEast][]

### 1.1 分：先通过二分法将数组分为一个一个单独的数。 ###

**分的算法实现（递归）：**

**传入参数为**：

数组(arr)、指向数组最左边的指针（left）、指向数组最右边的指针（right）、

空数组（temp）（长度与原数组一样，用在这里是方便将第一步也归入递归步骤）

**实现内容**：

当传入的right>left,说明数组可以再细分，于是取两者的平均数（mid）。

这时将数组分为两组：一组是left到mid,另一组是mid+1到right，这两组依次调用递归方法，直到right<=left。

### 1.2 治(思路和分的思路相反)： ###

第一次，每两个数分为一组，并排序好。

第二次，将第一步中的每两组和并成为一组，并排序好。

第三次，将第二步中的每两组和并成为一组，并排序好。

...........................

**治的算法实现：**

**传入参数**：

原数组（arr）、要合并的两个数组的左指针（left）、要合并的两个数组的右指针（right）、

要合并的两个数组的中指针（mid）、空数组(temp)。

注：上述的两个数组，在分的思路中，**本来是属于同一个数组，**后面才分开：

所以左指针为第一个数组的最左，mid指针为第一个数组的最右；

右指针为第二个数组的最右，mid+1指针为第二个数组的最左。

**实现内容**：

先拿第一个数组的第一个数（left）和第二个数组的第一个数（mid+1）比较

如果第一个数组的数大于（小于）第二个数组的数，那么将第二（一）个数组的数放入新数组（temp）的第一位。

接着第二（一）个数组的指针右移一位，再次进行上述比较。

当出现某一个数组比较完的时候，将另一个数组剩下的数全部加到temp中。

最后将比较好的数组传递给原来的数组（arr）![SouthEast 1][]![SouthEast 2][]

# 二、归并排序的空间复杂度和时间复杂度 #

本人不才：直接借鉴一下其他人的解法 ：http://blog.csdn.net/yuzhihui\_no1/article/details/44223225

# 三、归并排序的代码实现Java #

public class GuiBing {
    	public static void main(String[] args){  
            int[] arr=new int[]{23,5,15,37,59,45,2,156,32,48}; 
            int[] temp = new int[arr.length];//注意：Int[] temp =arr  这样的话，是将temp指向了arr所指向的数组，当temp改变的时候，arr也会改变
            sort(arr,0,arr.length-1,temp); 
            show(arr);
        }  
        public static void show(int[] arr){  //输出函数  
            for(int a: arr){  
                System.out.println(a);  
            }  
        }  
        public static void sort(int[] arr,int left,int right,int[] temp){
        	if(left<right){
        		int mid=(left+right)/2;
        		sort(arr,left,mid,temp);               //分解
        		sort(arr,mid+1,right,temp);            //分解
        		jiehe(arr,left,mid,right,temp);	       //合并
        	  }
        	}
       public static void jiehe(int[] arr,int left,int mid,int right,int[] temp){    //mid作为两边数组的临界标签
        		int right_left = mid+1;                    //存储右数组的最左边指针，用于移动
        		int left_left = left;
        		int i=0;				//存储数组的第一位
        		while(left_left<=mid && right_left<=right){   //两边数组同时遍历，依次将小的数存入temp数组
        			if(arr[left_left]<arr[right_left])      
        				temp[i++]=arr[left_left++];   			
        			else if(arr[left_left]>arr[right_left])
        				temp[i++]=arr[right_left++];  			
        		}
        		while(right_left<=right){
            			temp[i++]=arr[right_left++];
            	}	
        		while(left_left <=mid){
        			temp[i++]=arr[left_left++]; 
        		}    	
        		i=0;
        		 while(left <= right){                               //遍历，将temp改动的数组复制到arr中
        	            arr[left++] = temp[i++];
        	     }                               
        	}
    }

# 四、参考借鉴文章 #

https://www.cnblogs.com/chengxiao/p/6194356.html

http://blog.csdn.net/yuzhihui\_no1/article/details/44223225

[SouthEast]: /images/20220601/46235d616e0844769d29a2695d50d857.png
[SouthEast 1]: https://img-blog.csdn.net/20180129104145502?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQva3VuZmQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20220601/7cf66faff4c14fc2811affe0d0dd3fe0.png