排序算法2

2、归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

原理：通过对若干个有序节点的归并实现排序。

方法：1、先将原序列拆分成若干子序列 2、将子序列重组成两个有序列 3、合并两个有序列

例 待排序序列为{ 28, 7, 27, 3, 1, 6, 9, 0, 5, 4 }

（1）拆分序列后{28，7，27，3，1}{6，9，0，5，4}——>{28,7,27}{3,1}/{6,9,0}{5,4}——>{28,7}{27}/{3,1}/{6,9}{0}/{5,4}——>{28}{7}{27}{3}{1}/{6}{9}{0}{5}{4}

（2）合并序列为有序列{7,28}{3,27}{1}/{6,9}{0,5}{4}——>{3,7,27,28}{1}/{0,5,6,9}{4}——>{1,3,7,27,28}/{0,4,5,6,9}

（3）合并有序列{0, 1, 3, 4, 5, 6, 7, 9, 27, 28}

代码实现(JAVA)

import java.util.Arrays;public class mergesort {	    /** 	     * 归并排序 	     * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列 	     * 时间复杂度为O(nlogn) 	     * 稳定排序方式 	     */  	//start起始下标  end最后一位下标	    public static int[] sort(int[] nums, int start, int end) {  	        int mid = (start + end) / 2;  	        if (start < end) {  	            // 左边  	            sort(nums, start, mid);  	            // 右边  	            sort(nums, mid + 1, end); 	            // 左右归并  	            merge(nums, start, mid, end);  	        }  	        return nums;  	    }  	  	    public static void merge(int[] nums, int start, int mid, int end) {  	        int[] temp = new int[end - start + 1];  	        int i = start;//左序列起始  	        int j = mid + 1;//右序列起始	        int k = 0;  	  	        // 比较两个有序列，将最小的放入临时序列中  	        while (i <= mid && j <= end) {  	            if (nums[i] <= nums[j]) {  	                temp[k++] = nums[i++];  	            } else {  	                temp[k++] = nums[j++];  	            }  	        }  	  	        // 把左边剩余的数移入临时序列 	        while (i <= mid) {  	            temp[k++] = nums[i++];  	        }  	  	        // 把右边边剩余的数移入临时序列  	        while (j <= end) {  	            temp[k++] = nums[j++];  	        }  	  	        // 把临时序列中的数覆盖nums数组  	        for (int k2 = 0; k2 < temp.length; k2++) {  	            nums[k2 + start] = temp[k2];  	        }  	    }  	  	      	    // 归并排序的实现  	    public static void main(String[] args) {  	  	        int[] nums = { 28, 7, 27, 3, 1, 6, 9, 0, 5, 4 };  	        mergesort.sort(nums, 0, nums.length-1);  	        System.out.println("sort:"+Arrays.toString(nums));  	    }  	}