冒泡排序：
/*
================================================
功能：冒泡排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上
而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较
小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要
求相反时，就将它们互换。
下面是一种改进的冒泡算法，它记录了每一遍扫描后最后下沉数的
位置k，这样可以减少外层循环扫描的次数。
冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void bubble_sort(int *x,int n)
{
int j,k,h,t;
for (h=n-1; h>0; h=k) /*循环到没有比较范围*/
{
for (j=0,k=0; j<h; j++) /*每次预置k=0，循环扫描后更新k*/
{
if (*(x+j) > *(x+j+1)) /*大的放在后面，小的放到前面*/
{
t = *(x+j);
*(x+j) = *(x+j+1);
*(x+j+1) = t; /*完成交换*/
k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
}
}
}
}
例：
//利用冒泡排序法对输入的10个整数从小到大排序，显示出每步的排序过程，打印最终结果
//采用一维数组表示这10个数
#include "stdio.h"
#define N 10
int main() {
int i,j,temp;
int a[N+1];
int count = 0;// 记数器，记录是第几趟排序
printf( " Please enter %d date: n",N );
for (i = 1; i <= N; i++)
scanf( " %d",&a[i]);
printf( "************************n");
for (i = 1; i <= N; i++) {
count++;//第记录一趟，计数器加１
for ( j=1; j<=N; j++) {//若相邻两数 左边 大于 右边 则交换
if (a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; }
}
//打印第几趟和本趟排序结果
printf( "%3d:",count);
for (j = 1; j <= N; j++)
printf( "%d ",a[j]); printf( " n ");
}
//打印最终的排序结果
printf( " The result is :");
for (i = 1; i <= 10; i++);
printf( "%d",a[i]);
return 0;
}
改进后的冒泡排序：
//设置一个标志flag，一旦发现在某趟无需交换数据，即提前跳出循环，终止排序，修改后的程序如下：
#include "stdio.h"
#define N 10
int main() {
int i,temp;
int a[N+1];
int count=0;
int flag;
printf( " Please enter %d date: n",N );
for( i=1; i<=N; i++)
scanf( " %d",&a[i]);
printf( "************************n");
flag=1;//默认整个排序过程有交换
for( i=1; i<=N&&flag; i++) {
flag=0;
for( j=1; j<=N; j++) {
if(a[j]>a[j+1]) {
flag=1;//当前趟有交换
temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; }
}
if(flag) {//判断是否需打印呢？
count++;
printf( "%3d:",count);
for( j=1; j<=N; j++)
printf( "%d ",a[j]); printf( " n ");
}
}
//打印最终的排序结果
printf( " The result is :");
for( i=1; i<=10; i++);
printf( "%dn",a[i]);
return 0;
}
编程风格思考： １、输入、输出的人性化。良好的提示、错误提醒…… ２、方法的可扩展性？自定义数组（数据个数、类型）排序 ３、测试用例 （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
