排序算法——选择排序

一、算法思想

1. 算法描述

1. 从第2个元素开始（第1个元素就是已排好序的），从已排好序的后面开始，依次与该元素比较
2. 如果元素比该元素大，则向后顺移一位，否则继续向前比较
3. 如果元素比该元素小，或者已到最前面，即该元素最小，则插入该元素到当前位置
4. 重复1~3步骤，直至所有元素都排序完成

2. 伪代码

INSERTION-SORT(A){
    for i = 2 to A.length{
        key = A[i]
        // 把 key 插入到已排好序的序列 A[1..i-1] 中
        j = i-1
        while j > 0 and A[j] > key{
            //大于key的元素都向后移动
            A[j+1] = A[j]
            j = j -1
        }
        //插入元素 key
        A[j+1] = key
    }
}

3. 算法流程

插入排序流程

二、算法实现

1. kotlin

/**
 * 插入排序
 * 1. 从第2个元素开始（第1个元素就是已排好序的），从已排好序的后面开始，依次与该元素比较
 * 2. 如果元素比该元素大，则向后顺移一位，否则继续向前比较
 * 3. 如果元素比该元素小，或者已到最前面，即该元素最小，则插入该元素到当前位置
 * 4. 重复1~3步骤，直至所有元素都排序完成
 * @author likly
 * @version 1.0
 */

/**
 * 插入排序
 * @param array 要排序的数组
 * @param debug 是否输入每次排序后的结果
 */
fun insertSort(array: Array<Int>, debug: Boolean = false) {
    //从第2个元素（下标为1）起，依次遍历
    for (i in 1 until array.size) {
        //记录当前元素为 key
        val key = array[i]
        //从已排好序的最后开始
        var j = i - 1
        //如果未遍历完，并且当前位置的值大于key元素的值，那么该元素向后位移一位
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j]
            j--
        }
        //把key元素插入到当前位置
        array[j + 1] = key
        if(debug){
            printlnArray("第${i}次排序：",array)
        }
    }
}

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

运行结果：

排序前：5 2 4 6 1 3 
第1次排序：2 5 4 6 1 3 
第2次排序：2 4 5 6 1 3 
第3次排序：2 4 5 6 1 3 
第4次排序：1 2 4 5 6 3 
第5次排序：1 2 3 4 5 6 
排序后：1 2 3 4 5 6