手撕排序算法系列之：冒泡排序。

從本篇文章開始，我會介紹并分析常見的幾種排序，大致包括插入排序，冒泡排序，希爾排序，選擇排序，堆排序，快速排序，歸并排序等。

大家可以點(diǎn)擊此鏈接閱讀其他排序算法：排序算法_大合集（data-structure_Sort）

本篇主要來手撕冒泡排序~~?

目錄

1.常見的排序算法

1.1交換排序

2.冒泡排序的實現(xiàn)

2.1基本思想

2.2單趟冒泡排序

2.2.1思路分析

2.2.2單趟代碼實現(xiàn)

3.冒泡排序代碼實現(xiàn)

4.冒泡排序測試

5.冒泡排序的時間復(fù)雜度

5.1最壞情況?

5.2最好情況

6.冒泡排序的優(yōu)化寫法?

6.1優(yōu)化思想

6.2優(yōu)化代碼?

6.3優(yōu)化算法的時間復(fù)雜度

6.3.1 最壞情況

6.3.2 最好情況

7.冒泡排序的特性總結(jié)

1.常見的排序算法

1.1交換排序

冒泡排序?qū)儆谝环N交換排序，因此我們在了解冒泡排序之前，先了解一下交換排序的基本思想。

基本思想：所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位置。

交換排序的特點(diǎn)是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

2.冒泡排序的實現(xiàn)

2.1基本思想

?直接插入排序是一種簡單的交換排序法，其基本思想是：

用兩個變量指定2個數(shù)，如果前一個數(shù)比后一個數(shù)字大就交換（升序）。

2.2單趟冒泡排序

2.2.1思路分析

單趟下來冒泡排序就會把最大的數(shù)字放在最后一位（升序）。

2.2.2單趟代碼實現(xiàn)

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//單趟
for (int i = 1; i < n ; ++i)
{
	if (a[i - 1] > a[i])
		{
		Swap(&a[i - 1], &a[i]);
		}
}

3.冒泡排序代碼實現(xiàn)

在單趟的基礎(chǔ)之上，加上一個循環(huán)，將單趟套進(jìn)去即可。需要注意的是，每次循環(huán)冒出一個數(shù)字，因此單趟循環(huán)之后到下一次循環(huán)中比較次數(shù)就要減一，這里我們使用變量來控制即可

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		//單趟
		for (int i = 1; i < n - j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
			}
		}
	}
}

4.冒泡排序測試

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//冒泡排序 時間復(fù)雜度：O(N^2)
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		//單趟
		for (int i = 1; i < n - j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
			}
		}
	}
}
int main()
{
	//冒泡排序
	TestBubbleSort();
	return 0;
}

測試結(jié)果：

5.冒泡排序的時間復(fù)雜度

5.1最壞情況?

最壞情況：逆序排順序。假設(shè)有n個數(shù)，等差數(shù)列1+2+3+4+...+n

因此最壞的時間復(fù)雜度為O(n^2)。

5.2最好情況

最好情況：有序排有序。對于冒泡排序來說，即使是有序仍然會把每個數(shù)進(jìn)行冒泡。雖然有序，但是冒泡排序不知道呀，仍然按著老套路一個一個比較冒。

因此最好的時間復(fù)雜度仍為O(n^2)。

6.冒泡排序的優(yōu)化寫法?

在時間復(fù)雜度分析的過程中，我們可以發(fā)現(xiàn)，如果序列已經(jīng)有序了，時間復(fù)雜度仍然是O(n^2).因此我們可以對這種情況進(jìn)行優(yōu)化。

6.1優(yōu)化思想

我們定義一個變量，在冒泡的過程中，如果有兩個數(shù)字進(jìn)行交換，說明原序列不是有序的，但是如果冒一遍發(fā)現(xiàn)，沒有數(shù)字記性交換，說明該序列是有序的，就沒必要繼續(xù)冒下去了。因此，我們可以定義一個exchange變量，其實賦值為0，如果冒一遍有交換，就讓exchange = 1，如果沒有交換，不改變exchange的值，我們最后只需要判斷exchange的值即可的值序列是否有序。

6.2優(yōu)化代碼?

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

//冒泡排序 時間復(fù)雜度：O(N^2)
//優(yōu)化：如果前幾個已經(jīng)有序,比較一遍之后后續(xù)的無序再進(jìn)行比較 直接往后走
//實現(xiàn):定義一個exchange變量，初始化為0;如果交換就說明變化，將exchange變1.
//沒變的話就說明有序，就不用往下走 直接break;

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		int exchange = 0;
		//單趟
		for (int i = 1; i < n - j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				exchange = 1;
				Swap(&a[i - 1], &a[i]);
			}
		}

		if (exchange == 0)
			break;
	}
}

int main()
{
	//冒泡排序
	TestBubbleSort();
	return 0;
}

6.3優(yōu)化算法的時間復(fù)雜度

6.3.1 最壞情況

最壞情況仍是逆序排順序 時間復(fù)雜度O(n^2)

6.3.2 最好情況

最好情況是本身就有序，我們在第一遍冒泡過程過，exchange沒有改變，我們就break了。

因此此時的時間復(fù)雜度是O(n)。

7.冒泡排序的特性總結(jié)

冒泡排序的特性總結(jié)：

1. 冒泡排序是一種非常容易理解的排序

2. 時間復(fù)雜度： O(N^2)

3. 空間復(fù)雜度： O(1)

4. 穩(wěn)定性：穩(wěn)定

（本篇完）?文章來源地址http://www.zghlxwxcb.cn/news/detail-501879.html

到了這里，關(guān)于[ 數(shù)據(jù)結(jié)構(gòu) -- 手撕排序算法第二篇 ] 冒泡排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！