插入排序算法

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}

排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是插入排序算法：

插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應(yīng)該是最容易理解的了，因為只要打過撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

插入排序和冒泡排序一樣，也有一種優(yōu)化算法，叫做拆半插入。

1. 算法步驟

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

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

2. 動圖演示

代碼實現(xiàn)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 arrGo實例 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 進行拷貝，不改變參數(shù)內(nèi)容? ? ? ? int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);? ? ? ? // 從下標為1的元素開始選擇合適的位置插入，因為下標為0的只有一個元素，默認是有序的? ? ? ? for (int i = 1; i < arr.length; i++) {? ? ? ? ? ? // 記錄要插入的數(shù)據(jù)? ? ? ? ? ? int tmp = arr[i];? ? ? ? ? ? // 從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)? ? ? ? ? ? int j = i;? ? ? ? ? ? while (j > 0 && tmp < arr[j - 1]) {? ? ? ? ? ? ? ? arr[j] = arr[j - 1];? ? ? ? ? ? ? ? j--;? ? ? ? ? ? }? ? ? ? ? ? // 存在比其小的數(shù)，插入? ? ? ? ? ? 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=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=0) && (key= 0;j--)? ? ? ? {? ? ? ? ? ? if(array[j] > temp)? ? ? ? ? ? {? ? ? ? ? ? ? ? array[j + 1] = array[j];? ? ? ? ? ? ? ? array[j] = temp;? ? ? ? ? ? }? ? ? ? ? ? else? ? ? ? ? ? ? ? break;? ? ? ? }? ? }}Swift實例 for i in 1.. 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

以下是熱心網(wǎng)友對插入排序算法的補充，僅供參考：

熱心網(wǎng)友提供的補充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 tab
end

以上為插入排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等排序算法各有優(yōu)缺點，用一張圖概括：

關(guān)于時間復(fù)雜度

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

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

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

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

關(guān)于穩(wěn)定性

穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。

不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數(shù)據(jù)規(guī)模

k："桶"的個數(shù)

In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存

Out-place：占用額外內(nèi)存

穩(wěn)定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同