归并排序

x33g5p2x  于2021-12-06 转载在 其他  
字(2.0k)|赞(0)|评价(0)|浏览(227)

动画排序过程

执行流程

归并排序采用了 分治(Divide and Conquer)和 递归(Recursion)的思想(快速排序也是一样,这里你可以和快速排序比较一下他们的区别)

流程:

  1. 划分:将待排序列二分,一直向下划分,直到只有一个元素为止(只有一个元素相当于已排序)
  2. 合并:将已排序的两个子序列合并为一个新的有序序列(主要逻辑)

实现代码

归并排序实现代码:

/** * 归并排序 * @param arr:待排序的数组 * @param tempArr:辅助的临时数组 * @param left:最左边下标 * @param right:最右边下标 */
public static void sort(int[] arr, int[] tempArr, int left, int right) {
    // 如果只有一个元素,那么就不需要再继续划分了 (只有一个元素本身就是有序的,只需要被合并即可)
    // 如果 left<right则表示至少有两个元素,则需要继续划分 递归调用sort
    if (left < right) {
        int mid = (left+right)/2;   // 找到中间点
        // 递归划分左半区域
        sort(arr, tempArr, left, mid);
        // 递归划分右半区域
        sort(arr, tempArr, mid+1, right);
        // 将划分后的排序合并(排序的主要逻辑在这个方法里)
        merge(arr, tempArr, left, mid, right);
    }
}

/** * 将划分后的排序合并(排序的主要逻辑在这个方法里) * @param arr * @param tempArr * @param left * @param mid * @param right */
public static void merge(int[] arr, int[] tempArr, int left, int mid, int right) {
    // 标记左半区第一个未合并的元素下标
    int l_pos = left;
    // 标记右半区第一个未合并的元素下标
    int r_pos = mid+1;
    // 临时数组元素的下标
    int pos = left;

    // 合并(左半区、有半区都存在未合并的元素)
    while (l_pos<=mid && r_pos<=right) {
        if (arr[l_pos] < arr[r_pos])    // 左半区第一个未合并的元素 小于 右半区第一个未合并的元素
            tempArr[pos++] = arr[l_pos++]; // 将更小的那个数放到临时数组中 且pos、l_pos下标后移
        else
            tempArr[pos++] = arr[r_pos++];   // 同上
    }
    // 合并左半区剩余的元素(如果右半区已经合并完)
    while (l_pos <= mid)
        tempArr[pos++] = arr[l_pos++];

    // 合并右半区剩余的元素(如果左半区已经合并完)
    while (r_pos <= right)
        tempArr[pos++] = arr[r_pos++];

    // 把临时数组中合并后的元素复制回原来的数组
    while (left <= right) {
        arr[left] = tempArr[left];
        left++;
    }
}

测试代码:

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("请输入你想生成随机数的个数");
    int num = sc.nextInt();
    int[] arr = new int[num];
    int[] tempArr = new int[num];
    for (int i=0; i<num; i++) arr[i] = (int)(Math.random()*100);
    System.out.println("排序前的数据:");
    for (int i=0; i<arr.length; i++)
        System.out.print(arr[i]+" ");

    long begin = System.currentTimeMillis();
    sort(arr, tempArr, 0, arr.length-1);
    long end = System.currentTimeMillis();

    System.out.println();
    System.out.println("总耗时为:"+(end-begin));
    System.out.println("排序后的数据:");
    for (int i=0; i<arr.length; i++)
        System.out.print(arr[i]+" ");

    System.out.println();

}

总结

空间复杂度:O(n)

  • 因为创建一个相同大小的临时数组嘛

时间复杂度:O(NlogN)

  1. 每一层归并的时间复杂度为O(N)
  2. 归并层数最大为O(logN+1)

相关文章

微信公众号

最新文章

更多