可能是你看過最全的十大排序算法詳解(完整版代碼)

更新時(shí)間：2022年06月17日 11:56:54 作者：秋名山碼民

排序算法是程序中常用的算法,下面這篇文章主要給大家介紹了關(guān)于十大排序算法的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下

前言

兄弟們，應(yīng)上篇數(shù)據(jù)結(jié)構(gòu)的各位要求，今天我開始工作了，開始肝算法，劍指offer還在路上，我真想開車去接它，奈何碼神沒有駕照的開車，算了，弄排序算法吧，有點(diǎn)長，耐心看啊，原創(chuàng)不易，你們懂的，先上一張圖

可以看出排序算法，還是比較多的，算了，不多說了，你我肝完就是出門自帶4年實(shí)習(xí)經(jīng)驗(yàn)的！

交集排序

冒泡

冒泡我一般也將它稱為枚舉就是把所有都走一遍嘛，效率比較低，一般在算法競賽中如果實(shí)在沒有比較好的，可以用，那就先講一個(gè)簡單的枚舉吧！

枚舉字典序

首先可能有的同學(xué)不知道什么是字典序，請(qǐng)看：
（1，2，3），（1，3，2）…這就是字典序的體現(xiàn)，官方解釋是這樣的：

字典排序（lexicographical order）是一種對(duì)于隨機(jī)變量形成序列的排序方法。其方法是，按照字母順序，或者數(shù)字小大順序，由小到大的形成序列。

比如說有一個(gè)隨機(jī)變量X包含{1 2 3}三個(gè)數(shù)值。

其字典排序就是{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 1 2} {3 2 1}

如果是字母：先比較第一個(gè)字符i和b，b<i，b是第2個(gè)，i是第9個(gè)2<9于是baray<ilove如果第一位相同，就比較第二位，

例如：abcdd<abcde aaaay<aaaaz如果其中之一是另一個(gè)的前綴，則短的那個(gè)排前面：aaa

下面用代碼實(shí)現(xiàn)一下1-n的排列：

//冒泡排序，我也將它稱為枚舉
#include<iostream>
#include<cstdio>
using namespace std;
void print(int n, int *a, int cur)
{
	if (cur == n)//遞歸邊界
	{
		for (int i = 0; i < n; i++)
		{
			printf("%d", a[i]);
		}
		printf("\n");
	}
	else for (int i = 1; i <= n; i++)
	{
		int OK = 1;
		for (int j = 0; j < cur; j++)
		{
			if (a[j] == i)//判斷i是否出現(xiàn)過
				OK = 0;
			if (OK)//i沒有出現(xiàn)過下一個(gè)
			{
				a[cur] = i;
				print(n, a, cur + 1);//遞歸
			}
		}
	}
}
int main()
{

}

下面我們來看一下正宗的冒泡排序，總體思想是：倆倆比較，如果反序交換，直到?jīng)]有反序的記錄為止，代碼實(shí)現(xiàn)比較簡單，是倆個(gè)for循環(huán)的嵌套

#include<iostream>
#include<algorithm>//調(diào)用算法庫，使用交換函數(shù)swap
#include<cstdio>
using namespace std;
int main()
{
	int a[10];
	for (int i = 0; i < 10; i++)
	{
		cin >> a[i];

	}
	for (int i = 0; i < 10; i++)
	{
		for (int j = i + 1; j < 10; j++)
		{
			if (a[i] < a[j])
				swap(a[i], a[j]);
		}
	}
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

總體來說比較簡單，但是耗時(shí)，耗內(nèi)存，反正就是不好，來優(yōu)化一下，為什么不好？歸根結(jié)底還是做了許多重復(fù)的運(yùn)算，大量的比較，
總體思路是這樣的：再某一次比較后，發(fā)現(xiàn)所有的數(shù)據(jù)都變成了順序，直接退出循環(huán)，不再繼續(xù)循環(huán)

//將for改為
	bool flag = true;
	for (int i = 0; i < 10 && flag; i++)
	{
		flag = false;
		for (int j = 10 - 1; j >= i; j--)
		{
			if (a[j] > a[i])
			{
				swap(a[j], a[j + 1]);
					flag = true;
			}
		}
	}

算法復(fù)雜度：倆個(gè)for，就是O（n^2)了，有點(diǎn)大

