定义
无聊的解释（百度百科）：
假设我们输入的是 5，1，4，2，3 我们从第二个数字开始，这个数字是1，我们的任务只要看看1有没有正确的位置，我们的做法是和这个数字左边的数字来比，因此我们比较1和5，1比5小，所以我们就交换1和5，原来的排列就变成了 1，5，4，2，3
接下来，我们看第3个数字有没有在正确的位置。这个数字是4，它的左边数字是5，4比5小，所以我们将4和5交换，排列变成了 1，4，5，2，3我们必须继续看4有没有在正确的位置，4的左边是1，1比4小，4就维持不动了，以此类推。。。
插入排序的日常应用
简单示例
Java示例代码
两种：1.交换；2.赋值
public class InsertSort {
public static void main(String[] args) {
int[] arr = SortUtils.getRandomIntArray(10000, 1, 1000);
insertSort2(arr);
SortUtils.printArray(arr);
}
private static void insertSort(int[] arr) {
int length = arr.length;
for (int i = 1; i < length; i++) {
//寻找元素arr[i]的合适插入位置
//1.如果j-1位置值比j位置值大，交换
for(int j=i;j>0;j--){
if(arr[j]<arr[j-1]){
SortUtils.swap(arr,j,j-1);
}else{
break;
}
}
}
}
private static void insertSort2(int[] arr) {
int length = arr.length;
for (int i = 1; i < length; i++) {
//寻找元素arr[i]的合适插入位置;
// 1.提取出arr[i];
// 2.如果j-1位置的数比j位置值大，j位置值等于j-1位置;
// 3.把提取出来的值赋值给及位置
int temp = arr[i];
int j = i;
for(;j>0;j--){
if(arr[j-1]>temp){
arr[j] = arr[j - 1];
}else{
break;
}
}
arr[j] = temp;
}
}
}
Kotlin
fun main(args: Array<String>) {
val arr = SortUtils.getRandomIntArray(10000,1,1000)
insertSortKt2(arr)
SortUtils.printArray(arr)
}
//交换
fun insertSortKt(arr:IntArray){
val length =arr.size
for ((key,value) in arr.withIndex()){
var j = key
while (j>0&&(arr[j-1]-arr[j])>0){
SortUtils.swap(arr,j-1,j)
j--
}
}
}
//赋值
fun insertSortKt2(arr:IntArray){
val length =arr.size
for ((key,value) in arr.withIndex()){
var j = key
var temp =arr[j]
while (j>0&&(arr[j-1]-temp)>0){
arr[j]=arr[j-1]
j--
}
arr[j]=temp
}
}
后记
- 赋值的排序方法要比交换的运行速度快。尤其是一些数据基本已经有序，只有几个无序时，尤其适用。
- Kotlin不能直接使用工具类中的反射，这个还没太研究明白=。=
