插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
1. 算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。
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;
}
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;
}
}
Java
1 public class InsertSort implements IArraySort {
2
3 @Override
4 public int[] sort(int[] sourceArray) throws Exception {
5 // 对 arr 进行拷贝，不改变参数内容
6 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
7
8 // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
9 for (int i = 1; i < arr.length; i++) {
10
11 // 记录要插入的数据
12 int tmp = arr[i];
13
14 // 从已经排序的序列最右边的开始比较，找到比其小的数
15 int j = i;
16 while (j > 0 && tmp < arr[j - 1]) {
17 arr[j] = arr[j - 1];
18 j--;
19 }
20
21 // 存在比其小的数，插入
22 if (j != i) {
23 arr[j] = tmp;
24 }
25
26 }
27 return arr;
28 }
29 }
案例：
本题要求实现直接插入排序函数，待排序列的长度1<=n<=1000。
函数接口定义：
void InsertSort(SqList L);
其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：
typedef int KeyType;
typedef struct {
KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/
int Length;
}SqList;
裁判测试程序样例：
#include<stdio.h>
#include<stdlib.h>
typedef int KeyType;
typedef struct {
KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/
int Length;
}SqList;
void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/
void InsertSort(SqList L);
int main()
{
SqList L;
int i;
CreatSqList(&L);
InsertSort(L);
for(i=1;i<=L.Length;i++)
{
printf("%d ",L.elem[i]);
}
return 0;
}
/*你的代码将被嵌在这里 */
输入样例：
第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：
10
5 2 4 1 8 9 10 12 3 6
输出样例：
输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。
1 2 3 4 5 6 8 9 10 12
void InsertSort(SqList L){
int i,j;
int temp;
for(i=1;i<=L.Length;i++){
for(j=i+1;j<=L.Length;j++){
if(L.elem[i]>L.elem[j]){
temp = L.elem[j];
L.elem[j] = L.elem[i];
L.elem[i] = temp;
}
}
}
}