? ? ? 方法步驟：? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ①?比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

? ? ? ? ? ②?對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后?? ? ? ? ? ? ? ? ?的元素會(huì)是最大的數(shù)。

? ? ? ? ? ③?針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

? ? ? ? ? ④?持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

? ? ? ? 圖示

? ? ? ??

代碼實(shí)現(xiàn)

??

//冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 0; //作為判斷是否交換的標(biāo)志
		for (int j = 1; j < n - i; j++)
		{
			if (a[j-1] > a[j])
			{
				flag = 1;
				int tmp = a[j-1]; //交換
				a[j-1] = a[j];
				a[j] = tmp;
			}
		}
		if (flag == 0)
			break;
	}
}

時(shí)間和空間復(fù)雜度

? ? ?若初始序列為正序序列，則只需進(jìn)行一趟排序，在排序過(guò)程中進(jìn)行n-1次比較，不移動(dòng)元素；若初始序列為逆序序列，則需進(jìn)行n-1趟排序，n(n-1) / 2次比較，每次比較都需要移動(dòng) 3 次，移動(dòng)次數(shù)為? 3n(n-1) / 2.

? ? 時(shí)間復(fù)雜度：O(n^2)

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

穩(wěn)定性

? ? ?冒泡排序：穩(wěn)定排序

二. 快速排序

? ? ? 基本思想

? ? ? ?任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過(guò)程，直到所有元素都排列在相應(yīng)位置上為止
?

? ? ?方法步驟：? ? ? ?

1. 從數(shù)列中挑出一個(gè)元素，稱為 "基準(zhǔn)"（pivot）;

2. 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；

3. 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；

? ? ?圖示

代碼實(shí)現(xiàn)

? ?

?hoare法

? ? ? ? 思想方法：

? ? ? ? ? ?定義兩個(gè)指針 left 和 right，分別指向左邊和右邊，左指針從左向右找大( 大于pivotkey)，右? ? ? 指針從右向左找小(小于pivotkey)，左大右小就交換，相遇時(shí)與基準(zhǔn)值交換

? ? ? ? ?圖解：

? ? ? ? ? ? ? ?

? ? ? ??

?

int PartSort(int* a, int left, int right) //給數(shù)組分區(qū)，返回樞軸元素下標(biāo)
{
	int pivotkey = left;
	while (left < right)
	{
		//右邊找比pivotkey小的
		while (left < right && a[right] >= a[pivotkey])
			right--;
		//左邊找比pivotkey大的
		while (left < right && a[left] <= a[pivotkey])
			left++;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[pivotkey]); //把記錄的樞軸元素，交換到樞軸位置
	return left;   //返回樞軸所在的位置下標(biāo)
}

? ?

?挖坑法

? ? ? 思想方法：

? ? ? ? ? ? ??定義兩個(gè)指針 left 和 right，分別指向左邊和右邊，先將第一個(gè)數(shù)據(jù)元素放在臨時(shí)變量 pivotkey 中，形成一個(gè)坑位；讓右指針先走，當(dāng)指向的值小于 pivotkey 就停下，形成新的坑位；讓左指針走，當(dāng)指向的值大于 pivotkey 就停下，使其形成此次的新坑位，直到兩指針相遇，把pivotkey的值放入坑中。

?

? ? ? ? 圖解：

?? ? ? ??

? ? ? ? ? ?

int PartSort(int* a, int left, int right) //給數(shù)組分區(qū)，返回樞軸元素下標(biāo)
{
	int pivotkey = a[left]; //保存第一個(gè)數(shù)據(jù)元素的值
	while (left < right)
	{
		while (left < right && a[right] >= pivotkey) //找小
		{
			right--;
		}
		a[left] = a[right]; //右邊形成新的坑
		while (left < right && a[left] <= pivotkey) //找大
		{
			left++;
		}
		a[right] = a[left]; //左邊形成新的坑
	}
	a[left] = pivotkey;
	return left;
}

? 前后指針?lè)?/strong>

int PartSort(int* a, int left, int right) //給數(shù)組分區(qū)，返回樞軸元素下標(biāo)
{
	int prev = left;
	int cur = left + 1;
	int pivotkey = left;
	while (cur <= right)
	{
		if (a[cur] < a[pivotkey] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		cur++;
	}
	Swap(&a[pivotkey], &a[prev]);
	return prev;
}