一、简介
插入排序，就是假定一个参考值，假设该参考值左边的元素都有序，那么从该元素开始从后往前挨个查找，如果找到比参考值大的数，那么就将这个大的数后移，如果未找到比参考值大的数，说明不用移动元素。循环比较，这样经过比较后移之后就会空出下标为0的位置，用于存放这个参考值。
二、排序思路
排序思路：（假设从小到大）
【1】 待排序数组: 5, 6, 3, 7, 2, 1
【2】第一趟: 参考值指向第二个元素6, 假设6左面的元素 5 为有序的,从5开始,6和5比较,因为 6 > 5,没有找到比6大的数，因此不用右移,于是第一趟结果为: 5,6,3,7,2,1
【3】第二趟: 参考值指向第三个元素3, 经过第一趟排序3左边的元素 5,6 已经有序,从3开始从后往前挨个比较, 3 < 6,将6往后移,3 < 5,将5也往后移,这时候空出第一个位置用于填充参考值3,于是第二趟排序结果为: 3,5,6,7,2,1
【4】第三趟: 参考值指向第四个元素7, 经过第二趟排序后7左边的元素 3,5,6 已经有序,从7开始从后往前挨个比较, 7 > 6,7 > 5, 7 > 3,没有找到比7大的数,因此不用右移,于是第三趟结果为: 3,5,6,7,2,1
【5】第四趟: 参考值指向第五个元素2, 经过第三趟排序后2左边的元素 3,5,6,7 已经有序,从2开始从后往前挨个比较, 2 < 7,将7往后移, 2 < 6, 将6也往后移; 2 < 5,将5往后移;2 < 3 ,将3也往后移,这时空出第一个位置用于填充参考值2,于是第四趟结果为: 2,3,5,6,7,1
【6】第五趟: 参考值指向第六个元素1, 经过第三趟排序后1左边的元素 2,3,5,6,7 已经有序,从1开始从后往前挨个比较, 1 < 7,将7往后移,1 < 6,将6也往后移; 1 < 5,将5往后移;1 < 3 ,将3也往后移;1 < 2 ,将2也往后移,这时候空出第一个位置用于填充参考值1,于是第五趟结果为: 1,2,3,5,6,7
【7】元素已经有序，排序完毕。
三、代码实现
int arr[] = {5,6,3,7,2,1};
for (int i=1;i<arr.length;i++) {
for (int j=i;j>0;j--) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
Log.d(TAG, "after sort="+Arrays.toString(arr));
四：原理分析：
网友评论