[原创]各种排序方法总结【2008年7月7日更新】

Orz已经晕了……早饭+午饭都没吃……撑不住了……出去吃饭了回来再看…………
----------------解决方案--------------------------------------------------------
晚上来补完！！
----------------解决方案--------------------------------------------------------
我都是让同学帮带的..呵呵
----------------解决方案--------------------------------------------------------
帖子顶起再看 .！
收回去了 ,  呵呵  ,给出原创链接！
----------------解决方案--------------------------------------------------------
qsort怎么在递归中写随机划分啊（在一个函数中，不要两个函数的）？
我只会先将数组中的元素随机乱序一下，曾经试过在递归函数中写随机划分，总是有问题
----------------解决方案--------------------------------------------------------
看算法导论吧，上面好像有，不过我跳过没看....
----------------解决方案--------------------------------------------------------
我的qsort(随机乱序输入的数据，从而使之趋向于平衡）
void sort(int low,int high,int key[])
{
     int i,j,tag;
     i=low; j=high;
     if(i<j)
     {
       tag=key[i];
       do
       {
         while(tag<key[j] && i<j) j--;
         if(i<j)
         {
                key[i]=key[j];
                i++;
                while(tag>=key[i] && i<j) i++;
                if(i<j)
                {
                       key[j]=key[i];
                       j--;
                }
         }
       }while(i<j);
       key[i]=tag;
       sort(low,j-1,key);
       sort(i+1,high,key);
     }
}
int main(void)
{
    int i,tmp[3];
    int n;
    int key[200000];
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&key[i]);
    for(i=n/2;i<n;i++)
    {
      tmp[0]=((rand()<<4)+rand())%n;
      tmp[1]=((rand()<<4)+rand())%n;
      tmp[2]=key[tmp[0]];
      key[tmp[0]]=key[tmp[1]];
      key[tmp[1]]=tmp[2];
    }
    sort(0,n-1,key);
    for(i=0;i<n;i++)
    {
      printf("%d ",key[i]);
    }
    printf("\n");
    return 0;
}
----------------解决方案--------------------------------------------------------
Orz....居然睡着了，一觉醒来发现十点了………………
那个，希尔我有种简单的解决方法，可以很轻松搞定。
基数按复杂度看似乎没有桶排快。而且很难写。我准备看看再说，看来我背着写也就这水平了。明天翻了算法导论再来补完。
快排的高效版的划分没头绪。我算了下，原来的想法是错误的。反而会降低效率，所以决定舍弃原来那种，改用算法导论上面的……Orz算法导论是交换为主啊……那么效率……
不管了……推到明天吧，累死了……
----------------解决方案--------------------------------------------------------
孔明啊……我想要短小精悍的划分代码……555……
----------------解决方案--------------------------------------------------------

貌似如果数据是随机的，那么我上面发的那个快排函数比大部分人写的（网上流传的）要快1/4，而且也比较简洁。
就是不知道怎么样把这个函数改成随机划分的
----------------解决方案--------------------------------------------------------