paixu.txt

数据结构各种排序：直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序！C环境实现

对常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、希尔排序、堆排序。
对结果进行简单的分析。
源程序：
#include<stdio.h> 
#include<conio.h>

//////直接插入排序
void InsertSort(int a[],int n)
{ 
int i,j,k=1; 
for(i=2;i<=n;i++) 
{ if(a[i]<a[i-1]) 
     { 
      a[0]=a[i]; 
      a[i]=a[i-1]; 
      for(j=i-2;a[0]<a[j];j--)
   a[j+1]=a[j];
      a[j+1]=a[0];}
     printf("\n第%d趟结果为:",i-1);
   for(k=1;k<=n;k++) 
printf(" %d",a[k]);
}
}

//////折半插入排序
void Binsort(int a[],int n)   
{ int i,j,low,high,mid,k;
   for (i=2;i<=n;i++) 
   { a[0]=a[i];   
      low=1; high=i-1;
      while (low<=high)   
       { mid=(low+high)/2;
          if (a[0]>=a[mid])   low=mid+1;   
            else    high=mid-1; 
        }
      for (j=i-1;j>=low;j--)
       a[j+1]=a[j];   
      a[low]=a[0];   
   printf("\n第%d趟结果为:",i-1);
   for(k=1;k<=n;k++) 
printf(" %d",a[k]);
} 
}

//////希尔排序
void Shellsort (int a[],int n) 
{ int i,j,d=n/2,k=1,t; 
     while (d>=1)
      { for (i=d+1;i<=n;i++) 
           { a[0]=a[i]; j=i-d;
              while ((j>0)&&(a[0]<a[j]))
               { a[j+d]=a[j]; 
                  j=j-d;

   }
              a[j+d]=a[0]; 
     
}
         d=d/2; 
printf("\n第%d趟结果为:",k);
   for(t=1;t<=n;t++) 
printf(" %d",a[t]);
    k++;
     }
}

//////冒泡排序
void Bubsort(int a[],int n)
{ int i,j,flag,temp,k;
for (i=n;i>=2;i--)
{ flag=0;
    for (j=1;j<=i-1;j++) 
      if (a[j]>a[j+1]) 
      { temp=a[j]; 
        a[j]=a[j+1];
        a[j+1]=temp;
        flag=1;
      }
    if (flag==0) break; 
printf("\n第%d趟结果为:",n-i+1);
   for(k=1;k<=n;k++) 
printf(" %d",a[k]);
}
}


//////快速排序
void QuickSort(int a[],int left,int right)
{
   int i,j,temp,k;
   i=left;
   j=right;
   temp=a[left];
   if(left>right)
      return;
   while(i!=j)/*找到最终位置*/
   {
      while(a[j]>=temp && j>i)
         j--;
      if(j>i)
         a[i++]=a[j];
       while(a[i]<=temp && j>i)
          i++;
       if(j>i)
      a[j--]=a[i]; 
   printf("\n本趟排序结果为:");
   for(k=1;k<=right;k++) 
printf(" %d",a[k]);

   }
   a[i]=temp;

   QuickSort(a,left,i-1);/*递归左边*/
   QuickSort(a,i+1,right);/*递归右边*/
}


///////简单选择排序
void Slectsort(int a[],int n)   
{ int i,j,k,temp,t=1,p;
   for (i=1;i<n;i++)   
   { j=i;      
      for (k=i+1;k<=n;k++) 
       if (a[k]<a[j]) j=k;
      if (i!=j) 
       { 
       temp=a[i];   a[i]=a[j]; a[j]=temp; 
      
   printf("\n第%d趟结果为:",t);
   for(p=1;p<=n;p++) 
    printf(" %d",a[p]);
   }
   t++;
   }
}



void Print(int a[],int n) 
{ 
int i; 
for(i=1;i<=n;i++) 
printf(" %d",a[i]); 
printf(" \n");
}

int main(int argc, char* argv[])
{
int n,i; 
int left=1;
int right;
int a[100]; 
char ch='1';
loop:
printf("\n请输入共有几个数据参加排序(最多为100个):");
scanf("%d",&n);
right=n;
printf("请随机输入%d个数据:\n",n);
for(i=1;i<=n;i++) 
   scanf("%d",&a[i]); 
printf("\n请选择需要的排序操作:\n");
printf("                     1.直接插入排序\n");
printf("                     2.折半插入排序\n");
printf("                     3.希尔排序\n");
printf("                     4.冒泡排序\n");
printf("                     5.快速排序\n");
printf("                     6.简单选择排序\n");
ch=getch();
   if((ch!='1')&&(ch!='2')&&(ch!='3')&&(ch!='4')&&(ch!='5')&&(ch!='6'))
    {
     printf("请输入1,2,3,4,5,6\n");
     ch=getch();
    }
switch(ch)
{
    case '1':
            InsertSort(a,n);
        printf("\n直接插入排序的最后排序结果为:");
        Print(a,n); 
goto loop;break; 
    case '2':
            Binsort(a,n);
        printf("\n折半插入排序的最后排序结果为:"); 
        Print(a,n); 
goto loop;break;
    case '3':
           Shellsort (a,n);
        printf("\n希尔排序的最后排序结果为:");
        Print(a,n); 
goto loop;break;
    case '4': 
            Bubsort(a,n);
        printf("\n冒泡排序的最后排序结果为:");
        Print(a,n);
goto loop;break;      
    case '5': 
      QuickSort(a,left,right);
        printf("\n快速排序的最后排序结果为:");
       Print(a,n); 
    goto loop;break;
    case '6':
          Slectsort(a,n); 
        printf("\n简单选择排序的最后排序结果为:");
        Print(a,n); 
goto loop;break;
}
}