插入排序(Insertion Sort)
插入排序将已排序部分定义在左端,将未排序部分元的第一个元素插入到已排序部分合适的位置
- 从第一个元素开始,该元素可以认为已经被排序;
- 取出下一个元素,在已经排序的元素序列中从后向前扫描;
- 如果该元素(已排序)大于新元素,将该元素移到前一位置;
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
- 将新元素插入到该位置后;
- 重复步骤2~5。
// Demo(Scala)
package info.aoye
object Test {
def main(args: Array[String]): Unit = {
val array = Array(5, 6, 3, 3, 4, 67, 1)
println(insertionSort(array).toList)
}
def insertionSort(array: Array[Int]): Array[Int] = {
for (i <- 1 until array.length) { // 0 to array length - 1
// 当前位置(数组下表为1,实际上第二个元素)
var index = i
// 当前位置的值
val item = array(i)
// 与前一个值对比,如果前一个值大于当前值,将前一个值付给当前值,索引也向前移动。
while (index > 0 && array(index - 1) > item) {
array(index) = array(index - 1)
index = index - 1
}
// 将当前位置的值放到找到的位置
array(index) = item
}
array
}
}