简单排序之插入排序
1.什么是插入排序
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。
2.插入排序图解
3.插入排序代码实现
public static void insertSort(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
int key = nums[i];
for (int j = i; j >= 0; j--) {
if (j > 0 && nums[j - 1] > key) {
nums[j] = nums[j - 1];
} else {
nums[j] = key;
break;
}
}
}
}
4.插入排序效率
在大多数情况下 ,插入排序算法是基本的排序算法中最好的一种 。虽然插入排序算 法仍然需要 O(N²)的时间 ,但是在一般情况下 ,它要比冒泡排序快一倍 ,比选择排序还要快一点 。 尽管它比冒炮排序算法和选择排序算法都更麻烦一些 ,但它也并不很复杂 。它经常被用在较复杂的 排序算法的最后阶段 ,例如快速排序 。
这个算法需要多少次比较和复制呢 ?在第一趟排序中 ,它最多比较一次 ,第二趟最多比较两次 , 依此类推 。最后一趟最多 ,比较 N-1 次 。因此有
1 + 2 + 3 + + N I = N*(N-1) /2
然而 ,因为在每一趟排序发现插入点之前 ,平均只有全体数据项的一半真的进行了比较 ,我们除以 2 得到
N * (N-1)/4
复制的次数大致等于比较的次数 。然而 ,一次复制与一次交换的时间耗费不同 ,所以相对于随 机数据 ,这个算法比冒泡排序快一倍 ,比选择排序略快 。
在任意情况下 ,和其他的基本排序算法一样 ,对于随机顺序的数据进行插入排序也需要 O(N²)的时间级。
对于己经有序或基本有序的数据来说 ,插入排序要好得多 。当数据有序的时候 ,while 循环的 条件总是假 ,所以它变成了外层循环中的一个简单语句 ,执行 N-1 次 。在这种情况下 ,算法运行只 需要 O(N)的时间 。如果数据基本有序 ,插入排序几乎只 需要 O(N)的时间 ,这对把一个基本有序的 文件进行排序是一个简单而有效的方法 。
然而 ,对于逆序排列的数据 ,每次比较和移动都会执行 ,所以插入排序不比冒泡排序快 。
参考:
《java数据结构和算法》
上一篇: Java8日期和时间段的计算
下一篇: 算法设计与分析实践-作业4