归并排序

发表于 | 分类于

归并排序的基本思想：归并排序其实有两个过程，即分和治的过程。先“分割”再“合并”，我们把一个未排序的序列分成两部分，再分为4部分，依次分割下去，直到分成一个一个数据，我们可以认为单个的数据是已经排好序的。第二步，把这些排好序的数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。

算法描述

  • 分割过程：把长度为N的输入序列分成两个长度为N/2的子序列，然后再分割，直到每个序列的长度为1。
  • 合并的过程：merge过程就是把每个子序列两两合并，直到最终得到一个排好序的序列。
  • 将排好序的数组再复制回原数组。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class MergeSort{
    public static int[] sort(int[] a,int low,int high){
        int mid = (low+high)/2;
        if(low<high){
            sort(a,low,mid);
            sort(a,mid+1,high);
            merge(a,low,mid,high);
        }
        return a;
    }
    public static void merge(int[] a,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(a[i]<a[j]){
                temp[k++]=a[i++];
            }else{
                temp[k++]=a[j++];
            }
        }
        //把左边剩余的数移入数组
        while(i<=mid){
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=high){
            temp[k++] = a[j++];
        }
        //把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            a[x+low] = temp[x];
        }
    }
    public static void main(String[] args) {
        int[] array = new int[]{6,3,8,2,9,1};
        System.out.println(Arrays.toString(sort(array,0,5)));
    }
}

算法分析

  • 时间效率：O(nlogn)
  • 空间效率：O(n)
  • 稳定性： 稳定