有一个已经有序的数据序列，要求来自在这个已经排好的数据360百科序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新兵饭少态静似损这的排序方法--插入排序法守团密变却史画吗,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个司类数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部免支犯短分包含了这个数组的所有元素，但将最后一个元素除外(让数组多一个空间才建收汽分强省建督有插入的位置)，而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后，再将这个最后元素插入到已企汽之希约制排好序的第一部分中。
插入排序的基本思想是:每步将一个待排序的纪录，按其关键码值的大小插染入前面已经排序的文件中适当位置上，直误到全部插入完为止。
- 中文名 插入排序
- 外文名 insertion sorting
- 类 型 排序方法
- 分 类 直接插入排序，二分插入排序
基本简介
有来自一个已经有序的数据序列，要求在这个已经排好的数据序列中编乙市村规电乎聚较哥重插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法
基本思想
将n个元素的数列分为已有序和无序两个部分，如下所示：
插入排序 {{a1}，{a2，a3，a4，…，an}}
{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴360百科}}
…
{{a1(n-1），a2(n-1) ，…},{an(n-1)}}
每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。
算法步骤
⒈从有序数列和无序数列{a2,a3，…，an}方指述自么接脸敌国吃规开始进行排序；
⒉处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序来自的。用ai与ai-1，a i-2，…，a1进行比较，找出合适的位置将ai插入；
⒊重复第二步，共进行n-i次插入处理，数列全部有序。
void insertSort(Type* arr,long len)/*InsertSort algorithm*/
{
long i=0,j=0;/*iterator value*/
Type tmpData;
assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n");
for(i=1;i<len;i++)
{
j=i;
tmp机经类评异热见开采军Data=*(arr + i);
while(j > 0 && tmpData < arr[j-1])
{
arr[j]=arr[j-1];
j--;
}
arr[j尽之式燃否修误货]=tmpData;
}
严已}
算法思路
假定这个数组的食剧序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后，可以保证a[1…k]是局部有序的，保证了插入过程的正确性.
算法描述
望免块掉垂移逐二快且基 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫备教描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排者过思病方路才亚船序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
算法方法
算法设计有很多方法。插入排序使用的是增量360百科（incremental）方法；在排好字数组A[1..j-1]后，将A[j]插入，形成排好序的子数组A[1..j]；
算法实现
伪代码
INSERTION-SORT(A)
1刘内现坚段 forj← 2 tolength[A]
2 dokey← A[j]
3 Insert A[j] into the sorted sequence A[1..j-1].
4 i← j-1
5 whilei>0 and A [i] >key
6 do A [i+1] ← A [i]
7 i ← i-1
8 A[i+1] ← key
C语言示例
示例代码为C语言，输入参数中易业称连王术白女语守香，需要排序的数组为array[]，起始索引为first，终止索引为last。示例代码的函数采用in-place排序，调用完成后，array[]中从first到last处于升序排列。
void insertion_sort(int array[],unsigned int first,unsigned int last)
{
int i,友孩包论j;
int temp;
for (i = first+1; i<=last;i++)
{
temp = 三养胜三过五里array;
j=i-1;
//与已排序的数逐季者增额末一比较，大于temp时，该数移纸操杂素后
while((j>=first) && (array[j] > te选职随使深便美古季mp))
{
a航金材别一rray[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}
这个更好：
void InsertSort(char array[],unsigned int n)
{
int i,j;
int temp;
for(i=1;i<n;i++)
{
里没子害 temp = array;//store the original sorted array i希带封次n temp
for(j=i ; j>0 && temp < array[j-1] ; j--)//compare the new array with temp
{
array[j]=array[j-1];//all larger elements are moved one pot to the right
}
array[j]=temp;
}
}
这个是c++语言版本的插入排序。为了支持list使用了std::advance（）。
#include <iterator>
template<typename biIter>
void insertion_sort(biIter begin,biIter end)
{
typedef typename std::iterator_traits<biIter>::value_type value_type;
biIter bond = begin;
std::advance(bond,1);
for(; bond!=end; std::advance(bond,1)) {
value_type key = *bond;
biIter ins = bond;
biIter pre = ins;
std::advance(pre,-1);
while(ins!=begin && *pre>key) {
*ins = *pre;
std::advance(ins,-1);
std::advance(pre,-1);
}
*ins = key;
}
}
语言示例代码
Procedure InsertSort(Var R : FileType);
//对R[1..N]按递增序进行插入排序，R[0]是监视哨//
Begin
for I := 2 To N Do //依次插入R[2],...,R[n]//
begin
R[0] := R; J := I - 1;
While R[0] < R[J] Do //查找R的插入位置//
begin
R[J+1] := R[J]; //将大于R的元素后移//
J := J - 1
end
R[J + 1] := R[0] ; //插入R //
end
End; //InsertSort //
C语言代码
int[] arry = new int[] { 23,45,16,7,42};
for (int i = 1; i < arry.Length; i++)
{
int curvalue = arry;
int temp = i;
while (temp >0&&arry [temp -1]>curvalue)
{
arry [temp ]=arry [temp -1];
temp --;
}
arry[temp] = curvalue;
}
foreach (int i in arry)
{
Console.WriteLine(i);
}
Console.Read（）； AAuto语言示例代码
io.open();//打开控制台
/*
*-------------------------------------------------------
* 插入排序
**------------------------------------------------------
*/
//插入排序算法
insert_sort = function(array){
for(right=2;#array) {
var top = array[right];
//Insert array[right] into the sorted seqquence array[1....right-1]
var left = right -1;
while(left and array[left]>top){
array[left+1] = array[left];
left--;
}
array[left+1] = top;
}
return array;
}
//插入排序算法 - 倒序
insert_sort_desc = function(array){
for(right=2;#array) {
var top = array[right];
//Insert array[right] into the sorted seqquence array[1....right-1]
var left = right -1;
while(left and array[left]<top){
array[left+1] = array[left];
left--;
}
array[left+1] = top;
}
return array;
}
io.print("----------------")
io.print("插入排序（原地排序）")
io.print("----------------")
array ={12;3;556;7;17788;23};
insert_sort_desc(array)
//输出结果
for(i=1;#array;1){
io.print(array)
}
execute("pause") //按任意键继续
io.close();//关闭控制台
这是C#版，完整的代码，采用产生随机数，然后在利用插入排序重新排列。语言方式与C以及C++都有所不同，方法都是产用类的形式来表达。
class Program
{
class Carry
{
private int[] arr;
private int numitems;
private int upper;
public Carry (int size) //构建数组
{
arr = new int[size];
upper = size - 1;
numitems = 0; ;
}
public void insert(int items)//向数组中添加数据
{
for (int i = 0; i < upper ; i++)
arr[numitems] = items;
numitems++;
}
public void display()//打印数组
{
for (int i = 0; i < upper; i++)
Console.Write(arr+" ");
}
public void insert sort()//插入排序
{
for (int outer = 1; outer <= upper; outer++)
{
int temp=arr[outer];
int inner = outer ;
while(inner>0&&(int)arr[inner-1] >= temp)
{
arr[inner] = arr[inner - 1];
inner --;
}
arr[inner] = temp;
}
}
}
static void Main(string[] args)
{
Carry arry = new Carry⑽；//初始化一个10个数据元素的数组
Random rnd = new Random(100);//在1到100中随机产生10个数作为数组成员
for (int i = 0; i < 10; i++)
{
arry.insert(rnd.Next (0,100));
}
arry.insertsort ();//调用插入排序
arry.display();//打印数组
Console.ReadKey();
}
}
Java语言代码
public class InsertSort {
public static void main(String[] args) {
insertSort(new int[]{8,2,4,9,3,6,7,10});
}
// 辅助函数
public static void dumpArray(int[] a) {
for (int index = 0; index < a.length; index++) {
System.out.print(a[index] + " ");
}
System.out.println("");
}
public static void insertSort(int[] a) {
// 输出原始数组
dumpArray(a);
for (int index = 1; index < a.length; index++) {
int subIndex = index;
int currentData = a[index]; // 等待插入的数据
while ((subIndex > 0) && (a[subIndex - 1] > currentData)) {
a[subIndex] = a[subIndex - 1];
subIndex--;
}
a[subIndex] = currentData; // 插入到合适的位置
// 每次排序后也输出
dumpArray(a);
}
}
}
CL语言代码
（defun insert-sort (lt)
（do ((index 1 (1+ index)))
（（>= index (length lt)) nil)
（let ((temp (elt lt index)))
（do ((j 0 (1+ j)))
（（> j index))
（if (> (elt lt j) temp)
（progn
（do ((z index (1- z)))
（（<= z j))
（setf (elt lt z) (elt lt (- z 1))))
（setf (elt lt j) temp)
（return)))))))
（defun test-sort ()
（let ((lt (make-array 10 :fill-pointer 0)))
（dotimes (var 10)
（vector-push (random 10) lt))
（format t "~a~%" lt)
（insert-sort lt)
（format t "~a~%" lt)))
P代码实现
def insertion_sort(sort_list):
list_len = len(sort_list)
for i in range(1,list_len):
j = i -1
key = sort_list
while j >= 0 and sort_list[j] > key:
sort_list[j + 1] = sort_list[j]
j -= 1
sort_list[j + 1] = key
return sort_list
算法时间
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
插入排序
包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。
评论留言