本文为Kotlin代码，整理了
归并排序
冒泡排序
快速排序
插入排序（直接插入排序）
插入排序（希尔排序）

1. 归并排序

此算法用到了分治策略：
将原问题划分成n个规模较小而结构与原问题相似的子问题；
递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

代码

class MergeSort {
    private fun sort(array: IntArray, low: Int, mid: Int, high: Int) {
        // 存储归并后的临时数组
        val temp = IntArray(high - low + 1)
        // 记录第一个数组中需要遍历的下标
        var i = low
        // 记录第二个数组中需要遍历的下标
        var j = mid + 1
        // 用于记录在临时数组中的下标
        var index = 0
        // 遍历两个数组，取出较小的数字放入临时数组中
        while (i <= mid && j <= high) {
            if (array[i] < array[j]) {
                temp[index++] = array[i++]
            } else {
                temp[index++] = array[j++]
            }
        }
        while (j <= high) {
            temp[index++] = array[j++]
        }
        while (i <= mid) {
            temp[index++] = array[i++]
        }
        for (k in temp.indices) {
            array[k + low] = temp[k]
        }
    }

    fun mergeRecursion(array: IntArray, low: Int, high: Int) {
        val mid = (low + high) / 2
        // 结束条件
        if (low<high) {
            //处理左边
            mergeRecursion(array, low, mid)
            println("左边排序${array.contentToString()}")
            //处理右边
            mergeRecursion(array, mid + 1, high)
            println("右边排序${array.contentToString()}")
            //归并
            sort(array, low, mid, high)
        }
    }
}

调用

fun main() {
    val arr = intArrayOf(15, 7, 2, 9, 4, 1, 0, 8, 5, 3)
    MergeSort().mergeRecursion(arr, 0, arr.size - 1)
    println(arr.contentToString())
}

结果

2. 冒泡排序

就像水里的泡泡，越大的泡泡往上浮的速度越快。

代码

// 需要比较 len - 1 轮
class BubbleSort {
    fun start(arr: IntArray): IntArray {
        val len = arr.size
        for (i in 0 until len-1) {
            for (j in 0 until len-i-1) {
                if (arr[j] > arr[j+1]) {
                    val tmp = arr[j]
                    arr[j] = arr[j+1]
                    arr[j+1] = tmp
                }
            }
            println(arr.contentToString())
        }
        return arr
    }
}

调用

fun main() {
    val arr = intArrayOf(15, 7, 2, 9, 4, 1, 0, 27, 5)
    BubbleSort().start(arr)
}

结果

还可以进一步进行优化，如果排序不改变，就跳出循环。

3. 快速排序

代码

class QuickSort {
    fun sort(array: IntArray, start: Int, end: Int){
        if (start < end) {
//        第0个数为标准数
            val target = array[start]
//        记录排序的下标
            var low = start
            var high = end
//        循环找比标准数大的数和比标准数小的数
            while (low < high) {
//            右边的数字大于左边的数字
                while (low < high && array[high] > target) {
                    high--
                }
//            使用右边的数字替换左边的数字
                array[low] = array[high]
//            左边的数字小于标准数
                while (low < high && array[low] < target) {
                    low++
                }
                array[high] = array[low]
            }
            array[low] = target
//        处理所有小的数字
            sort(array, start, low)
//        处理所有大的数字
            sort(array, high + 1, end - 1)
        }
    }
}

调用

fun main() {
    val arr = intArrayOf(15, 7, 2, 9, 4, 1, 0, 27, 5)
    QuickSort().sort(arr, 0, arr.size-1)
    println(arr.contentToString())
}

结果

4. 插入排序（直接插入排序）

此算法遍历时，当前值的左边是有序数列

代码

class InsertSort {
    fun sort(array: IntArray) {
        val len = array.size
        for (i in 1 until len) {
            println(array.contentToString())
            if (array[i - 1] > array[i]) {
//                存放当前值
                val tmp = array[i]
//                遍历前面的数字，前一个数字放到后一个位置
                for (j in i - 1 downTo 0) {
                    array[j+1] = array[j]
                    if (tmp >= array[j]) {
                        array[j+1] = tmp
                        break
                    }
                    if (j == 0) {
                        array[0] = tmp
                    }
                }
            }
        }
    }
}

调用

fun main() {
    val arr = intArrayOf(15, 7, 2, 9, 4, 1, 0, 27, 5,5)
    InsertSort().sort(arr)
    println(arr.contentToString())
}

结果
一
5. 插入排序（希尔排序）

第一轮
分割，步长为9/2 = 4
2 5 3 7 1 8 3 9 0
1 5 3 7 2 8 3 9 0
1 5 3 7 0 8 3 9 2
0 5 3 7 1 8 3 9 2

再分割，步长为4/2 = 2
0 5 1 7 2 8 3 9 3

再分割，步长为2/2 = 1
0 1 2 3 3 5 7 8 9

代码

class ShellSort {
    fun sort(array: IntArray) {
        var d = array.size
        while (d > 0) {
            // 遍历所有的元素
            for (i in d until array.size) {
                // 遍历本组中所有的元素
                var j = i - d
                while (j >= 0) {
                    // 如果大于就交换顺序
                    if (array[j] > array[j + d]) {
                        val temp = array[j]
                        array[j] = array[j + d]
                        array[j + d] = temp
                    }
                    j -= d
                }
            }
            println(array.contentToString())
            // 步长减半
            d /= 2
        }
    }
}

调用

fun main() {
    val arr = intArrayOf(15, 7, 2, 9, 4, 1, 0, 27, 5,5)
    ShellSort().sort(arr)
}

结果：