算法简析之归并排序

简析

---

概念

归并排序 归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：

原理

1. 拆分：假设有N个元素的列表，首先把它拆分成2个或2个以上的元素组成的新的列表，分别对对它们进行排序。

2. 归并：把所有的排好序的子类表两两归并，如此重复，直到归并成一个含N个元素的有序列表为止

---

范例（java）

概念代码

public static int[] sort(int[] nums, int low, int high) {  
    int mid = (low + high) / 2;  
    if (low < high) {  
        // 左边  
        sort(nums, low, mid);  
        // 右边  
        sort(nums, mid + 1, high);  
        // 左右归并  
        merge(nums, low, mid, high);  
    }  
    return nums;  
}  

public static void merge(int[] nums, int low, int mid, int high) {  
    int[] temp = new int[high - low + 1];  
    int i = low;// 左指针  
    int j = mid + 1;// 右指针  
    int k = 0;  

    // 把较小的数先移到新数组中  
    while (i <= mid && j <= high) {  
        if (nums[i] < nums[j]) {  
            temp[k++] = nums[i++];  
        } else {  
            temp[k++] = nums[j++];  
        }  
    }  

    // 把左边剩余的数移入数组  
    while (i <= mid) {  
        temp[k++] = nums[i++];  
    }  

    // 把右边边剩余的数移入数组  
    while (j <= high) {  
        temp[k++] = nums[j++];  
    }  

    // 把新数组中的数覆盖nums数组  
    for (int k2 = 0; k2 < temp.length; k2++) {  
        nums[k2 + low] = temp[k2];  
    }  
}  


// 归并排序的实现  
public static void main(String[] args) {  

    int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };  

    MergeSort.sort(nums, 0, nums.length-1);  
    System.out.println(Arrays.toString(nums));  
}  

---