插入排序，一般也被稱為直接插入排序。對于少量元素的排序，它是一個有效的算法 。插入排序是一種最簡單的排序方法，插入排序和冒泡排序一樣，也有一種優化算法，叫做拆半插入，下面為大家詳細講解一下插入排序。

算法步驟

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

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

動圖演示

代碼實現

JavaScript

實例

function insertionSort(arr) {
   var len = arr.length;
   var preIndex, current;
   for (var i = 1; 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 while (j > 0 && tmp 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;iwhile((j>=0) && (key

C#

實例

public static void InsertSort(int[] array)
{
   for(int i = 1;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..let temp = arr[i]
   for j in (0..reversed() {
       if arr[j] > temp {
           arr.swapAt(j, j+1)
       }
   }
}