InsertSort
插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
插入排序(Insertion Sort)
基本原理
每步将一个待排序的元素,将其插入前面已排好序的部分中,直到全部插入完为止。
算法步骤
- 将待排序序列第一个元素看做已排序序列,把第二个元素到最后一个元素当成是未排序序列
- 从未排序序列中取出下一个元素记为 a,在已排序的序列中从后向前扫描
- 如果该元素(已排序)大于 a,将该元素移到下一位置
- 重复步骤 3,直到找到已排序的元素小于或者等于 a 的位置
- 将 a 插入到该位置后
- 重复步骤 2~5,直至没有未排序元素
动画演示
参考实现
1 | import java.util.Arrays; |
复杂度分析
排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
插入排序 | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) | \(O(1)\) | In-place | 稳定 |
References
-
2019-05-24
桶排序(Bucket sort)或箱排序(Bin sort),是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是 鸽巢排序 的一种归纳结果。
-
2019-05-24
在计算机科学中,选择排序(Selection sort)是一种排序算法,切确的说是就地比较排序。它具有 \(O(n^2)\) 时间复杂度,使其在大型列表上效率低下,并且通常比类似的插入排序更差。选择排序因其简单性而着称,并且在某些情况下具有优于更复杂算法的性能优势,特别是在辅助存储器有限的情况下。
-
2019-05-24
冒泡排序(Bubble Sort) 是一种简单的排序算法,它重复遍历列表,比较相邻的两个元素,如果它们的顺序错误则交换它们。
-
2019-05-24
计数排序(Counting sort)是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组 C ,其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。
-
2019-05-24
基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到 1887 年 Herman Hollerith 在打孔卡片制表机(Tabulation Machine)上的贡献。