四种插入排序

每个标题下分别给出主函数和测试用例，总的排序代码放在最后，表排序有详细注释，方便理解。

目录

第1关直接插入排序

第2关二分插入排序

第3关表插入排序

第4关shell排序

插入排序代码

---

第1关直接插入排序

int main(void)
{
  int cnt ;
  SortObject *p ;
  p = (SortObject*)malloc(sizeof(SortObject));
 linkObject *head ;
 head = (linkObject*)malloc(sizeof(linkObject));
 head->next = NULL;
  scanf("%d",&cnt);
  p->NUM = cnt ;
  p->data = (DataType*)malloc(sizeof(DataType)*cnt);
  printf("the result of listSort:\n");
  for(int i=0;i
  {
   scanf("%d",&p->data[i]);
   
  } 
  insertSort(p);
 
  
 
}

测试输入：

8 49 38 65 97 76 113 27 49

—— 预期输出 ——

the result of listSort:

38 49 65 97 76 113 27 49

38 49 65 97 76 113 27 49

38 49 65 97 76 113 27 49

38 49 65 76 97 113 27 49

38 49 65 76 97 113 27 49

27 38 49 65 76 97 113 49

27 38 49 49 65 76 97 113

第2关二分插入排序

int main(void)
{
  int cnt ;
  SortObject *p ;
  p = (SortObject*)malloc(sizeof(SortObject));
 linkObject *head ;
 head = (linkObject*)malloc(sizeof(linkObject));
 head->next = NULL;
  scanf("%d",&cnt);
  p->NUM = cnt ;
  p->data = (DataType*)malloc(sizeof(DataType)*cnt);
 //printf("the result of binInsertSort:\n");
  for(int i=0;i
  {
   scanf("%d",&p->data[i]);
   
  } 
  binInsertSort(p);
 
  
 
}

测试输入：

8 38 49 65 97 76 113 27 49

—— 预期输出 ——

the result of binInsertSort:

38 49 65 97 76 113 27 49

38 49 65 97 76 113 27 49

38 49 65 97 76 113 27 49

38 49 65 76 97 113 27 49

38 49 65 76 97 113 27 49

27 38 49 65 76 97 113 49

27 38 49 49 65 76 97 113

第3关表插入排序

int main(void)
{
  int data ;
  int cnt ;
 
 linkObject *head,*p ;
 head = (linkObject*)malloc(sizeof(linkObject));
 head->next = NULL;
  scanf("%d",&cnt);
  
 for(int i=0;i
 {
  scanf("%d",&data);
   p = (linkObject*)malloc(sizeof(linkObject));
 p->next = head->next;
 p->info = data;
 head->next = p ;
 }
 printf("the result of linkSort:\n");
 listSort(head);
 
  
 
}

第4关shell排序

int main(void)
{
  int cnt ;
  SortObject *p ;
  p = (SortObject*)malloc(sizeof(SortObject));
 linkObject *head ;
 head = (linkObject*)malloc(sizeof(linkObject));
 head->next = NULL;
  scanf("%d",&cnt);
  p->NUM = cnt ;
  p->data = (DataType*)malloc(sizeof(DataType)*cnt);
 
  for(int i=0;i
  {
   scanf("%d",&p->data[i]);
   
  } 
  shellSort(p,cnt/2);
 
  
 
}

测试输入：

8 49 38 65 97 13 76 27 49

—— 预期输出 ——

13 38 27 49 49 76 65 97

13 38 27 49 49 76 65 97

13 27 38 49 49 65 76 97

插入排序代码

#include 
#include 
 
/*数据结构定义*/
typedef int DataType;
typedef struct
{
  DataType *data; //用于存放待排序关键字的起始地址
  int NUM; //待排序关键字的个数 
} SortObject;
 
typedef struct node //用于表插入排序的数据结构
{
  DataType  info;  
  struct node *next;  
} linkObject;
 
//输出顺序表
void print(SortObject *p)
{
 for(int i=0;iNUM;i++)
   printf("%d ",p->data[i]);
 printf("\n");  
}
 
//输出链表
void printLink(linkObject *Head)
{
  linkObject *p = Head->next ;
  while(p)
  {
    printf("%d ",p->info);
    p = p->next;
  }
   printf("\n");
}
 
/*第一关
此处请填写代码实现递增序进行直接插入排序,
 要求每趟排序后 调用print函数，输出关键字的排列情况*/
void insertSort( SortObject *Rec )
{
  
 /*----begin------*/
 DataType temp;
 DataType *data = Rec->data;
 int i,j;
 
 for(i=1;iNUM;i++){
   temp = data[i];
   for(j = i-1 ; j >= 0 && temp
     data[j+1] = data[j];
   }
   data[j+1] = temp;
   print(Rec);
 }
 
 /*-----end------*/
 
}
 
/*第二关
此处请填写代码实现递增序进行二分插入排序,
 
  实质是在已经有序的表中采用二分法查找插入位置
  要求每趟排序后 调用print函数，输出关键字的排列情况*/
void binInsertSort(  SortObject *Rec )
{
 printf("the result of binInsertSort:\n");
 /*----begin------*/
 int i,j,left,mid,right;
 DataType *data = Rec->data;
 for(i = 1;iNUM;i++){
   DataType temp = data[i];
   left = 0,right = i-1;
   while(left<=right){
     mid = (left+right)>>1;
     if(temp>data[mid])left = mid+1;
     else right = mid - 1;
   }
  for(j = i-1;j>=left;j--)
    data[j+1] = data[j];
  data[left] = temp;
  print(Rec);
 }
 /*-----end------*/
 
}
 
/* 第四关
此处请填写代码实现递增序进行shell排序,
  
  要求每趟排序后 调用print函数，输出关键字的排列情况
  */
void shellSort( SortObject *Rec,int d )
{
  int i,j,inc;
  DataType* temp;
  DataType* data = Rec->data;
  for(inc = d ; inc>0;inc/=2){
    for(i = inc;iNUM;i++){
      temp = data[i];
      //这边都是inc范围的移动
      for(j = i - inc;j>=0&&data[j]>temp;j-=inc)
        data[j+inc] = data[j];
      data[j+inc] = temp;
    }
    print(Rec);
  }
}
 
/*第三关
此处请填写代码实现递增序进行表插入排序,
  返回值是关键字比较次数
  Head是表头结点，不存放数据，info是待插入数据
  要求每趟排序后 调用printLink函数，输出关键字的排列情况
  */
void listSort(linkObject *plist )
{
 
 /*----begin------*/
 linkObject *head,*p,*q,*pre,*now;
 head = plist;
 pre = head->next;
 if(pre==NULL)return;
 now = pre ->next;
 if(now==NULL)return;
 printLink(plist);
 while(now!=NULL){
  (void)(q = head),p = q->next;
   while(p!=now&&p->infoinfo){q = q->next,p = q->next;}
   if(p==now){pre = pre->next;now = pre->next; continue;}
   pre->next = now->next;
   q->next = now;
   now->next = p;
   now = pre->next;
   printLink(plist);
 }
 
 /*-----end------*/
 
}