冒泡排序（C语言版）

关于冒泡排序，相信大家无论学习哪种学习语言，在学到循环和数组的时候肯定都会接触到这个最基本的排序算法。为什么这种算法要叫做冒泡排序呢？是因为这个排序算法有点像水泡向上冒，所以叫做冒泡排序。

 

冒泡排序的定义： 一种交换排序，他的基本思想是：两两比较相邻记录的关键字，如果反序则排序，知道没有反序的记录为止。

 

在下面的代码中，我给出了三种冒泡排序，分别是最原始的冒泡排序，正宗的冒泡排序和改善过后的冒泡排序，当然改善方法不是我自己想的，是来自于程杰的《大话数据结构》，在此对程杰老师表示感谢，让我更好的入门，当然我这不是卖广告哈，呵呵，好吧，直接给出代码：

#include<stdio.h>
#include <stdlib.h>
#include <time.h> 

#define TRUE 1
#define FALSE 0
#define MAXSIZE 9
#define  random(x) (rand()%x)
 
typedef int ElemType, Status;	

typedef struct {	//定义一个线性表的顺序存储结构 
	ElemType data[MAXSIZE];
	int length;
}SqList;

/*将顺序表L中的i和j两个位置进行交换*/
void swap(SqList *L, int i, int j){
	ElemType temp = L->data[i];
	L->data[i] = L->data[j];
	L->data[j] = temp;
} 

/*
	对顺序表L做交换排序（冒泡排序初级版） 
	该初级版本排序的思想是，把每个数字与排在他后面的每个数字进行比较
	通过对比发现如果后面的数字比他小，则交换 
	这个算法的效率是非常低的，但是却是最容易理解并写出的排序代码 
*/
void BubbleSort0(SqList *L) {
	int i, j;
	for(i = 1; i < L->length; i++) {
	
		for(j = i + 1; j < L->length; j++) {
			if(L->data[i] > L->data[j]) {	//若前者大于后者， 
				swap(L,i, j);	//交换L->r[i]与L->r[j] 
			
			}
		}
	}
} 

/*
	正宗的冒泡排序法 
*/
void BubbleSort(SqList *L){
	int i, j;
	for(i = 1; i < L->length; i++) {
		for(j = L->length - 1; j >= i; j--) {	//j是从后往前循环的 
			if(L->data[j] < L->data[j - 1]) {
				swap(L, j, j - 1);
			}
		}
	} 
}

/*
	改良后的冒泡排序 
	加了个标记 flag，避免了因有序的情况下的无意义循环判断 
*/
void BubbleSort2(SqList *L){
	int i, j;
	Status flag = TRUE;	//用来做标记 
	for(i = 1; i < L->length & flag; i++) {
		flag = FALSE; 
		for(j = L->length - 1; j >= i; j--) {	//j是从后往前循环的 
			if(L->data[j] < L->data[j - 1]) {
				swap(L, j, j - 1);
				flag = TRUE;
			}
		}
	} 
}

/*将列表中的数据进行展示*/
void display(SqList	L) {
	int i;
	for(i = 0; i <L.length; i++) {
		printf("%d ", L.data[i]);
	}
	printf("\n");
}
int main() {
    srand((int)time(NULL));	//用当前的时间作为随机数种子，这样就能保证每次运行时都能取到不同的随机数序列
    
	SqList s;
	int i = 0;
	s.length = 0;
	for(i; i < MAXSIZE; i++) {	//创建一个原始栈并为其赋值 
		s.data[i] = random(MAXSIZE);
		s.length++;	
	}
	printf("数组的长度 ： %d\n原始数组为 : ", s.length);
	display(s); 
//	BubbleSort0(&s);
//	BubbleSort(&s);
	BubbleSort2(&s);
	printf("经过排序后 ：");
	display(s); 
}

 贯彻我的风格，我的测试数据都是随机生成的，只要多运行几次，就能够更完美的测试。觉得麻烦的朋友可以通过for循环多次运行。

数组的长度 ： 9
原始数组为 : 6 4 1 2 7 4 5 4 7
经过排序后 ：1 2 4 4 4 5 6 7 7
请按任意键继续. . .