才子佳人博客

我的故事我讲述

用C语言实现冒泡排序算法的源代码(调试通过)
 
来源:xjh  编辑:xjh  2018-10-23

交换排序的基本思想是:两两比较待排序记录的关键字,并交换不满足顺序要求的记录对,直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序。文章给出用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语言实现的冒泡排序算法源代码.cpp

用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



分类:编程开发| 查看评论
相关文章
文章点击排行
本年度文章点击排行
发表评论:
  • 昵称: *
  • 邮箱: *
  • 网址:
  • 评论:(最多100字)
  • 验证码: