交换排序的基本思想是:两两比较待排序记录的关键字,并交换不满足顺序要求的记录对,直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序。文章给出用C语言实现冒泡排序算法的源代码,在Vc++6.0环境中调试通过,并提供下载源码文本。
冒泡排序的具体过程如下:
第一步,先比较k1和k2,若k1>k2,则交换k1和k2所在的记录,否则不交换。继续对k2和k3重复上述过程,直到处理完kn-1和kn。这时最大的排序码记录转到了最后位置,称第1次起泡,共执行n-1次比较。
与第一步类似,从k1和k2开始比较,到kn-2和kn-1为止,共执行n-2次比较。
依次类推,共做n-1次起泡,完成整个排序过程。
若文件的初始状态是正序的,一趟扫描即可完成排序。所需关键字比较次数为n-1次,记录移动次数为0。因此,冒泡排序最好的时间复杂度为O(n)。
若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1<=i<=n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较次数达到最大值n(n-1)/2=O(n^2),移动次数也达到最大值3n(n-1)/2=O(n^2)。因此,冒泡排序的最坏时间复杂度为O(n^2)。
虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均性能比直接插入排序要差得多。冒泡排序是就地排序,且它是稳定的。
用C语言实现的冒泡排序算法如下:
// bubbleSort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#define N 6;
void bubble(int A[],int n) //冒泡排序
{
int t;
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++) //注意在内层循环中j的结束值是 n-i-1,否则出错
{
if(A[j+1]<A[j])
{
t=A[j];
A[j]=A[j+1];
A[j+1]=t;
}
}
}
}
int main(int argc, char* argv[])
{
int i,k,n;
n=N;
int array[6];
printf("bubble sort algorithom ,array N=6 : ");
for(i=0;i<n;i++)
{
printf("please input array[%d] value: ",i);
scanf("%d",&k);
array[i]=k;
}
//打印排序前内容
printf("current array value: ");
for(i=0;i<n;i++)
{
printf("%d ",array[i]);
}
printf(" ");
//排序
bubble(array,n) ;
//打印排序后内容
printf("sorted array value: ");
for(i=0;i<n;i++)
{
printf("%d ",array[i]);
}
printf(" ");
return 0;
}
参考:常用排序算法总结 http://www.programfan.com/club/showtxt.asp?id=202195