1. 問題描述

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

2. 問題分析

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

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

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

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

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

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

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

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

3. 算法設(shè)計

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

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

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

動圖演示

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

4. 程序設(shè)計

設(shè)計一

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

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

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

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

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

設(shè)計二

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

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

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

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

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

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

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

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

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

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

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

結(jié)論

由上面的程序段發(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è)有下面一組無序數(shù)組，我們要對它進(jìn)行升序排序

完整代碼

#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ù)組相鄰兩個元素進(jìn)行交換
			{
				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;
}

運(yùn)行結(jié)果

代碼貼圖

7. 問題拓展

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

選擇排序思想：

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

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

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

對剩下的子表采用同樣的方法，直到子表為空。在最壞情況下需要比較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;//假設(shè)第一個元素是最小的
		for (j = i + 1; j < len; j++)
		{
			if (arr[j] < arr[min])
			{
				min = j;//保存最小元素的下標(biāo)
			}
		}
		//交換
		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;
}

運(yùn)行結(jié)果

代碼貼圖

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

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

最新評論