插入排序
2021-04-14 18:27
标签：int bsp sort 开始 存储 col pre 算法 插入 基本思路分析： 首先选择第一个数作为基数，因为只有一个数，所以他就是一个有序的数组嘛。 然后遍历他后面的数，如果比他小，插入到他前面，如果比他大，就插入到他后面。此时就有两个数已经成为有序的了； 在遍历下一个数，找到他该插入的位置，即该位置的后一个数比改数大，前一个数比该数小。 5 1 4 2 3 —— 排序时，先进行比较的是1，他的位置就应该在五前面，5后移，1插入 1 5 4 2 3 —— 第二趟，排4了，4比5小，5后移，四的位置暂时在1和5之间，再看1和4比较，正好4比1大，因此不用把1后移，直接将4插入 1 4 5 2 3 ..... 1 2 3 4 5 另一套同样思路不同表达方式 插入排序 标签：int bsp sort 开始 存储 col pre 算法 插入 原文地址：https://www.cnblogs.com/zzxisgod/p/13335721.htmlpublic static int [] insertSort(int [] array){
for (int i = 1; i ) {
//定义一个变量，存储待插入的数据
int shouldInsert = array[i];
//定义一个变量，用来存储待插入的数的之前的下标
int beforeInsertIndex = i - 1;
while (beforeInsertIndex >= 0 && shouldInsert array[beforeInsertIndex]){
//将该位置的数后移，给待插入的数腾出位置来
array[beforeInsertIndex + 1] = array[beforeInsertIndex];
beforeInsertIndex --;
}
//退出while表示已经找到了要插入的位置
array[beforeInsertIndex + 1] = shouldInsert;
}
return array;
}
//定义一个插入排序的算法
public static int [] insertSort1(int [] array){
for (int i = 0; i 1; i++) {
//定义一个变量，保存待插入的数据(在最开始，待插入的数据是array[1])
//即现在为第二个数据
int shouldInsert = array[i+1];
//定义一个变量，用来读取待插入的数据的前面一个数据
//即现在为第一个数据
int beforeInsert = i;
int count = -1;
while (beforeInsert >= 0 && shouldInsert array[beforeInsert]){
//把待插入的数字的前一个数字后移
count++;
array[beforeInsert + 1] = array[beforeInsert];
beforeInsert--;
}
array[i - count] = shouldInsert;
}
return array;
}