文档介绍：c 语言数组五种排序法: bubble,choise,quick,insert,shell 和 js 数组排序 sort 的区别
( 1) " 冒泡法 "
冒泡法大家都较熟悉。 其原理为从 a[0] 开始, 依次将其和后面的元素比较 ,若 a[0]>a[i] ,则交
换它们,一直比较到 a[n] 。同理对 a[1],a[2],...a[n-1] 处理,即完成排序。下面列出其代码:
void bubble(int *a,int n) /* 定义两个参数:数组首地址与数组大小 */
{
int i,j,temp;
for(i=0;i< n-1 ;i++)
for(j=i+1;j< n ;j++) /* 注意循环的上下限 */
if(a[i]>a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
冒泡法原理简单,但其缺点是 交换次数多,效率低 。
下面介绍一种源自冒泡法但更有效率的方法 " 选择法 "。
( 2) " 选择法 "
选择法循环过程与冒泡法一致,它还定义了记号 k=i, 然后依次把 a[k] 同后面元素比较,若
a[k]>a[j], 则使 k=j. 最后看看 k=i 是否还成立,不成立则交换 a[k],a[i], 这样就比冒泡法省下许
多无用的交换,提高了效率。
void choise(int *a,int n)
{
int i,j,k,temp;
for(i=0;i<n-1;i++) {
k=i; /* 给记号赋值 */
for(j=i+1;j<n;j++)
if(a[k]>a[j]) k=j; /* 是 k 总是指向最小元素 */
if(i!=k) { /* 当 k!=i 是才交换,否则 a[i] 即为最小 */
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
选择法比冒泡法效率更高,但说到高效率,非 "快速法 "莫属,现在就让我们来了解它。
( 3) " 快速法 "
快速法定义了三个参数, (数组首地址 *a, 要排序数组起始元素下标 i,要排序数组结束元素下
标 j). 它首先选一个数组元素(一般为 a[(i+j)/2], 即中间元素)作为参照,把比它小的元素放
到它的左边,比它大的放在右边。然后运用递归,在将它左,右两个子数组排序,最后完成
整个数组的排序。下面分析其代码:
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[m]<k&&m<j) m++; /* 从左到右找比 k 大的元素 */
while(a[n]>k&&n>i) n--; /* 从右到左找比 k 小的元素 */
if(m<=n) { /* 若找到且满足条件,则交换 */
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(m<j) quick(a,m,j); /* 运用递归 */
if(n>i) quick(a,i,n);
}
( 4) " 插入法 "