排序算法——归并排序

一、算法思想

1. 算法描述

1. 把一个比较大的问题分割成两个比较小的问题求解
2. 重复步骤1直至问题已可直接求解，如要排序的元素只有一个，即已是排序结果
3. 把两个已排好序的小问题的解合并成一个较大的问题解
4. 重复步骤3直至达到原问题的解

2. 伪代码

MERGE-SORT(A,low,high){
    if(low < high){
        middle = (low + high)/2
        MERGE-SORT(A,low,middle)
        MERGE-SORT(A,middle+1,high)
        MERGE(A,low,middle,high)
    }
}

MERGE(A,low,middle,high){
    lowSize = middle - low +1
    highSize = high -middle
    
    for(i = 1 to lowSize){
        lowArray[i] = A[low + i]
    }
    for(i = 1 to highSize){
        highArray[j] = A[middle + i + 1]
    }
    
    i = j = 1
    k = low
    while(i < lowSize and j < highSize){
        if(lowArray[i]<=highArray[j]){
            A[k++] = lowArray[i++]
        }else{
            A[k++] = highArray[j++]
        }
    }
    
    while(i < lowSize){
       A[k++] = lowArray[i++] 
    }
    
    while(j < highSize){
       A[k++] = highArray[j++] 
    }
    
}

3. 算法流程

归并排序流程

二、算法实现

1. Kotlin

/**
 * 归并排序
 * 1. 把一个比较大的问题分割成两个比较小的问题求解
 * 2. 重复步骤1直至问题已可直接求解，如要排序的元素只有一个，即已是排序结果
 * 3. 把两个已排好序的小问题的解合并成一个较大的问题解
 * 4. 重复步骤3直至达到原问题的解
 * @author likly
 * @version 1.0
 */

/**
 * 归并排序--分治
 * @param array 要排序的数组
 * @param low 数组的下界
 * @param high 数组的上界
 * @param debug 是否输出调试信息
 */
fun mergeSort(array: Array<Int>, low: Int = 0, high: Int = array.lastIndex, debug: Boolean = false) {
    if (low < high) {
        val middle = (low + high) / 2
        mergeSort(array, low, middle, debug)
        mergeSort(array, middle + 1, high, debug)
        merge(array, low, middle, high, debug)
    }
}

/**
 * 归并排序--合并
 * @param array 要合并的数组
 * @param low 要合并的下界
 * @param middle 要合并的中间间
 * @param high 要合并的上界
 * @param debug 是否输出调试信息
 *
 */
fun merge(array: Array<Int>, low: Int, middle: Int, high: Int, debug: Boolean = false) {
    val lowArraySize = middle - low + 1
    val highArraySize = high - middle

    val lowArray = Array(lowArraySize, { 0 })
    val highArray = Array(highArraySize, { 0 })


    for (i in 0 until lowArraySize) {
        lowArray[i] = array[low + i]
    }

    for (i in 0 until highArraySize) {
        highArray[i] = array[middle + i + 1]
    }


    var i = 0
    var j = 0
    var k = low

    while (i < lowArraySize && j < highArraySize) {
        if (lowArray[i] <= highArray[j]) {
            array[k++] = lowArray[i++]
        } else {
            array[k++] = highArray[j++]
        }
    }
    while (i < lowArraySize) {
        array[k++] = lowArray[i++]
    }
    while (j < highArraySize) {
        array[k++] = highArray[j++]
    }

    if (debug) {
        printlnArray(array = array)
    }


}

fun main(args: Array<String>) {
    val array = arrayOf(5, 2, 4, 7, 1, 3, 2, 6)
    printlnArray("排序前:", array)
    mergeSort(array, debug = true)
    printlnArray("排序后:", array)
}

运行结果：

排序前:5 2 4 7 1 3 2 6 
2 5 4 7 1 3 2 6 
2 5 4 7 1 3 2 6 
2 4 5 7 1 3 2 6 
2 4 5 7 1 3 2 6 
2 4 5 7 1 3 2 6 
2 4 5 7 1 2 3 6 
1 2 2 3 4 5 6 7 
排序后:1 2 2 3 4 5 6 7