算法设计：插入排序法
一、算法思想
直接插入排序是一种简单的排序方法，具体做法是：在插入第i个记录时，R1、R2、…、Ri-1已经排序好，这时将Ri的关键字Ki依次与关键字Ki-1、Ki-2等进行比较，从而找到应该插入的位置并将Ri插入，插入位置及其后的记录依次向后移动
插入排序：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成
二、算法实现步骤
例如一个序列：{20,40,30,10,60,50}，我们用这个序列做一个直接插入的例子
1、首先第一趟，将第一个序列中第一个元素保留，将第二个元素和它比较，如果大就插入到后面，如果小就插入到前面
第一趟：{ 20 , 40 }
2、第二趟，保留第一第二个元素，将第三个元素和第二个比较，如果大就插入到第二个元素后面，如果小就插入到第二个元素前面；接着和第一个元素比较，如果大就插入到第一个元素后面，如果小就插入到第一个元素前面
第一趟：{ 20 , 40 }
第二趟：{ 20 , 3 0 , 40 }
3、第三趟以及其他趟如上，结果如下图
三、算法实现
1、使用Java语言
public static void insertSort(int[] array)
{
//第0位独自作为有序数列，从第1位开始向后遍历
for(int i=1;i<array.length;i++)
{
// 0到i-1位为有序，若第i位小于i-1位，继续寻位并插入，
//否则认为0~i位也是有序的，忽略此次循环，相当于continue
if(array[i]<array[i-1])
{
int temp=array[i];//保存第i位的值
int k = i - 1;
//从第i-1位向前遍历并移位，直至找到小于第i位值停止
for(int j=k;j>=0 && temp<array[j];j--)
{
array[j+1]=array[j];
k--;
}
//插入第i位的值
array[k+1]=temp;
}
}
}
2、C/C++实现
#include<iostream>
using namespace std;
int main()
{
int a[]={98,76,109,34,67,190,80,12,14,89,1};
int k=sizeof(a)/sizeof(a[0]);
int j;
for(int i=1;i<k;i++)//循环从第2个元素开始
{
if(a[i]<a[i-1])
{
int temp=a[i];
for(j=i-1;j>=0 && a[j]>temp;j--)
{
a[j+1]=a[j];
}
a[j+1]=temp;//此处就是a[j+1]=temp;
}
}
for(int f=0;f<k;f++)
{
cout<<a[f]<<" ";
}
return 0;
}
3、python语言
def insertSort(relist):
len_ = len(relist)
for i in range(1,len_):
for j in range(i):
if relist[i] < relist[j]:
//首先碰到第一个比自己大的数字，
//赶紧刹车，停在那，所以选择insert
relist.insert(j,relist[i])
//因为前面的insert操作，所以后面位数+1，
//这个位置的数已经insert到前面去了，所以pop弹出
relist.pop(i+1)
break
return relist
