数据结构之排序（二）—— 冒泡排序

冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：俩俩比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

最简单排序实现

原理

让每一个关键字，都和它后面的每一个关键字比较，如果大则交换，直到结束。如图：

算法

#include "stdafx.h"
using namespace std;
#include<iostream>
#include"stdafx.h"
//用于要排序数组个数最大值，可根据需要修改  
#define MAXSIZE 10  
typedef struct
{
	//用于存储要排序数组，r[0]用作哨兵或临时变量  
	int r[MAXSIZE + 1];
	//用于记录顺序表的长度  
	int length;
}SqList;
//交换L中数组r的下标为i和j的值  
void swap(SqList *L, int i, int j) {
	int temp = L->r[i];
	L->r[i] = L->r[j];
	L->r[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->r[i]>L->r[j]) {
				//交换L->r[i]与L->r[j]的值  
				swap(L, i, j);
			}
		}
	}
}
#define N 9
int main()
{
	int d[N] = { 9,1,5,8,3,7,4,6,2 };
	SqList L0;
	for (int i = 0; i < N; i++) {
		L0.r[i + 1] = d[i];
	}
	L0.length = N;
	cout<< "排序前:";
	for (int j = 1; j <= L0.length; j++) {
		cout<< L0.r[j];
	}
	BubbleSort0(&L0);
	cout << "\n初级冒泡排序:";
	for (int j = 1; j <= L0.length; j++) {
		cout << L0.r[j];
	}
	cout << endl;
	return 0;
}

运行结果

冒泡排序算法

原理

俩俩比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。如图：

算法

#include "stdafx.h"
using namespace std;
#include<iostream>
#include"stdafx.h"
//用于要排序数组个数最大值，可根据需要修改  
#define MAXSIZE 10  
typedef struct
{
	//用于存储要排序数组，r[0]用作哨兵或临时变量  
	int r[MAXSIZE + 1];
	//用于记录顺序表的长度  
	int length;
}SqList;
//交换L中数组r的下标为i和j的值  
void swap(SqList *L, int i, int j) {
	int temp = L->r[i];
	L->r[i] = L->r[j];
	L->r[j] = temp;
}
//对顺序表L作交换排序（冒泡排序版）  
void BubbleSort(SqList *L) {
	int i, j;
	for (i = 1; i<L->length; i++) {
		//注意j是从后往前循环
		for (j = L->length-1 ; j >=i; j--) {
			//若前者大于后者
			if (L->r[j]>L->r[j+1]) {
				//交换L->r[j]与L->r[j+1]的值  
				swap(L, j, j+1);
			}
		}
	}
}
#define N 9
int main()
{
	int d[N] = { 9,1,5,8,3,7,4,6,2 };
	SqList L0;
	for (int i = 0; i < N; i++) {
		L0.r[i + 1] = d[i];
	}
	L0.length = N;
	cout<< "排序前:";
	for (int j = 1; j <= L0.length; j++) {
		cout<< L0.r[j];
	}
	BubbleSort(&L0);
	cout << "\n冒泡排序后:";
	for (int j = 1; j <= L0.length; j++) {
		cout << L0.r[j];
	}
	cout << endl;
	return 0;
}

运行结果

冒泡排序优化

原理

增加一个标记变量flag来实现冒泡算法的改进。可以避免因已经有序的情况下的无意义循环判断。

算法

#include "stdafx.h"
using namespace std;
#include<iostream>
#include"stdafx.h"
//用于要排序数组个数最大值，可根据需要修改  
#define MAXSIZE 10  
typedef struct
{
	//用于存储要排序数组，r[0]用作哨兵或临时变量  
	int r[MAXSIZE + 1];
	//用于记录顺序表的长度  
	int length;
}SqList;
//交换L中数组r的下标为i和j的值  
void swap(SqList *L, int i, int j) {
	int temp = L->r[i];
	L->r[i] = L->r[j];
	L->r[j] = temp;
}
//对顺序表L作交换排序（优化的冒泡排序版）  
void BubbleSort(SqList *L) {
	int i, j;
	//flag用来作为标记
	bool flag = true;
	//若flag为true则退出退出循环
	for (i = 1; i<L->length&&flag; i++) {
		//初始为false
		flag = false;
		//注意j是从后往前循环
		for (j = L->length-1 ; j >=i; j--) {
			//若前者大于后者
			if (L->r[j]>L->r[j+1]) {
				//交换L->r[j]与L->r[j+1]的值  
				swap(L, j, j+1);
				//如果有数据交换，则flag为true
				flag = true;
			}
		}
	}
}
#define N 9
int main()
{
	int d[N] = { 9,1,5,8,3,7,4,6,2 };
	SqList L0;
	for (int i = 0; i < N; i++) {
		L0.r[i + 1] = d[i];
	}
	L0.length = N;
	cout<< "排序前:";
	for (int j = 1; j <= L0.length; j++) {
		cout<< L0.r[j];
	}
	BubbleSort(&L0);
	cout << "\n优化后的冒泡排序后:";
	for (int j = 1; j <= L0.length; j++) {
		cout << L0.r[j];
	}
	cout << endl;
	return 0;
}

运行结果

冒泡排序复杂度分析

冒泡排序时间复杂度为O（n^2）

算法稳定性

稳定