簡單

選擇排序

先來和冒泡排序比較一下，他倆的主要區(qū)別就是冒泡排序的數(shù)據(jù)在不斷的交換，而快速排序先交換數(shù)據(jù)的別名，再交換本身。打個(gè)比喻就是，一個(gè)是幻想天上掉餡餅，背水一戰(zhàn)，的炒股短線選手，而另一個(gè)則是看中時(shí)機(jī)的炒股老手，俗稱股神。

好了，比較也比較完了，我們來看簡單的代碼實(shí)現(xiàn)吧

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
	int a[10];
	for (int i = 0; i < 10; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < 10; i++)
	{
		int min = i;
		for (int j = i + 1; j < 10; j++)
		{
			if (a[min] > a[j])
				min = j;//交換下標(biāo)位置
		}
		if (i != min)
			swap(a[i], a[min]);
	}
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

如果來分析算法復(fù)雜度的話，你會(huì)驚訝的發(fā)現(xiàn)時(shí)間復(fù)雜度仍舊是O（n^2)，但是我要說的是它仍舊優(yōu)于冒泡排序，why？

冒泡排序和選擇排序是排序算法中比較簡單和容易實(shí)現(xiàn)的算法。冒泡排序的思想為：每一次排序過程，通過相鄰元素的交換，將當(dāng)前沒有排好序中的最大（?。┮频綌?shù)組的最右（左）端。而選擇排序的思想也很直觀：每一次排序過程，我們獲取當(dāng)前沒有排好序中的最大（?。┑脑睾蛿?shù)組最右（左）端的元素交換，循環(huán)這個(gè)過程即可實(shí)現(xiàn)對(duì)整個(gè)數(shù)組排序。

選擇排序的平均時(shí)間復(fù)雜度比冒泡排序的稍低:

同樣數(shù)據(jù)的情況下，2種算法的循環(huán)次數(shù)是一樣的，但選擇排序只有0到1次交換，而冒泡排序只有0到n次交換

快速排序

和冒泡排序相似，但是優(yōu)于冒泡，總體是一個(gè)分治的思想，交換軸點(diǎn)元素

劃分：將數(shù)組中的元素都重排分成左右倆部分，使得左邊都小于等于右邊的任意元素
遞歸求解：把左右分別進(jìn)行排序
合并：這時(shí)你會(huì)發(fā)現(xiàn)已經(jīng)排列好了

還是排列一串?dāng)?shù)字，進(jìn)行代碼實(shí)現(xiàn)：

#include<iostream>
using namespace std;

