算法 系列博客

【算法】刷题范围建议 和 代码规范
【算法】复杂度理论 ( 时间复杂度 )

【字符串】最长回文子串 ( 蛮力算法 )
【字符串】最长回文子串 ( 中心线枚举算法 )
【字符串】最长回文子串 ( 动态规划算法 ) ★
【字符串】字符串查找 ( 蛮力算法 )
【字符串】字符串查找 ( Rabin-Karp 算法 )

【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串 )
【算法】双指针算法 ( 有效回文串 II )
【算法】哈希表 ( 两数之和 )

【算法】快速排序
【算法】归并排序

一、归并排序

归并排序 : https://www.lintcode.com/problem/463

归并排序原理 :

归并排序 先分割为两部分 , 然后两边分别排序 , 再进行合并 ;
先局部有序 , 后整体有序 ;

归并排序 与 快速排序 比较 , 其比 快排 多花费 $O(n)$ 的空间 , 其合并两个数组时 , 不能在原数组中进行 ;
快速排序 , 始终都在原数组中进行 , 只涉及到交换数组中的元素 ;

正式由于该额外数组的存在 , 因此归并排序 , 并不是排序的最优算法 ;

算法要点 :

合并数组中 , 创建数组的时机 , 不要放在递归中 , 递归要调用很多次 , 频繁创建销毁数组 , 很耗费时间和空间 ;

代码示例 :

class Solution {

    /**
     * 归并排序
     * @param A
     */
    public void sortIntegers(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }

        // 用于合并数组的额外空间
        int mergeArray[] = new int[A.length];

        // 递归调用排序算法
        mergeSort(A, 0, A.length - 1, mergeArray);
    }

    // 将 array 数组中 start 到 end 之间的元素进行排序
    private void mergeSort(int[] array, int start, int end, int[] mergeArray) {
        if (start >= end) {
            // start 如果等于 end, 说明就一个元素, 不用排序
            // start 正常情况下不会大于 end
            return;
        }

        // 先在中间切一刀, 左侧右侧进行分别排序
        // 左侧排序
        mergeSort(array, start, (start + end) / 2, mergeArray);
        // 右侧排序
        mergeSort(array, (start + end) / 2 + 1, end, mergeArray);

        // 进行归并操作, 将已经排好序的两侧的数组进行合并
        merge(array, start, end, mergeArray);
    }

    // 合并两个已经排好序的数组
    private void merge(int[] array, int start, int end, int[] mergeArray) {
        // 左右两个数组的遍历索引, 初值值为左右两侧的开始索引
        int leftIndex = start;
        int rightIndex = (start + end) / 2 + 1;
        // 记录 mergeArray 的赋值索引
        int mergeIndex = leftIndex;

        while (leftIndex <= (start + end) / 2 && rightIndex <= end) {
            if (array[leftIndex] < array[rightIndex]){
                // 先赋值, 然后索引自增
                mergeArray[mergeIndex++] = array[leftIndex++];
            } else {
                mergeArray[mergeIndex++] = array[rightIndex++];
            }
        }

        // 上述赋值完毕后, 可能有一侧还有若干元素没有赋值完毕
        // 检查左侧是否赋值完毕, 如果没有赋值完毕, 则继续遍历, 如果赋值完毕, 则不会进入循环
        while (leftIndex <= (start + end) / 2) {
            mergeArray[mergeIndex++] = array[leftIndex++];
        }
        // 检查右侧是否赋值完毕, 如果没有赋值完毕, 则继续遍历, 如果赋值完毕, 则不会进入循环
        while (rightIndex <= end) {
            mergeArray[mergeIndex++] = array[rightIndex++];
        }

        // 上述操作将排序号的元素都放在 mergeArray 数组中, 在将其设置到 array 数组中
        for (int i = start; i <= end; i++) {
            array[i] = mergeArray[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
  
64
  
65
  
66
  
67
  
68
  
69
 

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/119142287