很多朋友是以谭浩强老师编的《c 语言教程》作为学习c 语言的入门教程的。书中涉及排序问题一般都以“冒泡法”和“选择法”实现。为了扩大视野,增加学习编程的兴趣,我参阅了有关书籍,整理了几种排序法,写出来同大家共勉。 让我们先定义一个整型数组 a[n ],下面用五种方法对其从小到大排序。 (1)“冒泡法” 冒泡法大家都较熟悉。其原理为从 a[0]开始,依次将其和后面的元素比较,若 a[0]>a,则交换它们,一直比较到 a[n ]。同理对 a[1],a[2],...a[n -1]处理,即完成排序。下面列出其代码: C/C++ code void bubble(int *a,int n) /*定义两个参数:数组首地址与数组大小*/ { int i,j,temp; for(i=0;ia[j]) { temp=a; a=a[j]; a[j]=temp; } } 冒泡法原理简单,但其缺点是交换次数多,效率低。 下面介绍一种源自冒泡法但更有效率的方法“选择法”。 2)“选择法” 选择法循环过程与冒泡法一致,它还定义了记号 k =i,然后依次把 a[k ]同后面元素比较,若 a[k ]>a[j],则使 k =j.最后看看 k =i 是否还成立,不成立则交换 a[k ],a,这样就比冒泡法省下许多无用的交换,提高了效率。 void choise(int *a,int n) { int i,j,k,temp; for(i=0;ia[j]) k=j; /*是k总是指向最小元素*/ if(i!=k) { /*当k!=i是才交换,否则a即为最小*/ temp=a[i]; //此处也错 a[i]=a[k]; //此处也错 a[k]=temp; } } } 选择法比冒泡法效率更高,但说到高效率,非“快速法”莫属,现在就让我们来了解它。 (3)“快速法” 快速法定义了三个参数,(数组首地址*a,要排序数组起始元素下标 i,要排序数组结束元素下标 j). 它首先选一个数组元素(一般为a[(i+j)/2],即中间元素)作为参照,把比它小的元素放到它的左边,比它大的放在右边。然后运用递归,在将它左,右两个子数组排序,最后完成整个数组的排序。下面分析其代码: C/C++ code void quick(int *a,int i,int j) { int m,n,temp; int k; m=i; n=j; k=a[(i+j)/2]; /*选取的参照*/ do { while(a--k && n>i) n--; /* 从右到左找比k小的元素*/ if(m<=n) { /*若找到且满足条件,则交换*/ temp=a--; a-=a[n]; a[n]=temp; m++...