void quickSort(int *arr,int begin,int end)
{
//begin為左，end為右
	//如果區(qū)間不只一個(gè)數(shù)
	if(begin < end)
	{
		int temp = arr[begin]; //將區(qū)間的第一個(gè)數(shù)作為基準(zhǔn)數(shù)
		int i = begin; //從左到右進(jìn)行查找時(shí)的“指針”，指示當(dāng)前左位置
		int j = end; //從右到左進(jìn)行查找時(shí)的“指針”，指示當(dāng)前右位置
		//不重復(fù)遍歷
		while(i < j)
		{
			//當(dāng)右邊的數(shù)大于基準(zhǔn)數(shù)時(shí)，略過，繼續(xù)向左查找
			//不滿足條件時(shí)跳出循環(huán)，此時(shí)的j對(duì)應(yīng)的元素是小于基準(zhǔn)元素的
			while(i<j && arr[j] > temp)
				j--;
			//將右邊小于等于基準(zhǔn)元素的數(shù)填入右邊相應(yīng)位置
			arr[i] = arr[j];
			//當(dāng)左邊的數(shù)小于等于基準(zhǔn)數(shù)時(shí)，略過，繼續(xù)向右查找
			//(重復(fù)的基準(zhǔn)元素集合到左區(qū)間)
			//不滿足條件時(shí)跳出循環(huán)，此時(shí)的i對(duì)應(yīng)的元素是大于等于基準(zhǔn)元素的
			while(i<j && arr[i] <= temp)
				i++;
			//將左邊大于基準(zhǔn)元素的數(shù)填入左邊相應(yīng)位置
			arr[j] = arr[i];
		}
		//將基準(zhǔn)元素填入相應(yīng)位置
		arr[i] = temp;
		//此時(shí)的i即為基準(zhǔn)元素的位置
		//對(duì)基準(zhǔn)元素的左邊子區(qū)間進(jìn)行相似的快速排序
		quickSort(arr,begin,i-1);
		//對(duì)基準(zhǔn)元素的右邊子區(qū)間進(jìn)行相似的快速排序
		quickSort(arr,i+1,end);
	}
	//如果區(qū)間只有一個(gè)數(shù)，則返回
	else
		return;
}
int main()
{
	int num[12] = {23,45,17,11,13,89,72,26,3,17,11,13};
	int n = 12;
	quickSort(num,0,n-1);
	cout << "排序后的數(shù)組為：" << endl;
	for(int i=0;i<n;i++)
		cout << num[i] << ' ';
	cout << endl;
	return 0;
}

算一下復(fù)雜度吧，最壞O（n^2），平均O（nlogn）幾乎沒有最壞的情況發(fā)生，所以效率還是比較高的，想一想如果就只要最大的值怎么弄？

#include<iostream>
using namespace std;
int Partition(int *a, int i, int j)
{
	int tmp = a[j];
	int index = i;
	if (i < j)
	{
		for (int k = i; k < j; k++) {
			if (a[k] >= tmp) {
				swap(a[index++], a[k]);
			}
		}
		swap(a[index], a[j]);
		return index;
	}
}


int Search(int a[], int i, int j, int k)
{
	int m = Partition(a, i, j);
	if (k == m - i + 1) return a[m];
	else if (k < m - i + 1)
	{
		return Search(a, i, m - 1, k);
	}
	//后半段
	else
	{

		//核心后半段：再找第 k-(m-i+1)大的數(shù)就行
		return Search(a, m + 1, j, k - (m - i + 1));
	}
}
int main()
{
	int a[7] = { 8,7,6,1,2,3,4 };
	int k = 3;
	cout << Search(a, 2, 6, k);
}

插入排序

直接插入排序

話說，碼神最近在玩斗地主，你們說手機(jī)斗地主和真人斗地主最大的區(qū)別，或者是說好處是什么？我感覺就是在手機(jī)上不用插牌了，省時(shí)間，這利用的就是插入排序的原理，可以說是“斗地主排序”

基本操作：將一個(gè)記錄插入到已經(jīng)排好的有序表中，從而得到一個(gè)新的，記錄數(shù)據(jù)+1的有序表
基操，看代碼：

void insertionSort(int *arr, int len) {
    if (len<2) {
        return ;
    }
    
    for (int i=1; i<len; i++) {
        int insertValue = arr[i];//暫存需要插入元素
        int j = i-1;
 
        //從右向左比較元素
        for (; j>=0 && insertValue<array[j]; j--) {
            arr[j+1] = arr[j];
        }
 
        arr[j+1] = insertValue;
    }
}

老規(guī)矩，分析時(shí)間復(fù)雜度，最好的情況是順序都是排列好的，此時(shí)只需要比較，時(shí)間復(fù)雜度為O（n），最壞的情況為O（n^2),平均下來是n ^ 2/4，所以平均時(shí)間復(fù)雜度也是O（n ^ 2).

希爾排序

如果說誰是第一個(gè)將排序算法復(fù)雜度突破O（n^2)的，那么我想希爾是第一個(gè)，可以說希爾排序是對(duì)插入排序的改進(jìn)，區(qū)別在于，希爾排序可以說是一個(gè)不斷分組的排序

先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，具體算法描述：

選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；

按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；

每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度。

