归并排序(merge sort)

• 于1945年，由冯诺伊曼提出首次提出

执行流程

• 不断地将数组平均分割成两个子序列, 直到不能再分割为止(只有一个元素)
• 不断地将2个子序列合并，直到合并成一个有序序列

divide实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

protected void sort() {
        leftArray = new Integer[array.length >> 1];
        sort(0, array.length);
    }

    /*
    * 对数组进行分割
    * 左闭右开 [begain, end)
    * */
    private void sort(int begain, int end) {
        if (end - begain < 2) return;

        int mid = (begain + end) >> 1;
        sort(begain, mid);
        sort(mid, end);

        merge(begain, mid, end);
    }   

merge实现

• merge需要注意
• 合并两个有序数组，如果可以利用额外的内存空间，会非常简单。
  • 初始化一个两个数组大小的结果数组，两个指针分别指向两个数组的开头
  • 依次比较两个元素，较小者加入结果数组，且指针后移一位
  • 直到两个数组中元素都加入新数组位置
• 但是, 这里的归并排序，要merge的两个子数组存在同一个数组中，如图

• 所以我们的做法是， 先备份左边数组， 再右边数组和左边数组比较，依次加入当前数组

• 代码如下 :

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  private void merge(int begain, int mid, int end){ int li = 0, le = mid - begain; // 左边数组 起始/结束位置 int ri = mid, re = end; // 右边数组 起始/结束位置 int ai = begain; // array的索引 // 拷贝左边数组到leftArray for (int i = li; i < le; i++) { leftArray[i] = array[begain + i]; } while (li < le){ if (ri < re && cmpElement(array[ri], leftArray[li]) < 0){ array[ai ++] = array[ri ++]; // 拷贝右边数组到array }else { array[ai ++] = leftArray[li ++];// 拷贝左边数组到array } }// cmp 位置改为 <= 会失去平衡性 }

复杂度

归并排序时间复杂度 : O(N * log N)

空间复杂度 : O(N / 2) + O(log N) = O(N)。 其中 N / 2是存放左边数组的空间, log N是递归调用的栈空间

稳定性

属于稳定排序 (相同的元素，不会交换位置)