气泡排序 (C)
常用的排序方法有冒泡排序法,选择排序法,插入排序法以及希尔排序法等。本文着重讲解如何利用C代码,实现冒泡排序。
首先,要了解什么是冒泡排序。冒泡排序是常用的一种排序方法,其基本方法就是逐次比较。即一次比较两个数,若它们的顺序错误,则它们交换;重复进行,直到没有需要交换为止。
以升序排序为例:
1、比较相邻数字的大小,若第一个数比第二个数大,则相互交换;
2、对每一对相邻的数作相同的工作,那么最后的数应该是最大的数;
3、针对所有数(除了最后一个)重复上述步骤,直到没有任何一对数字需要比较为止。
需要注意的是,第3条中所谓的“最后一个”是指前几步中已经处理过的最大的数,而不是整个数列的最后一个数。
例如,将下列数列用冒泡排序法从小到大重新排列;
49 38 65 97 76 13 27 49
每次排序后数列的变化如下:
第一趟排序:38 49 65 76 13 27 49 97
第二趟排序:38 49 65 13 27 49 76 97
第三趟排序:38 49 13 27 49 65 76 97
第四趟排序:38 13 27 49 49 65 76 97
:
:
:
经过一系列过程,最终数列次序为:13 27 3849 49 65 76 97.
通过对以上排序的分析,我们可以简要画出冒泡排序的流程图:
观察流程图,我们不难发现通过一个简单的循环结构,即可实现对一组数进行排序。
部分程序如下:
#include <stdio.h>
int main ()
{
int i, j,temp;
int array[n];
for (i = 0;i <8; i++)
{
scanf ("%d",&array[i]); //通过数组和循环输需要排序的数列
}
printf ("Before ordering,the rank is : ");
for (i = 0;i < 8 ; i++)
{
printf ("%d ",array[i]);
}
printf (" "); //显示排序之前的数组
for (j = 0;j < n-1; j++)
{
for(i = 0;i < n-j-1; i++) //两次循环实现排序
{
if (array[i] > array[i+1]) //相邻两数字比较
{
temp = array[i];
array[i] = array[i+1];
array[i+1] = temp; //中间变量temp实现相邻元素的交换
}
}
}
printf ("After ordering,the rank is :");
for(i = 0;i < n ; i++)
{
printf ("%d ",array[i]); //显示排序后的数组
}
printf (" ");
return 0;
}
数字的排序:
#include <stdio.h>
#define SIZE 10
int main()
{
int a[SIZE]={12 ,43,9,13,67,98,101,89,3,35};//十个数的无序数列
int i,j,t;
printf("此程序使用冒泡排序法排列无序数列! ");
//冒泡排序
for(i=0;i<10-1;i++)//n个数的数列总共扫描n-1次
{
for(j=0;j<10-i-1;j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束
{
if(a[j]>a[j+1])//后一位数比前一位数小的话,就交换两个数的位置(升序)
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
printf("排列好的数列是: ");
//输出排列好得吃数列
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
return 0;
}
字符排序:
#include <stdio.h>
#define SIZE 10
int main()
{
char a[SIZE]={'i','l','o','v','e','y','o','u','y','x'};//十个数的无序数列
int i,j;
char t;
printf("此程序使用冒泡排序法排列无序数列! ");
//冒泡排序
for(i=0;i<10-1;i++)//n个数的数列总共扫描n-1次
{
for(j=0;j<10-i-1;j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束
{
if(a[j]>a[j+1])//后一位数比前一位数小的话,就交换两个数的位置(升序)
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
printf("排列好的字符组是: ");
//输出排列好得吃数列
for(i=0;i<10;i++)
{
printf("%c ",a[i]);
}
return 0;
}
用函数来解决这个问题:
#include <stdio.h>
void function(char a[],int);//尤其注意,此处的函数声明必须是char a[],因为这里穿的是地址,不能仅仅使用char
int main()
{
int i;
char a[10]={'i','l','o','v','e','y','o','u','y','x'};//十个数的无序字符数列
printf("此程序使用冒泡排序法排列无序数列! ");
function(a,10);//调用冒泡排序
printf("排列好的字符组是: ");
//输出排列好得吃数列
for(i=0;i<10;i++)
{
printf("%c ",a[i]);
}
return 0;
}
void function(char a[],int m)
{
//冒泡排序
int i,j;
char t;
for(i=0;i<m-1;i++)//n个数的数列总共扫描n-1次
{
for(j=0;j<m-i-1;j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束
{
if(a[j]>a[j+1])//后一位数比前一位数小的话,就交换两个数的位置(升序)
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
return;
}
执行情况:
知识总结:
冒泡排序法:也叫升序排序法,但是相比起二分法查找只能应用于有序数列,二如何将一个无序数列变的有序就可以使用冒泡排序法!!!
对上面的过程进行总结:
该思想体现在成续上的解法是:
实例:
冒泡排序不仅仅可以应用于数字同样可以应用于字符字母的快速排序:
上一篇: JAVA 学习路径:11. 数组排序算法