排序算法(二)之归并排序——java实现
排序算法(2)之归并排序——java实现
本文要讲的归并排序是继快速排序之后的又一常用排序算法,相似的是归并排序也是一种分治算法,因此,与快排一样,对于规模较大的问题,非常适用。
与快排相比,归并排序是稳定的,最重要的是其优点在于,其最差时间复杂度也是O(NlogN)。
归并排序是将两个(两个以上按两两处理)有序表合并成一个新的有序表。这里要强调下,待归并的两个数列必须是有序的。具体原因见算法。
算法思想:
1.首先将原数列,分解成左右两部分
2.分别对左右两部分,进行分解处理
3.再讲子部分合并成为一个有序数列
代码框架如下:
static void merge(int[] a,int begin ,int end){ if(begin == end){//只有一个元素的时候,认为已经排好序,跳出递归 return; } if(begin<end){ int mid = (begin + end)/2; //分解左半部分和右半部分 1. merge(a,begin,mid); 2. merge(a,mid+1,end); //将分解处理之后的部分进行合并 3. mergeAndSort(a,begin,mid,end); } }
如果对递归不是特别熟悉的话,可以结合这个例子,手动的画出递归栈
↓ begin ↓ mid ↓ end
5 | 4 | 2 | 7 | 9 | 1 |
接下来的重点是merge:
比如说
a的左半部分是:1 3 8,赋值给left[]
a的右半部分是:2 4 5,赋值给right[]
为了方便对比,我们将left和right的最后加一个哨兵元素MAX,这样就不比对最后一个元素做特殊处理了。
static void mergeAndSort(int[] a,int begin,int mid,int end){ int[] left = new int[mid - begin + 2]; //多留出一个哨兵位 int[] right = new int[end - mid + 1]; for(int i = begin ; i <= end; i++){ if(i <= mid){ left[i - begin] = a[i]; }else{ right[i - mid - 1] = a[i]; } } left[mid - begin + 1] = Integer.MAX_VALUE; right[end - mid] = Integer.MAX_VALUE; int i = 0; int j = 0; int index = begin; while(index <= end){//按照顺序,将左右两部分归并 a[index++] = left[i] < right[j] ? left[i++] : right[j++]; } }
附录:
全部源代码为:
package sort; import java.util.Arrays; public class Merge { static void merge(int[] a,int begin ,int end){ if(begin == end){ return; } if(begin<end){ int mid = (begin + end)/2; merge(a,begin,mid); merge(a,mid+1,end); mergeAndSort(a,begin,mid,end); } } static void mergeAndSort(int[] a,int begin,int mid,int end){ int[] left = new int[mid - begin + 2]; int[] right = new int[end - mid + 1]; for(int i = begin ; i <= end; i++){ if(i <= mid){ left[i - begin] = a[i]; }else{ right[i - mid - 1] = a[i]; } } left[mid - begin + 1] = Integer.MAX_VALUE; right[end - mid] = Integer.MAX_VALUE; int i = 0; int j = 0; int index = begin; while(index <= end){ a[index++] = left[i] < right[j] ? left[i++] : right[j++]; } } public static void main(String[] args) { int[] a = {1,9,5,7,4,6,3,8,11,24}; merge(a,0,a.length - 1); System.out.println(Arrays.toString(a)); //打印结果为:[1, 3, 4, 5, 6, 7, 8, 9, 11, 24] } }