Java数据结构与算法中的排序算法(三)插入排序法详解

 插入排序法属于内部排序法,是对欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。

插入排序法的思想:

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

排序代码如下:

   //插入排序    public static void insertsort(int[] arr) {        //定义待插入的数        int insertVal = 0;        int insertIndex = 0;          for (int i = 1; i < arr.length; i++) {            insertVal = arr[i];            insertIndex = i - 1;  //arr[1]前面哪个数的下标
//给insertVal找到插入的位置 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { //insertIn >=0保证在给insertVal找插入位置时,不越界 如果insertVal < arr[insertIndex],说明还没有找到位置 arr[insertIndex + 1] = arr[insertIndex]; insertIndex--;
} //当退出while循环时,说明插入的位置找到,insertIndex+1 if (insertIndex + 1 != i) { arr[insertIndex + 1] = insertVal; } // System.out.println("第" + i + "轮插入"); // System.out.println(Arrays.toString(arr)); } }

举一个例子来验证:

Java数据结构与算法中的排序算法(三)插入排序法详解

  可以看到,假设数组中共有6个数,那么需要排序5轮,正确。

  同样,我们随即生成8000个数,存入数组,比较排序算法的运行时间:

Java数据结构与算法中的排序算法(三)插入排序法详解

  发现选择排序算法的时间还是比较快的。

来源:琢磨先生DataBase,本文观点不代表自营销立场,网址:https://www.zyxiao.com/p/125773

发表评论

登录后才能评论
侵权联系
返回顶部