突破算法第二天-插入排序

突破算法第二天-插入排序:
今天是突破算法第二天,插入排序,比较简单。效率比较低,但是思想很广泛,应用很广,是很多高级排序算法的一个子过程。

插入排序的原理

将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录
看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。
要点:设立哨兵,作为临时存储和判断数组边界之用

插入排序原理

插入排序java实现

1
2
3
4
5
6
7
8
9
10
11
12
public static void insertSort(int[] a, int n) {
for (int i = 0; i < n; i++) {
for (int j = i; j > 0 && (a[j]<a[j-1]); j--) {
swap(a, j, j-1);
}
}
}
private static void swap(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}

算法复杂度

插入排序的复杂度为O(n^2)

改进方法

希尔排序,其他的插入排序有二分插入排序,2-路插入排序。

适用场景

插入排序比较适合部分有序的数组(以下四种数组)

  • 数组中每个元素距离它的最终位置都不远
  • 一个有序的大数组接一个小数组
  • 数组中只有几个位置不正确
  • 数组比较小

博客搬家,请访问新博客地址吧! 我的博客

文章目录
  1. 1. 插入排序的原理
  2. 2. 插入排序java实现
  3. 3. 算法复杂度
  4. 4. 改进方法
  5. 5. 适用场景
,