[排序算法2] - 直接插入排序

 

包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。属于稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置） 。

 

基本思想：

 

将n个元素的数列分为已有序和无序两个部分，如下所示：

{{a1}，{a2，a3，a4，…，an}}

{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}

…

{{a1(n-1），a2(n-1) ，…},{an(n-1)}}

 

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

假设在一个无序的数组中，要将该数组中的数按插入排序的方法从小到大排序。假设啊a[]={3,5,2,1,4};插入排序的思想就是比大小，满足条件交换位置，一开始会像冒泡排序一样，但会比冒泡多一步就是交换后（a[i]=a[i+1]后）原位置（a[i]）会继续和前面的数比较满足条件交换，直到a[i+1]前面的数组是有序的。比如在第二次比较后数组变成a[]={2,3,5,1,4};

 

插入排序过程示例

 

算法复杂度

 

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

 

稳定性

 

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

 

算法的实现：

 

public class InsertSort {

    public static void main(String[] args) {
        int a[] = new int[]{1, 7, 9, 3, 5, 8, 6, 10, 6};
        System.out.print("Before sort: ");
        for (int i : a) {
            System.out.print(i + " ");
        }
        sort(a);
        System.out.print("\nAfter sort: ");
        for (int i : a) {
            System.out.print(i + " ");
        }
    }

    private static void sort(int arr[]) {
        for (int i=1; i< arr.length; i++) {
            for (int j =i; j > 0; j--) {
                // 只要小于前面有序数组中任何一个，就交换
                if (arr[j] < arr[j-1]) {
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                } else {
                    //不用交换，直接跳出
                    break;
                }
            }
            //输出每一步的结果
            System.out.println();
            for (int t : arr) {
                System.out.print(t + " ");
            }
        }
    }

}

 

结果：

 

Before sort: 1 7 9 3 5 8 6 10 6 
1 7 9 3 5 8 6 10 6 
1 7 9 3 5 8 6 10 6 
1 3 7 9 5 8 6 10 6 
1 3 5 7 9 8 6 10 6 
1 3 5 7 8 9 6 10 6 
1 3 5 6 7 8 9 10 6 
1 3 5 6 7 8 9 10 6 
1 3 5 6 6 7 8 9 10 
After sort: 1 3 5 6 6 7 8 9 10 

 

 算法演示： http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/straight_insertion_sort.asp