插入排序的思想与实现InsertSort

插入排序的思想与实现InsertSort

简单来说，插入排序的思想是将待排序数列（这里用数组表示）分为已排好序和未排好序的两部分，一般将前面先排有序，例如：a[0]...a[i]已经有序，剩下的任务就是将a[i+1]...依次插入到前面有序的数列中，并同时使前面的序列仍然有序。

插入排序的开销主要在：找待插入的位置。最坏的情况是原序列是逆序的，每次都要找到最前，开销是 1+2+3+...n-1=n*(n-1)/2,故时间复杂度是O(n*n).

在插入的过程中还需要平移前面的数列。但是这个时间开销是伴随寻找插入位置同时进行的。下面是一段代码，包含测试代码，可直接运行。

#include "stdafx.h"
#include"iostream"
using namespace std;
int* insertsort(int a[],int m);
int _tmain(int argc, _TCHAR* argv[])
{
 int a[5]={1,3,4,2,0};
 cout<<"Please input five numbers:"<<endl;
 for(int i=0;i<5;i++)
 {
  cin>>a[i];
 }
 int *c=insertsort(a,5);
 for(int i=0;i<5;i++)
  cout<<*(c+i)<<endl;
 cout<<"finished input";
 return 0;
}
int*  insertsort(int a[],int m)
{
 for(int i=0;i<m-1;i++)  // i从0开始到i-1,j从i+1开始，到m
 {
  int j=i+1;  //从i后面的第一个元素开始一次向前进行比较
  int temp=a[j];//这一步是为了保存a[j]的值以便之后进行交换，否则有可能会被a[i]覆盖
  while(i>=0&&temp<a[i])
  {
   a[i+1]=a[i]; //否的话因为需要将a[i]往后移位
   i--;//继续往前比较
   
  }
  ///退出循环要么是找到了比a[j]小的a[i],那么从这个i+1到j-1的位置均后移了，所以要将temp赋值给a[i+1];
  //第二种情况是i已经减小到-1,所以将temp直接插到a[0]
  a[i+1]=temp;
 }
 return a;
}