选择排序法

object SelectionSort {
    fun <E : Comparable<E>> sort(array: Array<E>) {
        for (index in array.indices) {
            //arr[i..n)未排序 arr[0..i)已排序
            //arr[i..n)中的最小值要放到arr[i]的位置
            var minIndex = index
            for (j in minIndex until array.size) {
                if (array[j] < array[minIndex]) {
                    minIndex = j
                }
            }
            array.swap(index, minIndex)
        }
    }

    private fun <E> Array<E>.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}

时间复杂度O(n^2)

object InsertionSort {
//正序交换排序
    fun <E : Comparable<E>> sort(array: Array<E>) {
        //  保持[0,i)有限有序,[i,array.length)无序
        for (i in array.indices) {
            // 保证[0,i)每个元素都比前一个元素大
            for (j in i downTo 1) {
                if (array[j] < array[j - 1]) {
                    array.swap(j, j - 1)
                } else {
                    break
                }
            }
        }
    }
//正序原地排序
    fun <E : Comparable<E>> sort2(array: Array<E>) {
        for (i in array.indices) {
            val e = array[i]
            var j: Int = i
            while (j > 0) {
                if (e < array[j - 1]) {
                    array[j] = array[j - 1]
                } else {
                    break
                }
                j--
            }
            array[j] = e
        }
    }
//逆序排序
    fun <E : Comparable<E>> sort3(array: Array<E>) {
        for (i in array.size - 1 downTo 0) {
            val e = array[i]
            var j = i
            while (j < array.size - 1) {
                if (e > array[j + 1]) {
                    array[j] = array[j + 1]
                } else {
                    break
                }
                j++
            }
            array[j] = e
        }
    }


    private fun <E> Array<E>.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}

时间复杂度O(n^2)

选择排序和插入排序的区别在于无论数组是否有序,选择排序的时间复杂度都是O(n^2),插入排序在数组有序的情况下,时间复杂度会变成为O(n)

Q.E.D.