归并排序算法

​

文章目录

1. 算法思想
2. 算法图解
3. 代码实现
4. 算法特点

1. 算法思想

 主要思想：

1. 算法图解

int[] array = {30,60,40,10,80,20,50,70};
以数组array为例降序分析

先将数组分为左右子表 

 将左右子表继续拆分，知道只有两个元素时，开始比较并排序

 接下来将有序的子表进行合并，产生一个新的数组用来存放排序结果

1. 代码实现

代码：

import java.util.Arrays;

public class MergeSort {

public int[] sortArray(int[] nums){
    if(nums.length<2){
        return nums; 
    }
    //切分数组，然后递归排序 ，并用merge合并
    int mid = nums.length/2;
    int[] left = Arrays.copyOfRange(nums,0,mid);
    int[] right = Arrays.copyOfRange(nums,mid,nums.length);
    return merge(sortArray(left),sortArray(right));
}

public static int[] merge(int[] left,int[] right){
    int[] result = new int[left.length+ right.length];
    for (int index = 0,i=0,j=0;index < result.length;index++){
        if(i>= left.length){
            result[index] = right[j++];
        } else if (j >= right.length){
            result[index] = left[i++];
        } else if (left[i]>right[j]) {
            result[index] = right[j++];
        } else {
            result[index] = left[i++];
        }
    }
    System.out.println("左子数组：");
    PrintArray.print(left);
    System.out.println("右子数组：");
    PrintArray.print(right);
    System.out.println("合并后的数组");
    PrintArray.print(result);
    System.out.println("-----------");
    return result;
}

public static void main(String[] args) {
    int[] nums = {32,12,1,12,23,45,11,100,55,76,34};

    int[] array = new MergeSort().sortArray(nums);
}

}
class PrintArray{

public static void print(int[] nums){
    System.out.println(Arrays.toString(nums));
}

}
结果：

1. 算法特点

时间复杂度：
每次将序列折半分组，共需要logn轮，因此归并排序算法的时间复杂度是O(nlogn)

空间复杂度：
排序过程中需要额外的一个序列去存储排序后的结果，所占空间是n，因此空间复杂度为O(n)

稳定性：
在排序过程中，相同元素的前后顺序并没有改变，是一种稳定排序算法

​