1. 問題描述

對N個整數(shù)（數(shù)據(jù)由鍵盤輸入）進行升序排列。

2. 問題分析

對于N個數(shù)因其類型相同，我們可利用 數(shù)組 進行存儲。

冒泡排序是在 兩個相鄰元素之間進行比較交換的過程將一個無序表變成有序表。

冒泡排序的思想：首先，從表頭開始往后掃描數(shù)組，在掃描過程中逐對比較相鄰兩個元素的大小。

若相鄰兩個元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個逆序。

在掃描過程中，不斷地將兩相鄰元素中的大者往后移動，最后就將數(shù)組中的最大者換到了表的最后，這正是數(shù)組中最大元素應有的位置。

然后，在剩下的數(shù)組元素中（n-1個元素），重復上面的過程，將次小元素放到倒數(shù)第 2 個位置。

不斷重復上述過程，直到剩下的數(shù)組元素為 0 為止，此時的數(shù)組就變?yōu)榱擞行颉?/p>

假設數(shù)組元素的個數(shù)為 n nn，在最壞情況下需要的比較總次數(shù)為:((n−1)+(n−2)+...+2+1)=n(n−1)/2。

3. 算法設計

冒泡排序的過程我們用示意圖簡單的表示，從整個排序過程中尋找規(guī)律，n個元素只需比較n−1次即可。

假設一個數(shù)組中有 7 個元素，現(xiàn)在對這 7 個元素進行排序，只需比較 6 輪即可得到所要的有序序列。

示意圖中最后加粗的數(shù)字即為經(jīng)過一輪交換位置固定的數(shù)字。示意圖如下：

動圖演示

清楚了冒泡排序的過程，我們再來看一個動態(tài)圖

4. 程序設計

設計一

數(shù)組名用 a 表示、數(shù)組下標用 j 表示，數(shù)組中相鄰兩個元素的下標可表示為 a[j]、a[j+1] 或 a[j-1]、a[j]。

在利用數(shù)組解決問題時需要注意數(shù)組下標不要越界。

假如定義一個整形數(shù)組 int a[n]，則數(shù)組元素下標的取值范圍是0～(n−1)，下標小于0或者大于n−1 都視為下標越界。

如果相鄰元素采用 a[j]、a[j＋1] 表示的話，則下標取值范圍是0～(n−2)；

若采用 a[j-1]、a[j] 表示，下標取值范圍則是1～(n−1)

設計二

數(shù)組元素互換 也是經(jīng)常遇到的一類題型，一般這種情況我們需要 借助一個中間變量 才可以完成，對于許多初學者來說經(jīng)常犯的一個錯誤是：對兩個元素直接相互賦值，而不借助中間變量。

我們先來看生活中的一個例子：

在藍墨水瓶中裝有藍墨水，紅墨水瓶中裝有紅墨水；現(xiàn)在我們要把藍墨水放到紅墨水瓶中，紅墨水放到藍墨水瓶中。

做法是先找一個白色空瓶（作用相當于程序中的中間變量）：

首先將藍墨水倒入白色空瓶： t=a[i] 或 t=a[i+1]；

接著將紅墨水倒入藍墨水瓶：a[i]=a[i+1] 或 a[i+1]=a[i]；

最后將白瓶中的藍墨水倒入紅墨水瓶：a[i+1]=t 或 a[i]=t；

經(jīng)過這 3 步就完成了紅墨水與藍墨水的互換。如果不借助白色空瓶，直接把藍墨水倒入紅墨水瓶，或把紅墨水倒入藍墨水瓶，這樣必將破壞原來所存儲的內(nèi)容。

第一輪的交換過程可以用簡單的程序段進行表示：

第二輪交換過程（最后一個元素經(jīng)過第一輪比較已經(jīng)確定，不需要再次進行比較）：

第三輪交換過程（最后兩個元素已經(jīng)確定，不需要再次進行比較）：

結論

由上面的程序段發(fā)現(xiàn)，第一輪比較的判定條件為 j < n-1；

第二輪為 j < n-2；

第三輪為 j < n-3；

依次類推，第 i 輪的循環(huán)判定條件必為 j < n-i。

在編程過程中我們可以用兩層循環(huán)來控制，第一層循環(huán)控制交換的輪數(shù)，第二層循環(huán)控制每輪需要交換的次數(shù)。

5. 流程框架

6. 代碼實現(xiàn)

假設有下面一組無序數(shù)組，我們要對它進行升序排序

完整代碼

#include <stdio.h>

//冒泡排序函數(shù)
void BubbleSort(int arr[], int len)
{
	int i;
	int j;
	int temp;
	for (i = 0; i < len - 1; i++) //控制比較的輪數(shù)
	{
		for (j = 0; j < len - 1 - i; j++) //控制每輪比較的次數(shù)
		{
			if (arr[j] > arr[j + 1]) //數(shù)組相鄰兩個元素進行交換
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;

			}
		}

	}

}

//輸出函數(shù)
void print(int arr[], int len)
{
	int i;
	for (i = 0; i < len; i++)
	{
		printf("%3d ", arr[i]);
	}
}

int main()
{

	int arr[10] = { 5,8,6,3,9,2,1,7,12,4 };

	BubbleSort(arr, 10);

	printf("The data after sorted：\n");
	print(arr, 10);

	printf("\n");

	return 0;
}

運行結果

代碼貼圖

7. 問題拓展

常用的排序方法除了上述的冒泡排序外，還有選擇排序、插入排序、快速排序和堆排序等，下面簡單介紹一下 選擇排序。

選擇排序思想：

掃描整個線性表，第一輪比較拿數(shù)組中的第一個元素與其他元素進行比較，遇到比第一個元素小的則進行交換；

再拿著交換之后的第一個元素接著上次比較的位置與后面的元素進行比較，直到掃描到線性表的最后，從中選出最小的元素，將它交換到表的最前面（這是它應有的位置）。

第二輪比較的時候從第二個元素開始，依次與第三個、第四個直到最后一個比較，在比較過程中有比第二個元素小的進行交換，接著與后面的元素比較；

對剩下的子表采用同樣的方法，直到子表為空。在最壞情況下需要比較n(n−1)/2 次。

選擇排序如下

#include <stdio.h>

//選擇排序
void selectSort(int arr[], int len)
{
	int i;
	int j;
	for (i = 0; i < len - 1; i++)
	{
		int min = i;//假設第一個元素是最小的
		for (j = i + 1; j < len; j++)
		{
			if (arr[j] < arr[min])
			{
				min = j;//保存最小元素的下標
			}
		}
		//交換
		int temp = arr[min];
		arr[min] = arr[i];
		arr[i] = temp;
	}
}

//輸出
void print(int arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%3d ", arr[i]);
	}
}

int main()
{
	int arr[10] = { 5,8,6,3,9,2,1,7,12,4 };

	selectSort(arr, 10);

	printf("The data after sorted：\n");
	print(arr, 10);

	printf("\n");

	return 0;
}

運行結果

代碼貼圖

不同排序法的效率是不同的，不同需求情況下可選擇不同的方法。

到此這篇關于C語言實現(xiàn)冒泡排序算法的示例詳解的文章就介紹到這了,更多相關C語言冒泡排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論