C语言常见的几个排序

时间：2010-10-11 来源：huabinbin00

#include "stdio.h" void insersoft(int ch[],int len) //插入排序
{
   int i,j,temp;
   for(i = 1; i < len; i++)
   {
     temp = ch[i];
     j = i-1;
while(j>=0 && temp<ch[j])
{
     ch[j+1] = ch[j];
     ch[j] = temp;
  j--;
}
   }
} void half_soft(int ch[],int len)    //二分法排序
{
int low=0;
int high ;
int mid,i,j,temp;
for(i = 1; i < len; i++)     //一个一个的插入
{
       low = 0;
    high = i-1;
    temp = ch[i];         //找到要插入的位置low
    while(low <= high)
    {
    mid = (low +high)/2;
    if(temp > ch[mid])
    low = mid +1;
    else
    high = mid -1;
    }
       for(j = i-1; j >=low; j--)
    {
       ch[j+1] = ch[j];   //往后挪一个位置
    }
    ch[low] = temp;
}
}
void selectsoft(int ch[], int len)   //选择排序
{
int i,j,temp;
for(i = 0; i < len-1; i++)
   for(j = i+1; j < len; j++)
   {
       if(ch[i] > ch[j])   //选择小的数据往前放
    {
       temp = ch[j];
    ch[j] = ch[i];
    ch[i] = temp;
    }
   }
}
void maopaosoft(int ch[], int len)   //冒泡排序
{
   int i,j,temp;
   for(i = 0; i < len; i++)
     for(j= 0; j < len-i-1; j++)
{
   if(ch[j] > ch[j+1])   //选择大的数据往后放
   {
      temp = ch[j];
   ch[j] = ch[j+1];
   ch[j+1] = temp;

   }
}
} //快速排序方法1
void quicksoft(int ch[], int low, int high)   //快速排序
{
    int i,j,temp;
i = low;
j = high;
temp = ch[low]; // 暂时作为基准点
while(i < j)
{
    while((i < j) && (temp < ch[j])) //在右边的只要比基点的大仍在右边
    {
     j--;   //向前移一位
    }
    if(i < j)   //出现比基准点小的数，替换基准点的数
    {
       ch[i] = ch[j];
    i++;   //右移一位
    }
       while((i < j) && (temp > ch[i])) //在左边的只要比基点的小仍在左边
    {
     i++; //右移一位
    }
    if(i < j)   //出现比基准点大的数，填入原先比基点小的数的位置即j
    {
    ch[j] = ch[i];
    j--;
    }
}
ch[i] = temp; if(low < i-1)
{
    quicksoft(ch,low,i-1);    //前半部分在做快速排序
}

if(j+1 < high)
{
     quicksoft(ch,i+1,high);    //后半部分在做快速排序
}
} //快速排序方法2
void quick_soft(int ch[], int left, int right)
{
int pos,temp,swap;
int i = 0;
pos = left;
temp = ch[pos]; for(i = 1; i <= right; i++)
{
     if(ch[i] < temp)
{
    pos++;
       swap = ch[pos];
    ch[pos] = ch[i];
    ch[i] = swap;
}
}
swap = ch[pos];
ch[pos] = ch[0];
ch[0] = swap;
    if(left < pos-1)
    {
   quick_soft(ch,left,pos-1);    //前半部分在做快速排序
    }

    if(pos+1 < right)
    {
   quick_soft(ch,pos+1,right);    //后半部分在做快速排序
    }

}
void shell_soft(int ch[], int len) //希尔排序
{
   int h,j,k,temp;
   for(h = len/2; h > 0; h = h/2) //控制增量
   {
      for(j = h; j < len;j++)      //相当于分组
   {
     temp = ch[j];
  for(k = j-h;(k>=0 && temp < ch[k]); k -= h) //对分组的数据进行排序
  {
     ch[k+h] = ch[k];
  }
     ch[k+h] = temp;   //这里k=k-h 就是交换
   }
   }
}
void main()
{
    int ch[10];
int i,num,temp,l;
puts("输入多少个数字：");
scanf("%d",&num);
puts("请输入一组数字：");
for(i = 0; i <num; i++)
{
  scanf("%d",&ch[i]);
}
//insersoft(ch,num);
//half_soft(ch,num);
//selectsoft(ch,num);
//maopaosoft(ch,num);
//quicksoft(ch,0,num-1);
//shell_soft(ch,num);
quick_soft(ch,0,num-1);
puts("排序结果为：");
for(i = 0; i <num; i++)
{
  printf("%5d",ch[i]);
}
printf("\n");
}