数据结构上机——双向起泡排序

相比于传统的冒泡排序
双向气泡排序做了两点优化：
1、利用flag标记有无数据交换，防止在数据有序的情况下再次浪费时间
2、每次循环，从前往后又从后往前，每次确定一个大的一个小的，大小通吃

//双向起泡排序的程序代码
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//顺序表结构类型定义
typedef int datatype;
typedef struct{
	int key;
	datatype data;
}sequenlist;

void create(sequenlist[],int);
void print(sequenlist[],int);
void dbubblesort(sequenlist[],int);

int main()
{
	const int n=10;
	sequenlist r[n+1];
	create(r,n);
	printf("排序前的数据：");
	print(r,n);
	dbubblesort(r,n);
	printf("排序后的数据：");
	print(r,n);
}

//建立顺序表
void create(sequenlist r[],int n)
{
	srand(time(0));
	for(int i=1;i<=n;i++)
		r[i].key=rand()%90;
}

//输出顺序表
void print(sequenlist r[],int n)
{
	for(int i=1;i<=n;i++)
		printf("%5d",r[i].key);
	printf("\n");
}

//添加双向起泡排序算法
void dbubblesort(sequenlist r[],int n)
{
	int low=1,high=n,flag,i,temp;
	while (low<high)
	{
		flag=0;//flag标记有无数据交换 
		for(i=low;i<high;i++)
		{
			if(r[i].key>r[i+1].key)
			{
				temp=r[i].key;
				r[i].key=r[i+1].key;
				r[i+1].key=temp;
				flag=1;
			}	
		}
		if(flag==0)break;
		high--;
		for(i=high;i>low;i--)
		{
			if(r[i].key<r[i-1].key)
			{
				temp=r[i].key;
				r[i].key=r[i-1].key;
				r[i-1].key=temp;
			} 
		}
		low++; 
	}
}






  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
 

文章来源: zstar.blog.csdn.net，作者：zstar-_，版权归原作者所有，如需转载，请联系作者。

原文链接：zstar.blog.csdn.net/article/details/111305563