一.基礎(chǔ)排序算法

1.冒泡排序

（1）算法思想

重復(fù)循環(huán)遍歷，每次比較相鄰的兩個(gè)元素，如果前大于后就交換，這樣每次最大的元素都會(huì)交換到最后，每次循環(huán)遍歷時(shí)去掉最后的元素。

（2）代碼實(shí)現(xiàn)

void BubbleSort(int arr[], int size)
{
	for (size_t i = 0; i < size-1; i++)
	{
        bool flag=false;
		for (size_t j = 0; j < size - i - 1; j++) 
		{
			if (arr[j] > arr[j + 1])
			{
				int temp=arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
                flag=true;
			}
		}
        if(!flag)//優(yōu)化：如果這一趟沒有交換元素，說明已經(jīng)有序，無需再排了
        return;
	}
}

（3）性能分析與優(yōu)化

最好時(shí)間復(fù)雜度：O(n)，(在加了優(yōu)化操作后，如果元素原本就已經(jīng)有序，則只需進(jìn)行一次遍歷)

平均時(shí)間復(fù)雜度：O(n^2)；（雙重循環(huán)）

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

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

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

優(yōu)化：定義一個(gè)flag記錄本次循環(huán)是否交換元素，如果沒有則說明元素已經(jīng)有序，直接結(jié)束排序。

2.選擇排序

（1）算法思想

遍歷數(shù)組，每次假定第i個(gè)為最小，與后面的比較，找到最小的，交換，這樣每次都能將最小的元素交換到i的位置（即每次將最小的元素排到正確位置）

（2）代碼實(shí)現(xiàn)

void ChoiceSort(int arr[], int size)
{
	for (size_t i = 0; i < size-1; i++)
	{
		int min = arr[i];
		int k = i;
		for (size_t j = i+1; j < size ; j++)
		{
			if (min > arr[j])
			{
				min = arr[j];
				k = j;
			}
		}
		if (k != i)
		{
			int temp = arr[i];
			arr[i] = arr[k];
			arr[k] = temp;
		}
	}
}

（3）性能分析與優(yōu)化

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

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

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

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

穩(wěn)定性：不穩(wěn)定

注意：雖然冒泡排序與選擇排序的平均時(shí)間復(fù)雜度都是O(n^2)，但是選擇排序一般更快，原因在于交換次數(shù)差異，冒泡排序的交換頻繁（交換n^2次），而選擇排序交換較少（n次）。

3.插入排序

（1）算法思想

假設(shè)第一個(gè)元素已經(jīng)有序，每次遍歷將遍歷到的元素按順序插入到前面已經(jīng)有序的數(shù)組中。

（2）代碼實(shí)現(xiàn)

void InsertSort(int arr[], int size)
{
	for (size_t i = 1; i < size; i++)
	{
		int val = arr[i];
		int j = i - 1;
		for (; j >= 0; j--)
		{
			if (arr[j] <val)
			{
				break;
			}
			arr[j+1] = arr[j];
		}
		arr[j + 1] = val;
	}
}

（3）性能分析與優(yōu)化

最好時(shí)間復(fù)雜度：O(n)（原數(shù)組已經(jīng)有序，只需要進(jìn)行一次遍歷）

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

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

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

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

適用場景：數(shù)據(jù)規(guī)模小，相對(duì)有序的數(shù)據(jù)，常用于收尾工作（對(duì)于相對(duì)有序的數(shù)據(jù)排序速度較快）

4.希爾排序

（1）算法思想

希爾排序?qū)嶋H上是將插入排序進(jìn)行分組優(yōu)化。

選擇合適的希爾增量，基礎(chǔ)的為每次按半分組（即如果數(shù)組中存在10個(gè)元素，那么分成5組，每組2個(gè)元素，比較這兩個(gè)元素，交換）。

（2）代碼實(shí)現(xiàn)

void ShellSort(int arr[], int size)
{
	for (size_t gap = size/2; gap >0 ; gap/=2)
	{
		for (size_t i = gap; i < size; i++)
		{
			int val = arr[i];
			int j = i - gap;
			for (; j >= 0; j-=gap)
			{
				if (arr[j] < val)
				{
					break;
				}
				arr[j + gap] = arr[j];
			}
			arr[j + gap] = val;
		}
	}
}

（3）性能分析與優(yōu)化

最好時(shí)間復(fù)雜度：O(nlogn)或O(n)；

平均時(shí)間復(fù)雜度：O(n^1.3)，（依賴于希爾增量，如果二分的話，就為n^2）

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

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

穩(wěn)定性：不穩(wěn)定

四種基礎(chǔ)排序算法比較

