.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}
排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是插入排序算法：
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
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 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 进行拷贝，不改变参数内容 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
=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
以下是热心网友对插入排序算法的补充，仅供参考：
热心网友提供的补充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以上为插入排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括： 
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
n：数据规模
k："桶"的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
科技
