插入排序

发布于: 2020 年 06 月 24 日
插入排序

原理:将需要排序的数据划分为已排序区间未排序区间,初始状态下未排序数据的第一个元素作为已排序区间,然后依次将未排序区间的元素插入到已排序区间的合适位置,直到全部排序完成。

如果对数组8,5,1,5,3,2,4进行插入排序动态演示图如下:

插入排序演示

Java代码实现如下:

public static void insertionSort(int[] a) {
if (a == null || a.length == 0) return;
for (int i = 1; i < a.length; ++i) {
int j = i;
int value = a[i];
//待排序的元素与已排好序区间的元素一一比较找到合适的位置
while (j > 0 && value < a[j-1]) {
//已排序元素依次往后移
a[j] = a[--j];
}
//将待排序元素值放入到合适位置
a[j] = value;
}
}

插入排序是一种稳定的排序算法

插入排序的时间复杂度是O(n²)

发布于: 2020 年 06 月 24 日 阅读数: 8
用户头像

wjchenge

关注

还未添加个人签名 2018.07.27 加入

还未添加个人简介

评论

发布
暂无评论
插入排序