實(shí)現(xiàn)如下：

 //希爾排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap>1)
	{
		//每次對(duì)gap折半操作
		gap = gap / 2;
		//單趟排序
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tem = arr[end + gap];
			while (end >= 0)
			{
				if (tem < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tem;
		}
	}
}

時(shí)間復(fù)雜度，牛逼的人們，通過大量的計(jì)算發(fā)現(xiàn)是O（n^3/2)，小于O
（n^2)，由于是跳躍式的排序所以不是穩(wěn)定排序

選擇排序

簡單選擇排序

可參考上面

堆排序

何為堆，如果已經(jīng)學(xué)過堆的話，就是那個(gè)堆，與棧相對(duì)的堆，

基本思路：將代排的序列構(gòu)造成一個(gè)大堆，此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母Y(jié)點(diǎn)，將它移走，也就是將其與堆數(shù)組的末尾元素交換，此時(shí)末尾元素就是最大值，然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)堆，這樣就會(huì)得到n個(gè)元素的次最大值，如此遞歸反復(fù)就會(huì)得到一個(gè)有序序列

varlen;   // 因?yàn)槁暶鞯亩鄠€(gè)函數(shù)都需要數(shù)據(jù)長度，所以把len設(shè)置成為全局變量
 
function buildMaxHeap(arr) {  // 建立大頂堆
    len = arr.length;
    for(vari = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
 
function heapify(arr, i) {    // 堆調(diào)整
    varleft = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
 
    if(left < len && arr[left] > arr[largest]) {
        largest = left;
    }
 
    if(right < len && arr[right] > arr[largest]) {
        largest = right;
    }
 
    if(largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}      
 
function swap(arr, i, j) {
    vartemp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
function heapSort(arr) {
    buildMaxHeap(arr);
 
    for(vari = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

時(shí)間可以說是主要耗在了初始建堆和在重建堆的反復(fù)篩選上

1.構(gòu)造堆：O（n）

2.重建堆：完全二叉樹：數(shù)據(jù)結(jié)構(gòu)，詳解時(shí)間復(fù)雜度為O(nlogn)

又因?yàn)槎雅判驅(qū)υ加涗浀呐判驙顟B(tài)并不敏感，因此它無論是好是壞，時(shí)間復(fù)雜度都為O（nlogn)，同希爾排序，都為不穩(wěn)定性的排序

歸并排序

完全二叉樹，是一棵神奇的樹，可以說歸并排序是完全體現(xiàn)了完全二叉樹的性質(zhì)

二路

若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。

把長度為n的輸入序列分成兩個(gè)長度為n/2的子序列；
對(duì)這兩個(gè)子序列分別采用歸并排序；
將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。

#include<iostream>
using namespace std;
void Merge(int[], int, int[], int, int, int)  
void MergeSort(int numbers[], int length, int temp[], int begin, int end)
{
	//1. 同樣判斷傳入的參數(shù)是否有效
	if (numbers == nullptr || length <= 0 || begin < 0 || end >= length)
		throw new exception("Invalid input.");
	
	//2. 作為遞歸的結(jié)束條件，開始下標(biāo)和結(jié)束下標(biāo)相等時(shí)，說明子序列中只有一個(gè)元素，看作有序的
	if (end - begin == 0)
		return;

	//3. 定義中間變量，將數(shù)組分半【如果有7個(gè)元素，下標(biāo)0-6，則middle=3，數(shù)組分為長度為4和3的兩段】
	int middle = ((end - begin) / 2 ) + begin;
	//4. 遞歸，先遞歸左半邊，再遞歸右半邊，將左右子序列不斷分為長度為1的子序列才停止遞歸
	MergeSort(numbers, length, temp, begin, middle);
	MergeSort(numbers, length, temp, middle + 1, end);
	//5. 再慢慢歸并
	Merge(numbers, length, temp, begin, end, middle);
}

void Merge(int numbers[], int length, int temp[], int begin, int end, int middle)
{
	//1. 判斷是否有不符合要求的參數(shù)傳入，有則拋出錯(cuò)誤
	if (numbers == nullptr || length <= 0 || begin < 0 || end >= length)
		throw new exception("Invalid input.");

	//2. 將原序列從中分開
	int leftIndex = begin;		//左邊序列的開始（左邊序列的結(jié)尾是middle）
	int rightIndex = middle + 1;//右邊序列的開始（右邊序列的結(jié)尾是end）
	int tempIndex = begin;		//輔助數(shù)組的下標(biāo)
	//3. 當(dāng)左右子序列尚未到頭時(shí)，循環(huán)
	while (leftIndex <= middle && rightIndex <= end)
	{
		//4. 兩兩對(duì)比判斷，誰大誰就放入輔助數(shù)組，同時(shí)指針后移
		if (numbers[leftIndex] < numbers[rightIndex])
			temp[tempIndex] = numbers[leftIndex++];
		else
			temp[tempIndex] = numbers[rightIndex++];
		//5. 輔助數(shù)組下標(biāo)++
		++tempIndex;
	}

	//6. 當(dāng)左邊或右邊子序列尚未到頭時(shí)，直接放入輔助數(shù)組
	while (leftIndex <= middle)
		temp[tempIndex++] = numbers[leftIndex++];

	while (rightIndex <= end)
		temp[tempIndex++] = numbers[rightIndex++];

	//7. 再將輔助數(shù)組中已經(jīng)有序的元素覆蓋掉原數(shù)組中無序的元素，使原數(shù)組變成部分有序
	for (int i = begin; i <= end; ++i)
		numbers[i] = temp[i];
}

int main(int arvc, char* argv[])
{
	const int length = 9;
	int nums[length] = { 18, 7, 23, 3, 9, 32, 10 , 99, 0};
	int *temp = new int[length];

	MergeSort(nums, length, temp, 0, 8);

	for (int i = 0; i < length; i++)
		cout << nums[i] << "  ";

	delete[] temp;
	temp = nullptr;
	cout << endl;
	return 0;
}

多路

同理，將多個(gè)有序表合并，稱為多路歸并，和二路歸并幾乎一樣，就不贅述了，

非比較類

計(jì)數(shù)排序

計(jì)數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

找出待排序的數(shù)組中最大和最小的元素；
統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)；
對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加；
反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1。

#include <iostream>
using namespace std;
const int MAXN = 1000;
int arr[MAXN];

void counting_sort(int n)
{
	int min_value = 0x3f3f3f3f, max_value = 0;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max_value)
			max_value = arr[i];
		if (arr[i] < min_value)
			min_value = arr[i];
	}
	int len = max_value - min_value + 1;
	int* bucket = new int[len]();
	for (int i = 0; i < n; i++)
	{
		bucket[arr[i] - min_value]++;
	}
	for (int i = 0, j = 0; i < len; i++)
	{
		while (bucket[i] != 0)
		{
			arr[j++] = i + min_value;
			bucket[i]--;
		}
	}
	delete bucket;
}

int main()
{
	int n;
	cout << "請(qǐng)輸入數(shù)組中元素的個(gè)數(shù)：";
	cin >> n;
	cout << "請(qǐng)輸入元素: " << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	cout << "排序前：" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	counting_sort(n);
	cout << "排序后：" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

時(shí)間復(fù)雜度是O(n+k)，空間復(fù)雜度也是O(n+k)，其排序速度快于任何比較排序算法。當(dāng)k不是很大并且序列比較集中時(shí)，計(jì)數(shù)排序是一個(gè)很有效的排序算法。

桶排序

桶排序是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排）。

設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；
遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去；
對(duì)每個(gè)不是空的桶進(jìn)行排序；
從不是空的桶里把排好序的數(shù)據(jù)拼接起來。

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000;
const int BUCKET_SIZE = 10;//默認(rèn)每個(gè)桶的范圍
int arr[MAXN];

void insert_sort(vector<int> &v){
	int len=v.size(),temp,i,j;
	for(i=1;i<len;i++){
		temp = v[i];
		for(j=i;j>0 && v[j-1]>temp;j--){
			v[j]=v[j-1];
		}
		v[j]=temp;
	}
}

void bucket_sort(int n){
	int min_value = 0x3f3f3f3f, max_value = 0;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max_value)
			max_value = arr[i];//獲取輸入數(shù)據(jù)的最大值
		if (arr[i] < min_value)
			min_value = arr[i];//獲取輸入數(shù)據(jù)的最小值
	}
	//桶的初始化
	int len = (max_value-min_value)/BUCKET_SIZE+1;
	vector<int> bucket[len];
	//將數(shù)據(jù)分配到桶
	for(int i=0;i<n;i++){
		bucket[(arr[i]-min_value)/BUCKET_SIZE].push_back(arr[i]);
	}
	for(int i=0,j=0;i<len;i++){
		//這里建議使用插入排序或者計(jì)數(shù)排序。當(dāng)然也可以使用堆排序，快速排序等等
		insert_sort(bucket[i]);
		for(auto x:bucket[i]){
			arr[j++]=x;
		}
	}
}

