插入排序

排序演算法是《資料結構與演算法》中最基本的演算法之一。排序演算法可以分為內部排序和外部排序，內部排序是資料記錄在記憶體中進行排序，而外部排序是因排序的資料很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、氣泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是插入排序演算法：

插入排序的程式碼實現雖然沒有氣泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序演算法，它的工作原理是通過構建有序序列，對於未排序資料，在已排序序列中從後向前掃描，找到相應位置並插入。

插入排序和氣泡排序一樣，也有一種優化演算法，叫做拆半插入。

1. 演算法步驟

將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最後一個元素當成是未排序序列。

從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的後面。）

2. 動圖演示

---

程式碼實現

JavaScript

例項

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

Python

例項

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

Go

例項

func insertionSort(arr []int) []int {
        for i := range arr {
                preIndex := i - 1
                current := arr[i]
                for preIndex >= 0 && arr[preIndex] > current {
                        arr[preIndex+1] = arr[preIndex]
                        preIndex -= 1
                }
                arr[preIndex+1] = current
        }
        return arr
}

Java

例項

public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 對 arr 進行拷貝，不改變引數內容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 從下標為1的元素開始選擇合適的位置插入，因為下標為0的只有一個元素，預設是有序的
        for (int i = 1; i < arr.length; i++) {

            // 記錄要插入的資料
            int tmp = arr[i];

            // 從已經排序的序列最右邊的開始比較，找到比其小的數
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的數，插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }
}

PHP

例項

function insertionSort($arr)
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $preIndex = $i - 1;
        $current = $arr[$i];
        while($preIndex >= 0 && $arr[$preIndex] > $current) {
            $arr[$preIndex+1] = $arr[$preIndex];
            $preIndex--;
        }
        $arr[$preIndex+1] = $current;
    }
    return $arr;
}

C

例項

void insertion_sort(int arr[], int len){
        int i,j,key;
        for (i=1;i<len;i++){
                key = arr[i];
                j=i-1;
                while((j>=0) && (arr[j]>key)) {
                        arr[j+1] = arr[j];
                        j--;
                }
                arr[j+1] = key;
        }
}

C++

例項

void insertion_sort(int arr[],int len){
        for(int i=1;i<len;i++){
                int key=arr[i];
                int j=i-1;
                while((j>=0) && (key<arr[j])){
                        arr[j+1]=arr[j];
                        j--;
                }
                arr[j+1]=key;
        }
}

C#

例項

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

Swift

例項

for i in 1..<arr.endIndex {
    let temp = arr[i]
    for j in (0..<i).reversed() {
        if arr[j] > temp {
            arr.swapAt(j, j+1)
        }
    }
}

原文地址：https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/3.insertionSort.md

參考地址：https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F

以下是熱心網友對插入排序演算法的補充，僅供參考：

熱心網友提供的補充1：

我編寫了Lua的版本：

-- 插入排序function insert_sort(tab)    len = maxn_ex(tab)    for i=1,len-1 do      local j = i+1      while( j > 1 )  do        if(tab[j] < tab[j-1]) then          tab[j],tab[j-1] = tab[j-1],tab[j]        end        j = j -1      end     end    return tabend

以上為插入排序演算法詳細介紹，插入排序、希爾排序、選擇排序、氣泡排序、歸併排序、快速排序、堆排序、基數排序等排序演算法各有優缺點，用一張圖概括：

關於時間複雜度

平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和氣泡排序。

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸併排序；

O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數。 希爾排序

線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。

關於穩定性

穩定的排序演算法：氣泡排序、插入排序、歸併排序和基數排序。

不是穩定的排序演算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：資料規模

k："桶"的個數

In-place：佔用常數記憶體，不佔用額外記憶體

Out-place：佔用額外記憶體

穩定性：排序後 2 個相等鍵值的順序和排序之前它們的順序相同