C語言實(shí)現(xiàn)冒泡排序算法代碼怎么寫

這篇文章主要介紹“C語言實(shí)現(xiàn)冒泡排序算法代碼怎么寫”，在日常操作中，相信很多人在C語言實(shí)現(xiàn)冒泡排序算法代碼怎么寫問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”C語言實(shí)現(xiàn)冒泡排序算法代碼怎么寫”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

1. 問題描述

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

2. 問題分析

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

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

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

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

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

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

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

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

3. 算法設(shè)計(jì)

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

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

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

動(dòng)圖演示

清楚了冒泡排序的過程，我們?cè)賮砜匆粋€(gè)動(dòng)態(tài)圖

4. 程序設(shè)計(jì)

設(shè)計(jì)一

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

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

假如定義一個(gè)整形數(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è)計(jì)二

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

我們先來看生活中的一個(gè)例子：

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

做法是先找一個(gè)白色空瓶（作用相當(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)墨水瓶，這樣必將破壞原來所存儲(chǔ)的內(nèi)容。

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

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

第三輪交換過程（最后兩個(gè)元素已經(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. 代碼實(shí)現(xiàn)

假設(shè)有下面一組無序數(shù)組，我們要對(duì)它進(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ù)組相鄰兩個(gè)元素進(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. 問題拓展

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

選擇排序思想：

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

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

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

對(duì)剩下的子表采用同樣的方法，直到子表為空。在最壞情況下需要比較n(n&minus;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è)第一個(gè)元素是最小的
		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語言實(shí)現(xiàn)冒泡排序算法代碼怎么寫”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！