排序算法 --- 插入排序

之气说到了冒泡和选择排序,接下来看看插入排序。

一、排序思想

把n个待排的元素看成一个有序表和一个无序表,开始时,有序表只包含1个元素,无序表中有n - 1个元素。排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码比较,将它插入适当的位置,使之成为新的有序表。


欢迎大家关注我的公众号 javawebkf,目前正在慢慢地将简书文章搬到公众号,以后简书和公众号文章将同步更新,且简书上的付费文章在公众号上将免费。


1. 案例:

假如现有待排序列如下(带 * 号的是有序表元素):

17*   3    25   14   20   9

那么开始的时候,17就是有序表,剩余元素是一个无序表。

  • 第一次:让3和有序表最后一个元素17比较,发现3比17小,那么就让17往后挪一位,然后让3再和前面的比较,发现前面没有元素了,所以第一次排序后的结果是:
3*   17*    25   14   20   9
  • 第二次:让25和17比较,发现25比17大,那么就不用变换位置,第二次排序后的结果是:
3*   17*    25*   14   20   9
  • 第三次:让14和有序表元素比较,结果是:
3*   14*    17*   25*   20   9
  • 第四次:让20和有序表元素比较,结果是:
3*   14*    17*   20*   25*   9
  • 第五次:让9和有序表元素比较,结果是:
3*   9*   14*    17*   20*   25*

二、代码实现

代码中有详细的注释:

public static void sort(int[] arr) {
    if (arr == null || arr.length == 1) {
        return;
    }
    for(int i=1; i<arr.length; i++) { // 默认第一个是有序表,从第二个元素开始进行插入排序
        int insertVal = arr[i]; // 待排元素
        int insertIndex = i - 1; // 从有序表最后一个元素开始比较
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) { // 如果还没有将有序表比较完 && 待排元素还没找到位置
            arr[insertIndex + 1] = arr[insertIndex]; // 比待排元素大的元素后移一位
            insertIndex --; // 继续往前比较
        }
        // 找到位置后,其他元素都后移了,自己占坑
        if (insertIndex + 1 != i) {
            arr[insertIndex + 1] = insertVal;
        }
    }
}

三、存在的问题

假如现在有如下序列:

16, 23, 12, 8, 1

要求按照从小到大的顺序排列,你会发现,最小的1在最后面,第二小的8在倒数第二个位置,那么在排序的时候,就会发生很多次交换,即while循环里面的代码会执行很多次,1在排序的时候就会执行四次,这样性能就下降了。有没有优化的空间呢?有,那就是希尔排序……

下一篇
举报

扫码关注云+社区

领取腾讯云代金券