一般情況下：算法效率：希爾>插入>選擇>冒泡

對(duì)于趨向于有序的數(shù)組，我們使用插入排序的效率更高。

一般中等數(shù)據(jù)量的排序都用希爾排序,選擇合適的增量序列,效率就已經(jīng)不錯(cuò)了,如果數(shù)據(jù)量比較大,可以選擇高級(jí)的排序算法,如快速排序。

二.高級(jí)排序算法

1.快速排序

（1）算法思想

思想:選取一個(gè)基準(zhǔn)數(shù),把小于基準(zhǔn)數(shù)的元素都調(diào)整到基準(zhǔn)數(shù)的左邊,把大于基準(zhǔn)數(shù)的元素都調(diào)整到基準(zhǔn)數(shù)的右邊,然后對(duì)基準(zhǔn)數(shù)左邊和右邊的序列繼續(xù)進(jìn)行如下的操作,直到整個(gè)序列變成有序的。

操作流程：1：選取基準(zhǔn)數(shù)val（默認(rèn)選擇第一個(gè)元素），定義L與R兩個(gè)下標(biāo)值，指向數(shù)組的首和尾。

2、從R開始往前找第一個(gè)<val的數(shù)字,放到L的地方，L++

3、從L開始往后找第一個(gè)>val的數(shù)字,放到R的地方,R --

4、重復(fù)上面的過程

（2）代碼實(shí)現(xiàn)

//快排分割函數(shù)
int Partation(int arr[], int L, int R)
{
	int val = arr[L];
	while (L < R)
	{
		while (arr[R]>val&&L<R)
		{
			R--;
		}
		if (L < R)
		{
			arr[L] = arr[R];
			L++;
		}
		while (arr[L] < val && L < R)
		{
			L++;
		}
		if (L < R)
		{
			arr[R] = arr[L];
			R--;
		}
	}
	arr[L] = val;
	return L;
}
//快排函數(shù)接口
void QuickSort(int arr[], int L, int R)
{
	if (L >= R)
		return;
	int pos = Partation(arr,  L,  R);
	//對(duì)分割后的兩部分分別進(jìn)行快排
	QuickSort(arr, L, pos - 1);
	QuickSort(arr, pos+1, R);
}
//快排函數(shù)
void QuickSort(int arr[],int size)
{
	return QuickSort(arr,0,size-1);
}

（3）性能分析與優(yōu)化

最好時(shí)間復(fù)雜度：O(nlogn)，遞歸深度最好為log(n)（完全二叉樹），比較過程為O(n)；

平均時(shí)間復(fù)雜度：O(nlogn)；

最壞時(shí)間復(fù)雜度：O(n^2)（數(shù)據(jù)完全有序且恒選擇第一個(gè)元素作為基準(zhǔn)數(shù)，會(huì)退化為冒泡排序）;

空間復(fù)雜度：最好O(nlogn),最壞O(n^2)（數(shù)據(jù)完全有序且恒選擇第一個(gè)元素作為基準(zhǔn)數(shù)）

穩(wěn)定性：不穩(wěn)定

快排算法優(yōu)化
1、隨著快排算法執(zhí)行,數(shù)據(jù)越來越趨于有序,在一定的范圍內(nèi),可以采用插入排序代替快速排序

2.選擇合適的基準(zhǔn)數(shù)，三數(shù)取中法（L,R,mid三數(shù)值在中間的），隨機(jī)數(shù)法。

適用場景：絕大多數(shù)通用場景，尤其是處理大量隨機(jī)元素，標(biāo)準(zhǔn)庫的默認(rèn)排序。

2.歸并排序

（1）算法思想

歸并排序的核心是分治思想，先遞，遞到只有一個(gè)元素，再在歸的過程中，對(duì)數(shù)據(jù)進(jìn)行合并排序

（2）代碼實(shí)現(xiàn)

//歸并過程函數(shù)
void Merge(int arr[], int l, int m, int r)
{
	int* p = new int[r - l + 1];
	int idx = 0;
	int i = l;
	int j = m + 1;
	while (i <= m && j <= r)
	{
		if (arr[i] <= arr[j])
		{
			p[idx++] = arr[i++];
		}
		else
		{
			p[idx++] = arr[j++];
		}
	}
	while (i <= m)
	{
		p[idx++] = arr[i++];
	}
	while (j <= r)
	{
		p[idx++] = arr[j++];
	}
	//在不合并好的數(shù)據(jù)拷貝到原始數(shù)組中
	for (size_t i = l,j=0; i <=r ; i++,j++)
	{
		arr[i] = p[j];
	}
	delete[]p;
	p = nullptr;
}
//歸并排序
void MergeSort(int arr[], int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	//先遞歸
	MergeSort(arr, begin, mid);
	MergeSort(arr, mid + 1, end);
	//再歸并
	Merge(arr, begin, mid, end);
}

