一、算法思想
1. 算法描述
- 从第2个元素开始（第1个元素就是已排好序的），从已排好序的后面开始，依次与该元素比较
- 如果元素比该元素大，则向后顺移一位，否则继续向前比较
- 如果元素比该元素小，或者已到最前面，即该元素最小，则插入该元素到当前位置
- 重复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
