重拾我的算法思维之--归并排序

归并排序

算法平均时间复杂度：O(nlog2n)

算法空间复杂度：O(n)  (用于存储有序子序列合并后有序序列)

原理：所谓归并排序是指将两个或两个以上有序的数列（或有序表），合并成一个仍然有序的数列（或有序表）。这句话讲的非常明白，有序，前提就是有序。

步骤分析：

1、划分子集

2、合并子集

先说一下归并算法合并的思路，也是核心：（升序）假设有一数组，分成两个子数组，子数组每次分别各取出一个数字进行比较（子数组取的元素索引都从小到大），将小的放入准备好的临时数组，当两个字数组中有一个数组的所有元素都比较过了，那就将另一数组剩余的元素依次放入临时数组中。那么这一趟结果就是有序排列好了。前提是两个子数组都是有序的。举个栗子：

1）假设有数组 [12,5,8,14,7,6]（子数组无序）

先划分为两个子数组[12,5,8],[14,7,6],并有一个临时数组temp[]

12 与 14 比较， 12放入temp[]中          temp[12]

5　与 14 比较， 5  放入temp[]中          temp[12,5]

8　与 14 比较， 8  放入temp[]中          temp[12,5,8]

子数组中[12,5,8]所有元素都比较完，剩余的另外子数组元素依次放入temp[]          temp[12,5,8,14,7,6]

可见子数组无序得到的结果并不是排好序的。

2）假设有数组 [5,8,12,6,7,14]（子数组有序）

先划分为两个子数组[5,8,12],[6,7,14],并有一个临时数组temp[]

5   与 6   比较， 5  放入temp[]中          temp[5]

8　与 6   比较， 6  放入temp[]中          temp[5,6]

8　与 7   比较， 7  放入temp[]中          temp[5,6,7]

8　与 14 比较， 8  放入temp[]中          temp[5,6,7,8]

12 与 14 比较， 12放入temp[]中          temp[5,6,7,8,12]

子数组中[5,8,12]所有元素都比较完，剩余的另外子数组元素依次放入temp[]          temp[5,6,7,8,12,14]

可见子数组有序得到的结果是排序好的。

怎样才能保证两边子数组是有序？当一个数组只有一个元素的时候，即算为有序的，然后用上面的第二个例子的思路归并，即为排序好的。

也就是说我们要先将要比较的数组arr[]，拆分为和数组arr.length同样多的子数组，然后两两归并，如图1所示：

　　　　　　　　　　　　　　　　　　　　　　      图1 归并排序

代码：附注释

1 public static void Merge(int[] arr,int low,int mid,int high){
 2         int[] temp = new int[high - low + 1];//
 3         int i = low;//左边部分起始索引
 4         int j = mid + 1;//右边部分起始索引
 5         int index = 0;
 6         //比较将较小的放入temp中
 7         while(i <= mid && j <= high){
 8             if(arr[i]<arr[j]){
 9                 temp[index++] = arr[i++];
10             }else if(arr[i]>arr[j]){
11                 temp[index++] = arr[j++];
12             }
13         }
14         //把左边剩余的全放入临时数组中
15         while(i <= mid){
16             temp[index++] = arr[i++];
17         }
18         //把右边剩余的全放入临时数组中
19         while(j <= high){
20             temp[index++] = arr[j++];
21         }
22         //最后将临时数组覆盖原数组
23         for (int x = 0; x < temp.length; x++) {
24             arr[x+low] = temp[x];
25         }
26     }
27     public static void MergeSort(int[] arr,int low,int high){
28         if(low < high){
29             int mid = (low+high)/2;
30             //将其分为两部分
31             MergeSort(arr,low,mid);//左边递归（再分两部分）
32             MergeSort(arr,mid+1,high);//右边递归（再分两部分）
33             //归并
34             Merge(arr,low,mid,high);
35         }
36     }