int main(){
	int n;
	cout << "請(qǐng)輸入數(shù)組中元素的個(gè)數(shù)：";
	cin >> n;
	cout << "請(qǐng)輸入元素: " << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	cout << "排序前：" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	bucket_sort(n);
	cout << "排序后：" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

桶排序最好情況下使用線性時(shí)間O(n)，桶排序的時(shí)間復(fù)雜度，取決與對(duì)各個(gè)桶之間數(shù)據(jù)進(jìn)行排序的時(shí)間復(fù)雜度，因?yàn)槠渌糠值臅r(shí)間復(fù)雜度都為O(n)。很顯然，桶劃分的越小，各個(gè)桶之間的數(shù)據(jù)越少，排序所用的時(shí)間也會(huì)越少。是一個(gè)用空間換時(shí)間的算法

基數(shù)排序

基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前。

取得數(shù)組中的最大數(shù)，并取得位數(shù)；
arr為原始數(shù)組，從最低位開始取每個(gè)位組成r數(shù)組；
對(duì)r進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；

#include <iostream>
#include <queue>
using namespace std;
using namespace std;
const int MAXN = 1000;
int arr[MAXN];
queue<int> q[10];

void radix_sort(int n)
{
	//獲取最大值的位數(shù)
	int max_value = 0;
	for (int i = 0; i < n; i++)
	{
		if (max_value < arr[i])
			max_value = arr[i];
	}
	int max_digit = 0;
	while (max_value)
	{
		max_digit++;
		max_value /= 10;
	}
	//開始排序
	int mod = 10, dev = 1;
	for (int i = 0; i < max_digit; i++, mod *= 10, dev *= 10)
	{
		for (int j = 0; j < n; j++)
		{
			int ix = arr[j] % mod / dev;
			q[ix].push(arr[j]);
		}
		int pos = 0;
		for (int j = 0; j < 10; j++)
		{
			while (!q[j].empty())
			{
				arr[pos++] = q[j].front();
				q[j].pop();
			}
		}
	}
}

int main()
{
	int n;
	cout << "請(qǐng)輸入數(shù)組中元素的個(gè)數(shù)：";
	cin >> n;
	cout << "請(qǐng)輸入元素: " << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	cout << "排序前：" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	radix_sort(n);
	cout << "排序后：" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

基數(shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。但基數(shù)排序的性能比桶排序要略差，每一次關(guān)鍵字的桶分配都需要O(n)的時(shí)間復(fù)雜度，而且分配之后得到新的關(guān)鍵字序列又需要O(n)的時(shí)間復(fù)雜度。假如待排數(shù)據(jù)可以分為d個(gè)關(guān)鍵字，則基數(shù)排序的時(shí)間復(fù)雜度將是O(d*2n) ，當(dāng)然d要遠(yuǎn)遠(yuǎn)小于n，因此基本上還是線性級(jí)別的。基數(shù)排序的空間復(fù)雜度為O(n+k)，其中k為桶的數(shù)量。一般來說n>>k，因此額外空間需要大概n個(gè)左右。