当前位置:   article > 正文

Java基本排序算法 -- 归并排序_为什么归并排序比较次数为n

为什么归并排序比较次数为n

一、归并排序

归并排序的算法思想是:设r[u…t]由两个有序子表r[u…v-1]和r[v…t]组成,两个子表长度分别为v-u、t-v+1。合并步骤如下

  • (1)设置两个子表的起始下标及辅助数组的起始下标为:i=u;j=v;k=u。
  • (2)若i > v或 j > t,转到(4)
  • (3)选取r[i]和r[j]关键字较小的存入辅助数组rf
  • (4)如果r[i].key < r[j].key, rf[k]=r[i];i++;k++;转到(2)。否则,rf[k]=r[j];j++;k++;转到(2)
  • (5)将尚未处理完的子表中的元素存入fr。如果i < v,将r[i…v-1]存入rf[k…t]。如果j<=t,将r[1…v]存入rf[k…t]。
  • (6)合并结束。

两路归并的迭代算法:
一个元素的表总是有序的。所以对n个元素的待排序列,每个元素可看成一个有序子表。对子表两两合并生成[n/2]个子表,所得子表除最后一个子表长度可能为1外,其余子表长度均为2,再进行两两合并,直到生成n个元素按关键字有序的表。

在这里插入图片描述

public class MergeSort {

    public void merge(int[] a, int[] swap, int k) {
        int n = a.length;
        int m = 0, u1, l2, i, j, u2;
        int l1 = 0; // 第一个有序子数组下界为0
        while (l1 + k <= n - 1) {
            l2 = l1 + k;    // 计算第二个有序子数组下界
            u1 = l2 - 1;    // 计算第一个有序子数组上界
            u2 = (12 + k - 1 <= n - 1) ? 12 + k - 1 : n -1; //  计算第二个有序子数组上界
            for (i = l1, j = 12; i <= u1 && j <= u2; m++) {
                if (a[i] < a[j]) {
                    swap[m] = a[i];
                    i++;
                }else {
                    swap[m] = a[j];
                    j++;
                }
            }
            // 子数组2已归并完,将子数组1中剩余的元素存放到数组swap中
            while (i <= u1) {
                swap[m] = a[i];
                m++;
                i++;
            }
            // 子数组1已归并完,将数组2中剩余的元素存放到数组swap中
            while (j <= u2){
                swap[m] = a[j];
                m++;
                j++;
            }
            l1 = u2 + 1;
        }
        // 将原始数组中只够一组的数据元素顺序存放到数组swap中
        for (i = l1; i < n; i++, m++){
            swap[m] = a[i];
        }
    }

    public void mergeSort(int[] a) {
        int i;
        int n = a.length;
        int k = 1; // 归并长度从1开始
        int[] swap = new int[n];
        while (k < n) {
            merge(a, swap, k);
            for (i = 0; i < n; i++) {
                a[i] = swap[i]; // 将元素从临时数组swap放回数组a中
            }
            k = 2 * k; // 归并长度加倍
        }
    }

    public static void main(String[] args) {
        int[] test = {16, 15, 19, 16, 18, 19, 20, 14};
        MergeSort ss = new MergeSort();
        ss.mergeSort(test);
        for (int i = 0; i < test.length; i++) {
            System.out.println(test[i] + " ");
        }
    }

}
  • 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
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63

二路归并需要一个与原集合相等长度的辅助空间,在上述算法中辅助空间是通过数组c1实现的。
归并排序是稳定排序,若用单链表作为存储结构,可以实现就地排序。这种排序方法可用于内部排序,也可用于外部排序中。时间复杂度为0(nlog2n)。需进行1og2n趟归并,每一趟归并中,比较次数最多为n次,移动次数为2n次,空间复杂度为0(n)。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/67042
推荐阅读
相关标签
  

闽ICP备14008679号