几个常用排序算法

插入排序

fun insertSort(arr: IntArray) {
    for (i in 1 <em>until </em>arr.size) {
        val temp = arr[i]
        var preIndex = i - 1
        while (preIndex >= 0 && arr[preIndex] > temp) {
            arr[preIndex + 1] = arr[preIndex]
            preIndex--
        }
        arr[preIndex + 1] = temp
    }
}

希尔排序

fun shellSort(array: IntArray) {
    val len = array.size
    var temp: Int
    var gap = len / 2
    while (gap > 0) {
        for (i in gap until len) {
            temp = array[i]
            var preIndex = i - gap
            while (preIndex >= 0 && array[preIndex] > temp) {
                array[preIndex + gap] = array[preIndex]
                preIndex -= gap
            }
            array[preIndex + gap] = temp
        }
        println(array.contentToString())
        gap /= 2
    }
}

快速排序

fun quickSort(arr: IntArray, left: Int, right: Int) {
    if (left < right) {
        var i = left
        var j = right
        val datum = arr[left]
        while (i < j) {
            //从右往左找不大于基准位的数据
            while (i < j && arr[j] > datum) {
                j--
            }
            //将不大于基准位的数据填入到左边空位
            if (i < j) {
                arr[i++] = arr[j]
            }
            //从左往右找不小于基准位的数据
            while (i < j && arr[i] < datum) {
                i++
            }
            //将不小于基准位的数据填入到右边空位
            if (i < j) {
                arr[j--] = arr[i]
            }
        }
        //将基准数据放入到最后的空位
        arr[i] = datum
        //递归调用, 对基准值两侧的数组排序
        quickSort(arr, left, i - 1)
        quickSort(arr, i + 1, right)
    }
}

堆排序

private var len: Int = 0
fun heapSort(arr: IntArray) {
    len = arr.size
    buildMaxHeap(arr)
    while (len > 0) {
        println(arr.contentToString())
        swap(arr, 0, len - 1)
        len--
        adjustHeap(arr, 0)
        println(arr.contentToString())
    }
}

private fun buildMaxHeap(arr: IntArray) {
    for (i in (len / 2 - 1) downTo 0) {
        adjustHeap(arr, i)
    }
}

private fun adjustHeap(arr: IntArray, i: Int) {
    var maxIndex = i
    if (i * 2 < len && arr[i * 2] > arr[maxIndex]) {
        maxIndex = i * 2
    }
    if (i * 2 + 1 < len && arr[i * 2 + 1] > arr[maxIndex]) {
        maxIndex = i * 2 + 1
    }
    if (maxIndex != i) {
        swap(arr, maxIndex, i)
        adjustHeap(arr, maxIndex)
    }
}

private fun swap(arr: IntArray, i1: Int, i2: Int) {
    val temp = arr[i1]
    arr[i1] = arr[i2]
    arr[i2] = temp
}