nbpx.txt

对十种内部排序的比较．有直接排序

				(*CmpNum)++;
                for(int j=last; temp[j]>L->r[i].key; j--) 
				{
				    (*CmpNum)++;
                    temp[j+1]=temp[j]; 
				}
                temp[j+1]=L->r[i].key; //插入待插元素         
                last++;   
			} 
			
		}
        //复制回原数组
        if(first<last)
            for(i=0; i<MAXSIZE; i++) 
			{
			L->r[i].key=temp[i];
				(*ChgNum)++;
			}
        else 
			{
			    for(i=first; i<=MAXSIZE; i++) 
				{
					L->r[i-first].key=temp[i];
						(*ChgNum)++;
				}
                for(i=0; i<=last; i++) 
				{
					L->r[MAXSIZE-first+i].key=temp[i]; 
						(*ChgNum)++;
				}
			}
	

      }


void SelectSort(){
  printf("1. 插入排序\n");
  printf("2. 希尔排序\n");
  printf("3. 快速排序\n");
  printf("4. 堆排序\n");
  printf("5. 冒泡排序\n");
  printf("6. 选择排序\n");
  printf("7. 折半插序\n");
  printf("8. 归并排序\n");
  printf("9. 基数排序\n");
  printf("10. 2-路插入排序\n");
  printf("11. 以上所有排序方式\n");
  printf("12. 退出程序\n\n");
  printf("Please Select the Operate:");
}

