插入排序 （Insertion Sort）

1、概念

插入排序 是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到 O(1)}的額外空間的排序），因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

2、運(yùn)行過(guò)程

插入排序可以分為兩種方式插入，分別是直接插入和折半插入。
我們首先來(lái)看一下直接插入的思路和運(yùn)行過(guò)程

1、直接插入

• 基本思路：
  順序地把待排序的序列中的各個(gè)元素按其關(guān)鍵字的大小，插入到已排序的序列的適當(dāng)位置。

• 運(yùn)行過(guò)程

  • 1、將待排序序列的第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。

  • 2、從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。）

    
    
    image

2、折半插入

• 基本思路：
  順序地把待排序的序列中的各個(gè)元素按其關(guān)鍵字的大小，通過(guò)折半查找插入到已排序的序列的適當(dāng)位置。
• 運(yùn)行過(guò)程
  • 1、將待排序序列的第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。
  • 2、從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置，在查找元素的適當(dāng)位置時(shí)，采用了二分搜索。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。）

3、二分搜索

如何確定一個(gè)元素在數(shù)組中的位置? (假設(shè)數(shù)組里面全都是 整數(shù))
如果是無(wú)序數(shù)組,從第0個(gè)位置開始遍歷搜索,平均時(shí)間復(fù)雜度: 0(n)

image

如果是有序數(shù)組，可以使用二分搜索，最壞時(shí)間復(fù)雜度: 0(logn)

image

二分搜索的思路：

• 假?zèng)]在[begin, end)范圃內(nèi)捜索某個(gè)元素v, mid == (begin + end)/2
• 如果v< m,去[begin, mid)范國(guó)內(nèi)二分搜索
• 如果v> m，去[mid + 1, end)范國(guó)內(nèi)二分搜索

• 如果v== m,直接返回mid

  
  
  image
  
  

  二分查找思路實(shí)現(xiàn)

  
  
  image

4、代碼：

• 直接插入java

public void sort(Integer[] array){
        for (int i = 1; i < array.length; i++) {
            Integer cur = i;
            Integer v = array[cur];
            while (cur > 0 && v < array[cur - 1]){
                array[cur] = array[cur-1];
                array[cur-1] = v;
                cur --;
            }
        }
    }

• 折半插入

    public int[] array;
    public int[]  sort() {
        for (int begin = 1; begin < array.length; begin++) {
            insert(begin, search(begin));
        }
        return array;
    }

    /**
     * 將source位置的元素插入到dest位置
     * @param source
     * @param dest
     */
    private  void  insert (int source ,int dest){
        int v = array[source];
        for (int i = source;i > dest;i--){
            array[i] = array[i - 1];
        }
        array[dest] = v;
    }


    /*
    * 利用二分搜索找到index 位置元素的待插入位置
    * 已經(jīng)排好的數(shù)組的區(qū)間范圍是 【0，index）
    * @param index
    * @return
    */
    private int search(int index){
        int begin = 0;
        int end = index;
        while (begin < end){
            int current = (end + begin)/2;//(end - begin )>>1;
            if (array[index] < array[current] ){
                end = current;
            }else{
                begin = current + 1;
            }
        }
        return begin;
    }

    public void setArray(int[] array) {
        this.array = array;
    }

    public int[] getArray() {
        return array;
    }

5、性能

當(dāng)原始序列“正序”時(shí)，直接插入排序效果最好，所以直接插入排序最好情況下時(shí)間復(fù)雜度為O(n)；當(dāng)原始序列“逆序”時(shí)，直接插入排序效果最差，所以直接插入排序最壞情況下時(shí)間復(fù)雜度為O(n^2)。

直接插入排序平均時(shí)間復(fù)雜度為O(n^2)；空間復(fù)雜度為O(1)；是穩(wěn)定的排序算法。

需要注意的是，使用了二分搜索后,只是減少了比較次數(shù),但插入排序的平均時(shí)間復(fù)雜度依然是0(n^2)

6、逆序?qū)?（Inversion）

什么是逆序?qū)?
數(shù)組<2,3,8,6,1>的逆序?qū)? <2,1> <3,1> <8,1> <8,6> <6,1>,共5個(gè)逆序?qū)?/p>

插入排序的時(shí)間復(fù)雜度與逆序?qū)Φ臄?shù)量成正比關(guān)系
逆序?qū)Φ臄?shù)量越多，插入排序的時(shí)間復(fù)雜度越高

最壞、平均時(shí)間復(fù)雜度: 0(n^2)
最好時(shí)間復(fù)雜度: 0(n)
空間復(fù)雜度: 0(1)

屬于穩(wěn)定排序
當(dāng)逆序?qū)Φ臄?shù)量極少時(shí)，插入排序的效率特別高甚至速度比0(nlogn)級(jí)別的快速排序還要快
數(shù)據(jù)量不是特別大的時(shí)候，插入排序的效率也是非常好的

參考：《戀上數(shù)據(jù)結(jié)構(gòu)與算法第二季》