30天挑战数据结构和算法之第3天插入排序

今天是30天挑战数据结构和算法的第三天，周末早早起床就为了完成这个任务，今天的内容是插入排序。

插入排序的原理是外部循环未排序的元素，内部循环从最后一个已排序的元素索引进行递减一直到0，如果发现当前元素比未排序的元素大，则将当前元素向右移动一个位置。直到当前元素比未排序的元素小，此时跳出内循环，插入未排序的元素。

伪代码如下

mark first element as sorted

for each unsorted element X

  'extract' the element X

  for j = lastSortedIndex down to 0

    if current element j > X

      move sorted element to the right by 1

    break loop and insert X here

用程序的角度去理解就是，不断地去检查前一个元素是否比当前元素大，如果是的话就进行交换。如果用javascript实现的话，如下。

function MyInsertionSort() {
    this.sort = function(array) {
        for (var i = 0; i < array.length; i++) {
            for (var j = i; j > 0; j--) {
                if (array[j-1] > array[j]) {
                    var temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                } else {
                    break;
                }
            }
        }
        return array;
    }
}

var sorter = new MyInsertionSort();
var notSortedArr = [15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19];
var sortedArr = sorter.sort(notSortedArr);
console.log(sortedArr);

然后是ruby的版本

def my_insertion_sort(array)
    0.upto(array.size - 1) do |i|
        j = i
        while j > 0 and array[j-1] > array[j]
            array[j-1], array[j] = array[j], array[j-1]
            j = j - 1
        end
    end
end

list = [15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19]
my_insertion_sort(list)
print list, "\n"

最后是java版本

import java.util.Arrays;

public class MyInsertionSort {

    private static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j-1] > array[j]) {
                    int temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                } else {
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19};
        sort(arr);
        System.out.println(Arrays.toString(arr));    
    }
}

下面来算算时间复杂度

外层循环：1+2+3+...+(n-3)+(n-2)+(n-1)=Sn

内层循环：(n-1)+(n-2)+(n-3)+...+3+2+1=Sn

两式相加一共n-1个n，得出Sn=n(n-1)/2，和n^2成正比，所以平均时间复杂度为O(N^2)。

最优时间复杂度为O(N)，仅当每个元素都是顺序排列的情况下。

最差时间复杂度为O(N^2)。

空间复杂度为O(1)。

举个插入排序在生活中的例子，大家在打牌的时候习惯将牌按照顺序插入到合适的位置，这个时候就会用到插入排序。

最后的总结，要说和冒泡排序有什么异同，相同的地方在于时间复杂度都一样。不同的地方在于，在内循环中冒泡排序算法采用元素索引升序顺序来定位当前元素，而插入排序算法采用元素索引降序顺序来定位当前元素。此外冒泡排序是当前元素和后一个元素比较，而插入排序是当前元素和前一个元素比较。