简单排序之插入排序

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 826 | 阅读时长 ≈ 1 分钟

直接插入排序 T=O(N^2)


　　

基本思想：

　将A[0]作为一个有序序列，然后将剩余n-1个元素依次插入该有序序列，
　每插入一个元素后依然保持该序列有序，经过n-1次插入操作后可排序完成。
　插入排序，在一般情况下，比冒泡排序快一倍，比选择排序快一点。 　　

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class InsertSortTest {

    private static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) { 
            int j = i; //从后向前查找元素A[i]要插入序列A[i-1]~A[0]中的位置
            int temp = arr[i]; //先将带插入元素存入临时变量
            while (j > 0 && temp < arr[j - 1]) { 
                arr[j] = arr[j - 1]; //遇到比A[i]大的元素就将它后移一位
                --j;
            }
            arr[j] = temp; //下标j最终就是带插入元素的插入位置
        }
    }
}

　　

插入排序的效率：

　　这个算法中，第一趟排序最多比较一次，第二趟排序最多比较两次，以此类推，最后一趟最多比较N-1次，

　　对于随机顺序的数据，插入排序也需要O(N^2)时间级，可是当数据基本有序，插入排序几乎只需要O(N)时间，

　　这对于把一个基本有序的文件进行排序是个简单有效的方法。

　　对于逆序排列的数据，每次比较和移动都会执行，所以插入排序不比冒泡排序快。

---------------- The End ----------------
0%