/**
* 插入排序
*/
@Service
public class InsertionSort implements Sort {
@Override
public String getName() {
return "插入排序";
}
@Override
public int[] sortArray(int[] nums) {
int t;
for (int i = 1; i < nums.length; i++) {
//先将待处理元素保存到临时变量
t = nums[i];
//从i的前一个元素开始往前找
for (int j = i - 1; j >= 0; j--) {
if (nums[j] > t) {
//元素比t大,后移
nums[j + 1] = nums[j];
} else {
//元素比t小或等于,则j+1的位置为t应该存在的位置,并结束循环
nums[j + 1] = t;
break;
}
}
}
return nums;
}
}
解释:
插入排序有一个很形象的比喻,那就是打扑克牌,在打扑克牌对牌整理的时候,其实就是一个插入排序。左手是整理好的扑克牌,右手一次取一张牌,将右手的牌按照大小顺序插入到左手中正确的位置,这就是插入排序。
实际在代码实现中,因为插入操作对数组来说,就会带来插入位置后面数据的后移操作,所以需要额外处理下,具体逻辑参见代码。