void AllAbove(LinkList *L, int *CmpNum, int *ChgNum){
  int i;
  
  int dlta[3] = {
    7, 3, 1
  };
  int Indata[1] = {
    1
  };
  
  for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];				//随机数列复位
  printf("\n插入排序:\n");
  
  ShellSort(L, Indata, 1, &CmpNum[0], &ChgNum[0]);
  
  printf("\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[0], ChgNum[0]);
  
     
  for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];				//随机数列复位
  printf("\n希尔排序:\n");
  
  ShellSort(L, dlta, 3, &CmpNum[1], &ChgNum[1]);
  
  printf("\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[1], ChgNum[1]);
  
  for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];				//随机数列复位
  printf("\n快速排序:\n");
  
  QuickSort(L, &CmpNum[2], &ChgNum[2]);
  
  printf("\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[2], ChgNum[2]);
  

  for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];				//随机数列复位
  printf("\n堆排序:\n");
  
  HeapSort(L, &CmpNum[3], &ChgNum[3]);
  
  printf("\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[3], ChgNum[3]);
 

  for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];				//随机数列复位
  printf("\n冒泡排序:\n");
  
  BubbleSort(L, &CmpNum[4], &ChgNum[4]);
  
  printf("\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[4], ChgNum[4]);
  
  for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];				//随机数列复位
  printf("\n选择排序:\n");
  
  SelSort(L, &CmpNum[5], &ChgNum[5]);
  
  printf("\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[5], ChgNum[5]);
 

   for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];				//随机数列复位
  printf("\n折半排序:\n");
  
  BInsertSort(L, &CmpNum[6], &ChgNum[6]);
  
  printf("\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[6], ChgNum[6]);
 

   for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];				//随机数列复位
  printf("\n归并排序:\n");
  
  MergeSort(L, &CmpNum[7], &ChgNum[7]);
  
  printf("\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[7], ChgNum[7]);
 

  for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];				//随机数列复位
  printf("\n基数排序:\n");
  
  RadixSort(L, &CmpNum[8], &ChgNum[8]);
  
  printf("\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[8], ChgNum[8]);
 

  for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];				//随机数列复位
  printf("\n2-路插入排序:\n");
 
  InsertSortBinary(L, &CmpNum[9], &ChgNum[9]);
  
  printf("\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[9], ChgNum[9]);
 
}
void main(){
  int i,j;
  int select = 0;
  int dlta[3] = {7, 3, 1};
  int Indata[1] = {1};
  int CmpNum[12], ChgNum[12];
  LinkList L;
  InitLinkList(&L);
  Display(&L);
   FILE *f2;
  
  
  memset(CmpNum, 0, sizeof(CmpNum));
  memset(ChgNum, 0, sizeof(ChgNum));
  do{
    SelectSort();
    for (i = 0; i < MAXSIZE; i++)
      L.r[i].key = RandArray[i];				//随机数列复位
    scanf("%d", &select);
    switch (select){
      case 1:
        printf("\n插入排序:\n");
		
        ShellSort(&L, Indata, 1, &CmpNum[select], &ChgNum[select]);
        if ((f2 = fopen("Output.txt", "a")) == NULL)
		{
    printf("can't open file\n");
    exit(0);
		}
		for(i=1;i<=MAXSIZE;i++){
			printf("%5d ",L.r[i].key);
             
			if(++j%10==0)printf("\n");
		}
        printf("\n\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[select],ChgNum[select]);
      fprintf(f2, "\n插入排序 CompareNumber=%d\tChageNumber=%d\n", CmpNum[select], ChgNum[select]);
        fclose(f2);
        break;
      case 2:
        printf("\n希尔排序:\n");
        
        ShellSort(&L, dlta, 3, &CmpNum[select], &ChgNum[select]);
       if ((f2 = fopen("Output.txt", "a")) == NULL){
    printf("can't open file\n");
    exit(0);
  }
   		for(i=1;i<=MAXSIZE;i++){
			printf("%5d ",L.r[i].key);
            
			if(++j%10==0)printf("\n");
		}
		printf("\n\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[select],ChgNum[select] );
         fprintf(f2, "\n希尔排序 CompareNumber=%d\tChageNumber=%d\n", CmpNum[select], ChgNum[select]);
       fclose(f2);
		break;
      case 3:
        printf("\n快速排序:\n");
        
        QuickSort(&L, &CmpNum[select], &ChgNum[select]);
        if ((f2 = fopen("Output.txt", "a")) == NULL){
    printf("can't open file\n");
    exit(0);
  }
		for(i=1;i<=MAXSIZE;i++){
			printf("%5d ",L.r[i].key);
           
			if(++j%10==0)printf("\n");
		}
        printf("\n\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[select],ChgNum[select]);
        fprintf(f2, "\n快速排序 CompareNumber=%d\tChageNumber=%d\n", CmpNum[select], ChgNum[select]);
       fclose(f2);
		break;
      case 4:
        printf("\n堆排序:\n");
        
        HeapSort(&L, &CmpNum[select], &ChgNum[select]);
        if ((f2 = fopen("Output.txt", "a")) == NULL){
    printf("can't open file\n");
    exit(0);
  }
		for(i=1;i<=MAXSIZE;i++){
			printf("%5d ",L.r[i].key);
           
			if(++j%10==0)printf("\n");
		}
        printf("\n\nCompareNumber=%d\tChageNumber=%d\n",CmpNum[select], ChgNum[select]);
       fprintf(f2, "\n堆排序 CompareNumber=%d\tChageNumber=%d\n", CmpNum[select], ChgNum[select]);
       fclose(f2);
		break;
      case 5:
        printf("\n冒泡排序:\n");
        
        BubbleSort(&L, &CmpNum[select], &ChgNum[select]);
        if ((f2 = fopen("Output.txt", "a")) == NULL){
    printf("can't open file\n");
    exit(0);
  }
		for(i=1;i<=MAXSIZE;i++){
			printf("%5d ",L.r[i].key);
           
			if(++j%10==0)printf("\n");
		}
        printf("\n\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[select],ChgNum[select]);
       fprintf(f2, "\n冒泡排序 CompareNumber=%d\tChageNumber=%d\n", CmpNum[select], ChgNum[select]);
       fclose(f2);
		break;
      case 6:
        printf("\n选择排序:\n");
        
        SelSort(&L, &CmpNum[select], &ChgNum[select]);
        if ((f2 = fopen("Output.txt", "a")) == NULL){
    printf("can't open file\n");
    exit(0);
  }
		for(i=1;i<=MAXSIZE;i++){
			printf("%5d ",L.r[i].key);
           
			if(++j%10==0)printf("\n");
		}
        printf("\n\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[select],ChgNum[select]);
        fprintf(f2, "\n选择排序 CompareNumber=%d\tChageNumber=%d\n", CmpNum[select], ChgNum[select]);
       fclose(f2);
		break;
      case 7:
        printf("\n折半排序:\n");
        
        BInsertSort(&L,&CmpNum[select], &ChgNum[select]);
        if ((f2 = fopen("Output.txt", "a")) == NULL){
    printf("can't open file\n");
    exit(0);
  }
		for(i=1;i<=MAXSIZE;i++){
			printf("%5d ",L.r[i].key);
           
			if(++j%10==0)printf("\n");
		}
        printf("\n\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[select],ChgNum[select]);
       fprintf(f2, "\n折半排序 CompareNumber=%d\tChageNumber=%d\n", CmpNum[select], ChgNum[select]);
      fclose(f2);
		break;
       case 8:
        printf("\n归并排序:\n");
        
        MergeSort(&L,&CmpNum[select],&ChgNum[select]);
        if ((f2 = fopen("Output.txt", "a")) == NULL){
    printf("can't open file\n");
    exit(0);
  }
		for(i=1;i<=MAXSIZE;i++){
			printf("%5d ",L.r[i].key);
          
			if(++j%10==0)printf("\n");
		}
        printf("\n\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[select],ChgNum[select]);
        fprintf(f2, "\n归并排序 CompareNumber=%d\tChageNumber=%d\n", CmpNum[select], ChgNum[select]);
       fclose(f2);
		break;
       case 9:
        printf("\n基数排序:\n");
        
        RadixSort(&L,&CmpNum[select], &ChgNum[select]);
         if ((f2 = fopen("Output.txt", "a")) == NULL){
          printf("can't open file\n");
         exit(0);
		 }
		   	for(i=1;i<=MAXSIZE;i++){
			printf("%5d ",L.r[i].key);
           
			if(++j%10==0)printf("\n");
		}
        printf("\n\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[select],ChgNum[select]);
        fprintf(f2, "\n基数排序 CompareNumber=%d\tChageNumber=%d\n", CmpNum[select], ChgNum[select]);
        fclose(f2);
        break;
     case 10:
        printf("\n2-路插入排序:\n");
        
        InsertSortBinary(&L, &CmpNum[select], &ChgNum[select]);
        if ((f2 = fopen("Output.txt", "a")) == NULL){
    printf("can't open file\n");
    exit(0);
  }
   		for(i=1;i<=MAXSIZE;i++){
			printf("%5d ",L.r[i].key);
           
			if(++j%10==0)printf("\n");
		}
		printf("\n\nCompareNumber=%d\tChageNumber=%d\n", CmpNum[select],ChgNum[select]);
         fprintf(f2, "\n2-路插入排序 CompareNumber=%d\tChageNumber=%d\n", CmpNum[select], ChgNum[select]);
       fclose(f2);
		break;
     case 11:
        AllAbove(&L, CmpNum, ChgNum);
        break;
 
    }
  }
 
  while (select != 12 );
  Display(&L);
}