（3）性能分析與優(yōu)化

最好時(shí)間復(fù)雜度：O(nlogn)

平均時(shí)間復(fù)雜度：O(nlogn)；

最壞時(shí)間復(fù)雜度：O(nlogn)（無論原先元素是否有序，遞歸的深度恒是nlogn）

空間復(fù)雜度：O(n)

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

適用場景：對(duì)穩(wěn)定性有要求，或者處理鏈表排序、海量數(shù)據(jù)的外部排序時(shí)，歸并排序是首選。

3.堆排序

（1）算法思想

找到每一個(gè)非葉子節(jié)點(diǎn)，將二叉堆調(diào)整為一個(gè)大根堆，之后將堆頂元素與隊(duì)尾元素交換，由于大根堆堆頂是恒是最大值，所以每一次調(diào)整都將一個(gè)最大值交換到了一個(gè)正確位置。

（2）代碼實(shí)現(xiàn)

//堆排下沉操作
void siftDown(int arr[], int i, int size)
{
	int val = arr[i];
	while (i < size  / 2)
	{
		int child = 2 * i + 1;
		if (child + 1 < size && arr[child + 1] > arr[child])
		{
			child = child + 1;
		}
		if (val < arr[child])
		{
			arr[i] = arr[child];
			i = child;
		}
		else
			break;
	}
	arr[i] = val;
}
//堆排序
void HeapSort(int arr[], int size)
{
	int n = size - 1;
	//找到每一個(gè)非葉子節(jié)點(diǎn)
	for (int i = (n - 1) / 2; i >= 0; i--)
	{
		siftDown(arr, i, size);
	}
	for (size_t i = n; i > 0; i--)
	{
		int temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;
		siftDown(arr, 0,i);
	}
}

（3）性能分析與優(yōu)化

最好時(shí)間復(fù)雜度：O(nlogn)

平均時(shí)間復(fù)雜度：O(nlogn)；

最壞時(shí)間復(fù)雜度：O(nlogn)

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

穩(wěn)定性：不穩(wěn)定

適用場景：內(nèi)存極其受限的嵌入式系統(tǒng)，或者經(jīng)典的 Top K 問題

4.基數(shù)排序（桶排序）

（1）算法思想

先構(gòu)建桶（沒有負(fù)數(shù)構(gòu)建0~9號(hào)桶，有負(fù)數(shù)構(gòu)建-9~9號(hào)桶），從右向左依次看元素的每一位，如果那一位與桶的序號(hào)相同，就將其放在對(duì)應(yīng)的桶中，放完一位后，再將所有的元素按桶的順序取出，如此循環(huán)，直到排完所有的位后。

（2）代碼實(shí)現(xiàn)

//基數(shù)排序
void RadixSort(int arr[], int size)
{
	int maxData = arr[0];
	for (size_t i = 1; i < size; i++)
	{
		if (maxData<abs(arr[i]))
		{
			maxData = abs(arr[i]);
		}
	}
	int len = to_string(maxData).size();
	vector<vector<int>>vecs;
	int mod = 10;
	int dev = 1;
	for (size_t i = 0; i < len; mod*=10,dev*=10,i++)
	{
		vecs.resize(20);
		for (size_t j = 0; j < size; j++)
		{
			int index = arr[j] % mod / dev+10;
			vecs[index].push_back(arr[j]);
		}
		int idx = 0;
		for (auto vec : vecs)
		{
			for (int v:vec)
			{
				arr[idx++] = v;
			}
		}
		vecs.clear();
	}

（3）性能分析與優(yōu)化

最好時(shí)間復(fù)雜度：O(nd)（d為最大數(shù)據(jù)的長度）

平均時(shí)間復(fù)雜度：O(nd)；

最壞時(shí)間復(fù)雜度：O(nd)

空間復(fù)雜度：O(n)（O(n+k)）（k為桶/基數(shù)的個(gè)數(shù)）

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

適用場景：整數(shù)、固定長度的字符串排序（適用范圍較窄，在處理海量整數(shù)時(shí)，速度可以碾壓前面三種 O(n log n) 的算法）

四種高級(jí)排序算法的比較

對(duì)于一般無序的大規(guī)模數(shù)據(jù)一般：快速排序 > 歸并排序 ≈ 堆排序 > 基數(shù)排序

到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)排序算法詳解的文章就介紹到這了,更多相關(guān)C++排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論