《数据结构》练级-冒泡排序

前端之家收集整理的这篇文章主要介绍了《数据结构》练级-冒泡排序前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

冒泡排序:

/*  
================================================  
 功能:冒泡排序  
 输入:数组名称(也就是数组首地址)、数组中元素个数  
================================================  
*/  
/*  
====================================================  
算法思想简单描述:  
  
 在要排序的一组数中,对当前还未排好序的范围内的全部数,自上  
 而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较  
 小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要  
 求相反时,就将它们互换。  
    
 下面是一种改进的冒泡算法,它记录了每一遍扫描后最后下沉数的  
 位置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++;//第记录一趟,计数器加1
		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( "%d\n",a[i]);

	return 0;
}

编程风格思考:

1、输入、输出的人性化。良好的提示错误提醒…… 2、方法的可扩展性?自定义数组(数据个数、类型)排序 3、测试用例 原文链接:https://www.f2er.com/datastructure/383230.html

猜你在找的数据结构相关文章