19、数据结构和算法 - 实战:归并排序算法

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数开始,谁小就先取谁。然后再进行比较,如果有数列比较完了,那直接将另一个数列的数据依次取出即可。可以看出合并有序数列的效率是比较高的,可以达到O(n)。

 

1.2 算法基本思想

归并排序的核心思想其实很简单,如果要排序一个数组,我们先把数组从中间分成前后两部分,然后分别对前后两部分进行排序,再将排好序的两部分数据合并在一起就可以了。归并排序使用的是分治思想,分治也即是分而治之,将一个大问题分解为小的子问题来解决。分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想,递归是一种编程技巧。

 

1.3 归并排序复杂度分析

  • 归并排序是一个稳定的排序算法,在进行子数组合并的时候,我们可以设置当元素大小相等时,先将前半部分的数据放入临时数组,这样就可以保证相等元素在排序后依然保持原来的顺序。
  • 不仅递归求解的问题可以写成递推公式,递归代码的时间复杂度也可以写成递归公式。
  • 如果我们对n个元素进行归并排序所需要的时间是T(n),那分解成两个子数组排序的时间都是 ,而合并两个子数组的时间复杂度为 。所以,归并排序的时间复杂度计算公式为:O(n)

1.4 归并排序代码实现

package com.yuanxw.datastructure.chapter19;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {
   
     
    public static void main(String[] args) {
   
     
        // int[] array = new int[]{10, -7, 8, -2, 5, -4};
        // 定义需要排序的数组
        int[] array = new int[]{
   
     8, 4, 5, 7, 1, 3, 6, 2};
        // 临时数组
        int[] temp = new int[array.length];
        System.out.println("【归并排序】前的结果:" + Arrays.toString(array));
        // 拆分
        mergeSort(array, 0, array.length - 1, temp);
        System.out.println("【归并排序】后的结果:" + Arrays.toString(array));
    }

    /**
     * 拆分数组
     *
     * @param array 原始数组
     * @param left  数组左侧下标
     * @param right 数组右侧下标
     * @param temp  临时数组(中间数组)
     */
    public static void mergeSort(int[] array, int left, int right, int[] temp) {
   
     
        // 如果【left < right】成立,说明还没有拆分到最小单元
        if (left < right) {
   
     
            // 得到中间索引
            int middle = (left + right) / 2;
            // 递归-拆份左边的部分
            mergeSort(array, left, middle, temp);
            // 递归-拆份右边的部分
            mergeSort(array, middle + 1, right, temp);
            // 合并 数组
            merge(array, left, middle, right, temp);
        }
    }

    /**
     * 合并数组
     *
     * @param array
     * @param left
     * @param middle
     * @param right
     * @param temp
     */
    public static void merge(int[] array, int left, int middle, int right, int[] temp) {
   
     
        // 左边最左侧下标
        int leftIndex = left;
        // 右边最左侧下标
        int middleIndex = middle + 1;
        // 临时数组
        int tempIndex = 0;
        while (leftIndex <= middle && middleIndex <= right) {
   
     
            // 比较左右两边大小,分别放到temp临时数组中
            if (array[leftIndex] <= array[middleIndex]) {
   
     
                temp[tempIndex] = array[leftIndex];
                tempIndex++;
                leftIndex++;
            } else {
   
     
                temp[tempIndex] = array[middleIndex];
                tempIndex++;
                middleIndex++;
            }
        }

        // 如果比较完毕, 第左边还有数剩下, 则全部填入temp
        while (leftIndex <= middle) {
   
     
            temp[tempIndex] = array[leftIndex];
            tempIndex++;
            leftIndex++;
        }

        // 如果比较完毕, 第右边还有数剩下, 则全部填入temp
        while (middleIndex <= right) {
   
     
            temp[tempIndex] = array[middleIndex];
            tempIndex++;
            middleIndex++;
        }

        // 将temp数组中的数据全部拷贝到array数组中
        for (int i = 0; i < tempIndex; i++) {
   
     
            array[left + i] = temp[i];
        }
    }
}

执行结果:

【归并排序】前的结果:[8, 4, 5, 7, 1, 3, 6, 2]
【归并排序】后的结果:[1, 2, 3, 4, 5, 6, 7, 8]