数列定位：int a[10]={10,9,8,7,6,5,4,3,2,1};
要求：用C语言里的8种排序法分别对它排序（排好后是从小到大的顺序），排序的同时，统计该数据共交换了多少次才排序成功。看看用哪种方法交换的次数最少？
提示：C语言里的8种排序法分别是
     1：冒泡排序
     2：选择排序
     3：插入排序
     4：希尔排序
     5：快速排序
     6：归并排序
     7：堆排序
     8：基数排序
当然，你可以只用一种排序法写出来共交换了多少次（比如我就用冒泡排序法排出来了，也统计了冒泡排序法要用45步完成排序），这也是可以的，当然了，你如果能编出代码把8 种排序法一起编进去那就更好了。

用“冒泡排序”，俺写好了，大家可以参考下：

#include <stdio.h>
void sort(int *a,int len)

 {
   int i,j,t,z,count=0;
   for(i=0;i<len-1;i++)
     {
       for(j=0;j<len-i-1;j++)
          {
           if(a[j]>a[j+1])
              {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
              printf(" 第 %3d 次交换: ",++count);
              for(z=0;z<10;z++)
              printf("%4d ",a[z]);
              printf("\n");
              }
             
          }
     }
      printf("共交换%4d 次",count);
      printf("\n");
  }
int main(int argc, char *argv[])
{
   int a[10]={10,9,8,7,6,5,4,3,2,1};
   int i=0;
   printf("这段代码是用冒泡排序法来统计共交换了多少次。\n ");
   printf("交换前的数据： ");
   for(i=0;i<10;i++)
              printf(" %4d",a[i]);
   printf("\n");
   sort(a,10);
   printf(" 交换后的数据： ");
   for(i=0;i<10;i++)
             printf("%4d ",a[i]);
   return 0;
}

效果图：

编程的时候，请在代码里注明：用什么排序法完成的。
还有就是，如果你和别人用的同一种排序法，但是比别人用的步数少也完成排序的，也可以写下来。

你换个思路呢。你把
for(i=0;i<len-1;i++)
     {
       for(j=0;j<len-i-1;j++)
          {
           if(a[j]>a[j+1])
里面的(i=0;i<len-1;i++）改成(i=len-1;i0;i--）
(j=0;j<len-i-1;j++)同理
试试看。

用“选择排序法”写好了，排序顺序和冒泡排序顺序不一样，但是交换次数一样。都是45次。

# include "stdio.h"
# define N 10
int main()
{
    int i,j,temp,count,z;
    int a[N]={10,9,8,7,6,5,4,3,2,1};
    printf("这段代码是用选择排序法来统计共交换了多少次。\n ");
    printf("交换前的数据： ");
    for(i=0;i<N;i++)
              printf(" %4d",a[i]);
    printf("\n");
    for(i=0;i<N;i++)
    for(j=i+1;j<N;j++)
    {
        if (a[i]>a[j])
        {
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
        printf(" 第 %3d 次交换: ",++count);
        for(z=0;z<N;z++)
              printf("%4d ",a[z]);
         printf("\n");
        }
    }
    printf("共交换%4d 次",count);
    printf("\n");
    printf(" 交换后的数据： ");
    for(i=0;i<N;i++)
    printf("%5d",a[i]);
}

用“插入排序法”写好了，排序顺序和上面的不一样，但是交换次数一样。都是45次。

#include<stdio.h>
#include<malloc.h>
void InsertSorting(int a[],int len)
{   int count=0;
    for(int i=1;i<len;i++)
    {
        int k=i,z;
        int temp=a[k];
        for(int j=i-1;(j>=0)&&(a[j]>temp);j--)
        {
            a[j+1]=a[j];
            k=j;
        a[k]=temp;
        printf(" 第 %3d 次交换: ",++count);
        for(z=0;z<10;z++)
              printf("%4d ",a[z]);
         printf("\n");
         }
        
    }
    printf("共交换%4d 次",count);
}
int main(int argc, char *argv[])
{
   int a[10]={10,9,8,7,6,5,4,3,2,1};
   int i=0;
   printf("这段代码是用插入排序法来统计共交换了多少次。\n ");
   printf("交换前的数据： ");
    for(i=0;i<10;i++)
              printf(" %4d",a[i]);
    printf("\n");
   InsertSorting(a,10);
   printf(" 交换后的数据： ");
   for(i=0;i<10;i++)
             printf("%3d ",a[i]);
  return 0;
}

效果图：

不错的文章，我准备对文中提到的各种排序方法都来试试，比较一番，是不是还是45呢。

分配排序分为：桶排序和基数排序。
   桶排序和基数排序均属于分配排序。分配排序的基本思想：排序过程无须比较关键字，而是通过用额外的空间来"分配"和"收集"来实现排序，它们的时间复杂度可达到线性阶：O(n)。简言之就是：用空间换时间，所以性能与基于比较的排序才有数量级的提高！
    桶排序所需要的额外空间取决于关键字的个数，若 array[0..n - 1] 中关键字的取值范围是 0 到 m - 1 的整数，则必须设置 m 个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。
   基数排序基本思想：基数排序是对桶排序的改进和推广。如果说桶排序是一维的基于桶的排序，那么基数排序就是多维的基于桶的排序。我这么说，可能还不是太清楚。比方说：用桶排序对 [0, 30] 之间的数进行排序，那么需要 31 个桶，分配一次，收集一次，完成排序；那么基数排序则只需要 0 - 9 总共 10 个桶（即关键字为数字 0 - 9），依次进行个位和十位的分配和收集从而完成排序。

你说："可以看比较次数"。那么就以下面的冒泡排序法为例，如何查看呢？？

#include <stdio.h>

 void sort(int *a,int len)

 {
   int i=0;
   int j;
   int t;
   for(i=0;i<len-1;i++)  
     {
       for(j=0;j<len-i-1;j++)
          {
           if(a[j]>a[j+1])
              {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
             }
          }
    }
  }
int main(int argc, char *argv[])
{
   int a[10]={10,9,8,7,6,5,4,3,2,1};
   int i=0;
   sort(a,10);
   for(i=0;i<10;i++)
             printf("%d ",a[i]);
  return 0;
}

[此贴子已经被作者于2018-5-23 09:50编辑过]