算法 ： 插入排序

 算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

代码实现 JavaScript 实例

function insertionSort(arr) {     var len = arr.length;     var preIndex, current;     for (var i = 1; i = 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  0 && tmp  $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 temp)             {                 array[j + 1] = array[j];                 array[j] = temp;             }             else                 break;         }     } }

Swift 实例

for i in 1..