c++經典排序之冒泡排序算法

c++冒泡排序算法實作

冒泡排序，是一種計算機科學領域的較簡單的排序算法。它通過周遊要排序的元素，依次比較相鄰元素的大小，如果前面的元素大于後面的元素，則交換兩個元素的位置。是以，在第一趟周遊完成時，會把最大的元素排在最末尾，第二趟周遊完成時，會把次大的元素排在倒數第二位，依次類推直到要排序的元素以升序的方式排列。由于該過程類似于魚吐的泡泡一樣向上浮，是以冒泡排序也由此得名。

接下來來看一下c++如何實作冒泡排序的。

#include <iostream>
using namespace std;
int main()
{
	int a[10] = {2,11,4,1,5,18,13,10,15,8};
	cout << "數組中的數分别是：";
	for(int i = 0;i<10;i++)
		cout << a[i] << " ";
	cout << endl;
	for(int i = 0;i<9;i++)
	{
		for(int j = 0;j<9-i;j++)
		{
			int temp = 0;		
			if(a[j]>a[j+1])//如果前面的元素大于後面的元素，則交換位置
			{
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
		cout << "第" << i << "輪排序之後：";
		for(int k =0;k<10;k++)
		{
			cout << a[k] << " ";
		}
		cout << endl;
	}
	cout << "排序之後數組如下：";
	for(int i = 0;i<10;i++)
		cout << a[i] << " ";
	cout << endl;
	return 0;
}
           

運作代碼，結果如下：

從排序的結果可以看出，從最大數，次大數…等會依次被放置在正确的位置上。當然再仔細觀察一下，可以看出在第4（從0開始算）輪排序之後，所有的資料都已經被排好序了，是以第4輪之後的所有排序都是無用功。是以這裡可以想一下，是否可以判斷資料有序時，提前結束排序呢？這種判斷的依據是什麼呢？

很顯然，當某一輪周遊完成時，沒有進行交換資料位置的操作，就可以說明資料是有序的。是以可以增加一個标志位，來記錄是否有進行資料交換。改進的冒泡排序具體實作如下：

#include <iostream>
using namespace std;
int main()
{
	bool flag = false; 
	int a[10] = {2,11,4,1,5,18,13,10,15,8};
	cout << "數組中的數分别是：";
	for(int i = 0;i<10;i++)
		cout << a[i] << " ";
	cout << endl;
	for(int i = 0;i<9&&!flag;i++)
	{
		flag = true;
		for(int j = 0;j<9-i;j++)
		{
			int temp = 0;		
			if(a[j]>a[j+1])
			{
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				flag = false;
			}
		}
		cout << "第" << i << "輪排序之後：";
		for(int k =0;k<10;k++)
		{
			cout << a[k] << " ";
		}
		cout << endl;
	}
	cout << "排序之後數組如下：";
	for(int i = 0;i<10;i++)
		cout << a[i] << " ";
	cout << endl;
	return 0;
}
           

運作代碼，結果如下：
           

在第四輪排序之後可以看到資料已經有序了，再進行第五輪周遊時，沒有進行交換資料的操作，是以設定的flag = true，此時再進行i<9&&!flag的判斷時，條件不成立，可以提前結束排序，以免再有多餘的周遊和比較的過程。

感興趣的朋友們可以關注我，一起學習C++吧！