本文共 1418 字，大约阅读时间需要 4 分钟。

终于到了“大话数据结构”最后一个章节了。当然前面的图和树还有待大量的学习和训练。

冒泡排序，应该是最简单的排序方式了，以下为其基本和改进实现：

Input number (q to quite): 5 3 1 9 4 6 3 7 9 1 6 4 3 4 qYour input List is: 5 3 1 9 4 6 3 7 9 1 6 4 3 4After bubble sort: 1 1 3 3 3 4 4 4 5 6 6 7 9 9

#include
   
    using namespace std;#define MAXSIZE 100struct List{
   	int data[MAXSIZE];	int size;};void swap(List &L, int i, int j){
   	int temp = L.data[i];	L.data[i] = L.data[j];	L.data[j] = temp;}void show(const List &L){
   	for (int i = 0; i < L.size; i++)		cout << L.data[i] << " ";	cout << endl;}void BubbleSort(List &L){
   	for (int i = 0; i < L.size-1; i++) {
   		for (int j = 0; j < L.size - i -1; j++) {
   			if (L.data[j] > L.data[j+1])				swap(L, j, j+1);		}	}}void BubbleSort2(List &L){
   	bool flag = true;	for (int i = 0; i < L.size - 1&&flag; i++) {
   		flag = false;		for (int j = 0; j < L.size - i - 1; j++) {
   			if (L.data[j] > L.data[j + 1]) {
   				swap(L, j, j + 1);				flag = true;			}		}	}}void main(){
   	List test;	cout << "Input number (q to quite): ";	int temp;	test.size = 0;	while (test.size <= MAXSIZE&&cin >> temp) {
   		test.data[test.size] = temp;		test.size += 1;		cout << "Input number (q to quite): ";	}	cin.clear();	cin.ignore(100, '\n');	cout << "Your input List is: ";	show(test);	cout << "After bubble sort: ";	BubbleSort2(test);	show(test);}
   

改进方法“BubbleSort2”，是为了优化当列表中已经是具有一定序列的情况，可以去掉已排好序的冗余判断过程。冒泡排序的时间复杂度是:

转载地址：http://tpyci.baihongyu.com/