inserts.cpp

来自「非常全的排序算法c实现」· C++ 代码 · 共 46 行

/*算法思想简单描述：
 在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排
 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
 也是排好顺序的。如此反复循环，直到全部排好顺序。*/
#include<iostream.h>//直接插入排序
#define MAX 4
void insert_sort(int a[],int n);
int main()
{ 
   int *p, i,n,a[MAX];
   n=MAX;
   p=a;

   cout<<"Input "<<n<<" number for sorting :"<<endl;
   for(i=0;i<MAX;i++)
   {
	 cin>>a[i];
   }
   cout<<endl;
   insert_sort(p,MAX);

   cout<<"After insert_sort:"<<endl;
   for(i=0;i<MAX;i++)
   {
     cout<<a[i]<<" ";
   }
   cout<<endl;
   return 0;
}


void insert_sort(int a[],int n)//直接插入排序
{
   int i,j,t;

   for(i=1;i<n;i++) //要选择的次数：1~n-1共n-1次
   { 
      t=a[i];//暂存下标为i的数.下标从1开始
      for(j=i-1;j>=0&&t<a[j];j--)//注意:j=i-1,j--,这里就是下标为i的数,在它前面有序列中找插入位置。
	  {
         a[j+1]=a[j]; //如果满足条件就往后挪
	  }
      a[j+1]=t; //找到下标为i的数的放置位置
   }
}