开发者博客:www.developsearch.com
插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好序,本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,为元素 x “腾位置”,最后将 k 对应的元素值赋为 x ,插入排序也是根据排序的特性来命名的。
以下是一个实例,红色 标记的数字为插入的数字,被划掉的数字是未参与此次排序的元素,红色 标记的数字与被划掉数字之间的元素为逐个向后移动的元素,比如第二趟参与排序的元素为 [11, 31, 12] ,需要插入的元素为 12 ,但是 12 当前并没有处于正确的位置,于是我们需要依次与前面的元素 31 、 11 做比较,一边比较一边移动比较过的元素,直到找到第一个比 12 小的元素 11 时停止比较,此时 31 对应的索引 1 则是 12 需要插入的位置。
- 初始: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
- 第一趟: [11, 31 , 12, 5, 34, 30, 26, 38, 36, 18] (无移动的元素)
- 第二趟: [11, 12 , 31, 5, 34, 30, 26, 38, 36, 18] ( 31 向后移动)
- 第三趟: [5 , 11, 12, 31, 34, 30, 26, 38, 36, 18] ( 11, 12, 31 皆向后移动)
- 第四趟: [5, 11, 12, 31, 34 , 30, 26, 38, 36, 18] (无移动的元素)
- 第五趟: [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] ( 31, 34 向后移动)
- 第六趟: [5, 11, 12, 26 , 30, 31, 34, 38, 36, 18] ( 30, 31, 34 向后移动)
- 第七趟: [5, 11, 12, 26, 30, 31, 34, 38 , 36, 18] (无移动的元素)
- 第八趟: [5, 11, 12, 26, 30, 31, 34, 36 , 38, 18] ( 38 向后移动)
- 第九趟: [5, 11, 12, 18 , 26, 30, 31, 34, 36, 38] ( 26, 30, 31, 34, 36, 38 向后移动)
插入排序会优于选择排序,理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势,有效地减少一些比较的次数,当然这种优势得看数组的初始顺序如何,最坏的情况下(给定的数组恰好为倒序)插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ,这种极端情况下,插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法,插入效率与数组初始顺序息息相关。一般情况下,插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。
实现代码:
/** * Insertion Sorting */ INSERTION(new Sortable() { public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { int len = array.length; for (int i = 1; i < len; i++) { T toInsert = array[i]; int j = i; for (; j > 0; j--) { int compare = array[j - 1].compareTo(toInsert); if (compare == 0 || compare < 0 == ascend) { break; } array[j] = array[j - 1]; } array[j] = toInsert; } } })
相关推荐
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
该资源提供了Java中实现插入排序的全面指南。文档中涵盖了插入排序的基本概念,包括如何对数组进行排序以及如何在Java中实现插入排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现插入排序,包括详细的...
详解Java常用排序算法-插入排序
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
java编写的插入排序算法
Java语言实现的直接插入排序算法,代码里头有详细注释,注释皆为简单英文,因为这个算法比较简单,欢迎新手下载学习使用,欢迎后期的学习交流!
java实现的常用的几种基本排序算法,插入、交换、选择、归并
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
编写选择排序,插入排序,自顶向上合并排序,合并排序,快速排序,理解各排序算法的实现原理,加深对排序算法的理解。
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
插入排序算法java代码,望对大家有帮助
Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的氣泡排序 Heap 排序法 - 改良的選擇排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 搜尋 循序搜尋法(使用衛兵...
插入排序是一种简单但有效的排序算法,它将数组分成已排序部分和未排序部分,然后逐个将未排序部分的元素插入到已排序部分的合适位置,逐步构建有序数组。在这个教程中,我们将深入研究插入排序的原理,并提供一个...
该文档涵盖了数组排序的基本概念,包括如何实现各种排序算法,如冒泡排序、选择排序、插入排序、归并排序和快速排序。此外,文档还为每个排序算法提供了详细的代码示例和实现细节。 该文档还涵盖了高级主题,如如何...
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。
Java的算法 排序算法 冒泡排序 堆排序 插入排序 合并排序 快速排序 选择排序 希尔排序
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
java代码-插入排序算法的改进
八大排序java实现版本,直接插入排序、折半插入排序、冒泡排序、简单选择排序、希尔插入排序、快速排序 、堆排序、2-路归并排序 、基数排序,并有时间比较,博文...