Sort Algorithms

算法中的排序 based on kotlin

定义通用接口

interface Sort<T : Comparable<T>> {

    /**
     * Sorts the given array in ascending order.
     *
     * @param arr the array to be sorted
     */
    fun sort(arr: Array<T>)

}

fun <T : Comparable<T>> Array<T>.swap(i: Int, j: Int) {
    if (i == j) return
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}

O(n^2)

时间复杂度为 \(\mathrm{O}(N^2)\) 的主要原因是没有进行分治，而是通过两层循环来实现排序。

插入排序

在本身数组是有序的清空下，插入排序时间复杂度为 \(\mathrm{O}(N)\)

class InsertSort<T : Comparable<T>> : Sort<T> {

    override fun sort(arr: Array<T>) {
        if (arr.isEmpty() || arr.size == 1) return
        val n = arr.size
        for (i in 1 until n) {
            for (j in i downTo 1) {
                if (arr[j] < arr[j - 1]) {
                    arr.swap(j, j - 1)
                }
            }
        }
    }

}

O(nlog(n))

时间复杂度为 \(\mathrm{O}n(\log(n))\) 的排序算法一般都是基于分治的思想来实现的。

快速排序

快速排序的实现到可优化点，单路快排 -> 双路快排 -> 三路快排

class QuickSort<T : Comparable<T>> : Sort<T> {

    override fun sort(arr: Array<T>) {
        if (arr.isEmpty() || arr.size == 1) return
        quickSort(arr, 0, arr.size - 1)
    }

    private fun quickSort(array: Array<T>, left: Int, right: Int) {
        if (left >= right) return

        val pivotIndex = oneWay(array, left, right)

        quickSort(array, left, pivotIndex - 1)
        quickSort(array, pivotIndex + 1, right)

    }

    private fun oneWay(arr: Array<T>, left: Int, right: Int): Int {
        val pivot = arr[left]

        var start = left + 1
        var end = right

        while (true) {
            if (arr[start] <= pivot) {
                start++
            } else {
                arr.swap(end, start)
                end--
            }
            // 极限情况
            // case1: start=r+1 pivot 全小于 arr[l+1...r]
            // case2: end=l     pivot 全大于等于 arr[l+1...r]
            // 终止的本质是 start=end+1
            if (start > end) {
                break
            }
        }

        arr.swap(left, end)
        return end
    }

    private fun twoWay(arr: Array<T>, left: Int, right: Int): Int {
        val pivot = arr[left]
        var start = left + 1
        var end = right

        while (true) {
            while (start <= end && arr[start] < pivot) {
                start++
            }
            while (end >= start && arr[end] >= pivot) {
                end--
            }

            if (start > end) {
                break
            }
            arr.swap(start, end)
        }

        arr.swap(left, end)
        return end
    }

}

归并排序

归并排序分为两种，自顶向下，自底向上。以下的简单实现为 自顶向下 的实现。

class MergeSort<T : Comparable<T>> : Sort<T> {

    override fun sort(arr: Array<T>) {
        if (arr.isEmpty() || arr.size == 1) return
        this.divide(arr, 0, arr.size - 1)
    }

    private fun divide(array: Array<T>, left: Int, right: Int) {
        if (left >= right) return

        val mid = (left + right) / 2
        divide(array, left, mid)
        divide(array, mid + 1, right)
        merge(array, left, mid, right)
    }

    private fun merge(array: Array<T>, left: Int, mid: Int, right: Int) {
        val size = right - left + 1
        val tmp: Array<Comparable<T>> = Array(size) { array[left] }

        var x = left
        var y = mid + 1
        var tmpIndex = 0

        // 处理左右两个子数组，直到其中一个处理完
        while (x <= mid && y <= right) {
            tmp[tmpIndex++] = if (array[x] <= array[y]) {
                array[x++]
            } else {
                array[y++]
            }
        }

        // 处理左子数组剩余元素
        while (x <= mid) {
            tmp[tmpIndex++] = array[x++]
        }

        // 处理右子数组剩余元素
        while (y <= right) {
            tmp[tmpIndex++] = array[y++]
        }
        // 将临时数组中的元素复制回原数组
        System.arraycopy(tmp, 0, array, left, size)
    }

}