【算法】归并排序

算法系列博客

【算法】刷题范围建议和代码规范

【算法】复杂度理论 ( 时间复杂度 )

【字符串】最长回文子串 ( 蛮力算法 )

【字符串】最长回文子串 ( 中心线枚举算法 )

【字符串】最长回文子串 ( 动态规划算法 ) ★

【字符串】字符串查找 ( 蛮力算法 )

【字符串】字符串查找 ( Rabin-Karp 算法 )

【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串 )

【算法】双指针算法 ( 有效回文串 II )

【算法】哈希表 ( 两数之和 )

【算法】快速排序

【算法】归并排序

文章目录

算法系列博客
一、归并排序

一、归并排序

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

归并排序原理 :

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

先局部有序 , 后整体有序 ;

归并排序与快速排序比较 , 其比快排多花费

O(n)

的空间 , 其合并两个数组时 , 不能在原数组中进行 ;

快速排序 , 始终都在原数组中进行 , 只涉及到交换数组中的元素 ;

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

算法要点 :

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

代码示例 :

代码语言：javascript复制

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];
        }
    }
}

排序数组算法指针字符串

0 人点赞

【算法】归并排序

算法 系列博客

文章目录

一、归并排序

算法系列博客