可能是你看過最全的十大排序算法詳解(完整版代碼)
前言
兄弟們，應(yīng)上篇數(shù)據(jù)結(jié)構(gòu)的各位要求，今天我開始工作了，開始肝算法，劍指offer還在路上，我真想開車去接它，奈何碼神沒有駕照的開車，算了，弄排序算法吧，有點(diǎn)長，耐心看啊，原創(chuàng)不易，你們懂的，先上一張圖
可以看出排序算法，還是比較多的，算了，不多說了，你我肝完就是出門自帶4年實(shí)習(xí)經(jīng)驗(yàn)的！
交集排序
冒泡
冒泡我一般也將它稱為枚舉就是把所有都走一遍嘛，效率比較低，一般在算法競賽中如果實(shí)在沒有比較好的，可以用，那就先講一個簡單的枚舉吧！
枚舉字典序
首先可能有的同學(xué)不知道什么是字典序，請看：
（1，2，3），（1，3，2）…這就是字典序的體現(xiàn)，官方解釋是這樣的：
字典排序（lexicographical order）是一種對于隨機(jī)變量形成序列的排序方法。其方法是，按照字母順序，或者數(shù)字小大順序，由小到大的形成序列。
比如說有一個隨機(jī)變量X包含{1 2 3}三個數(shù)值。
其字典排序就是{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 1 2} {3 2 1}
如果是字母：先比較第一個字符i和b，b<i，b是第2個，i是第9個2<9于是baray<ilove如果第一位相同，就比較第二位，
例如：abcdd<abcde aaaay<aaaaz如果其中之一是另一個的前綴，則短的那個排前面：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)過下一個
{
a[cur] = i;
print(n, a, cur + 1);//遞歸
}
}
}
}
int main()
{
}下面我們來看一下正宗的冒泡排序，總體思想是：倆倆比較，如果反序交換，直到?jīng)]有反序的記錄為止，代碼實(shí)現(xiàn)比較簡單，是倆個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;
}
總體來說比較簡單，但是耗時，耗內(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ù)雜度：倆個for，就是O（n^2)了，有點(diǎn)大
簡單
選擇排序
先來和冒泡排序比較一下，他倆的主要區(qū)別就是冒泡排序的數(shù)據(jù)在不斷的交換，而快速排序先交換數(shù)據(jù)的別名，再交換本身。打個比喻就是，一個是幻想天上掉餡餅，背水一戰(zhàn)，的炒股短線選手，而另一個則是看中時機(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ù)雜度的話，你會驚訝的發(fā)現(xiàn)時間復(fù)雜度仍舊是O（n^2)，但是我要說的是它仍舊優(yōu)于冒泡排序，why？
冒泡排序和選擇排序是排序算法中比較簡單和容易實(shí)現(xiàn)的算法。冒泡排序的思想為：每一次排序過程，通過相鄰元素的交換，將當(dāng)前沒有排好序中的最大（小）移到數(shù)組的最右（左）端。而選擇排序的思想也很直觀：每一次排序過程，我們獲取當(dāng)前沒有排好序中的最大（?。┑脑睾蛿?shù)組最右（左）端的元素交換，循環(huán)這個過程即可實(shí)現(xiàn)對整個數(shù)組排序。
選擇排序的平均時間復(fù)雜度比冒泡排序的稍低:
同樣數(shù)據(jù)的情況下，2種算法的循環(huán)次數(shù)是一樣的，但選擇排序只有0到1次交換，而冒泡排序只有0到n次交換
快速排序
和冒泡排序相似，但是優(yōu)于冒泡，總體是一個分治的思想，交換軸點(diǎn)元素
- 劃分：將數(shù)組中的元素都重排分成左右倆部分，使得左邊都小于等于右邊的任意元素
- 遞歸求解：把左右分別進(jìn)行排序
- 合并：這時你會發(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ū)間不只一個數(shù)
if(begin < end)
{
int temp = arr[begin]; //將區(qū)間的第一個數(shù)作為基準(zhǔn)數(shù)
int i = begin; //從左到右進(jìn)行查找時的“指針”，指示當(dāng)前左位置
int j = end; //從右到左進(jìn)行查找時的“指針”，指示當(dāng)前右位置
//不重復(fù)遍歷
while(i < j)
{
//當(dāng)右邊的數(shù)大于基準(zhǔn)數(shù)時，略過，繼續(xù)向左查找
//不滿足條件時跳出循環(huán)，此時的j對應(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ù)時，略過，繼續(xù)向右查找
//(重復(fù)的基準(zhǔn)元素集合到左區(qū)間)
//不滿足條件時跳出循環(huán)，此時的i對應(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;
//此時的i即為基準(zhǔn)元素的位置
//對基準(zhǔn)元素的左邊子區(qū)間進(jìn)行相似的快速排序
quickSort(arr,begin,i-1);
//對基準(zhǔn)元素的右邊子區(qū)間進(jìn)行相似的快速排序
quickSort(arr,i+1,end);
}
//如果區(qū)間只有一個數(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ī)上不用插牌了，省時間，這利用的就是插入排序的原理，可以說是“斗地主排序”
基本操作：將一個記錄插入到已經(jīng)排好的有序表中，從而得到一個新的，記錄數(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ī)矩，分析時間復(fù)雜度，最好的情況是順序都是排列好的，此時只需要比較，時間復(fù)雜度為O（n），最壞的情況為O（n^2),平均下來是n ^ 2/4，所以平均時間復(fù)雜度也是O（n ^ 2).
希爾排序
如果說誰是第一個將排序算法復(fù)雜度突破O（n^2)的，那么我想希爾是第一個，可以說希爾排序是對插入排序的改進(jìn)，區(qū)別在于，希爾排序可以說是一個不斷分組的排序
先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，具體算法描述：
選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列個數(shù)k，對序列進(jìn)行k 趟排序；
每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進(jìn)行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
實(shí)現(xiàn)如下：
//希爾排序
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap>1)
{
//每次對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;
}
}
}時間復(fù)雜度，牛逼的人們，通過大量的計(jì)算發(fā)現(xiàn)是O（n^3/2)，小于O
（n^2)，由于是跳躍式的排序所以不是穩(wěn)定排序
選擇排序
簡單選擇排序
可參考上面
堆排序
何為堆，如果已經(jīng)學(xué)過堆的話，就是那個堆，與棧相對的堆，
基本思路：將代排的序列構(gòu)造成一個大堆，此時，整個序列的最大值就是堆頂?shù)母Y(jié)點(diǎn)，將它移走，也就是將其與堆數(shù)組的末尾元素交換，此時末尾元素就是最大值，然后將剩余的n-1個序列重新構(gòu)造成一個堆，這樣就會得到n個元素的次最大值，如此遞歸反復(fù)就會得到一個有序序列
varlen; // 因?yàn)槁暶鞯亩鄠€函數(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;
}時間可以說是主要耗在了初始建堆和在重建堆的反復(fù)篩選上
1.構(gòu)造堆：O（n）
2.重建堆：完全二叉樹：數(shù)據(jù)結(jié)構(gòu)，詳解時間復(fù)雜度為O(nlogn)
又因?yàn)槎雅判驅(qū)υ加涗浀呐判驙顟B(tài)并不敏感，因此它無論是好是壞，時間復(fù)雜度都為O（nlogn)，同希爾排序，都為不穩(wěn)定性的排序
歸并排序
完全二叉樹，是一棵神奇的樹，可以說歸并排序是完全體現(xiàn)了完全二叉樹的性質(zhì)
二路
若將兩個有序表合并成一個有序表，稱為2-路歸并。
- 把長度為n的輸入序列分成兩個長度為n/2的子序列；
- 對這兩個子序列分別采用歸并排序；
- 將兩個排序好的子序列合并成一個最終的排序序列。
#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)相等時，說明子序列中只有一個元素，看作有序的
if (end - begin == 0)
return;
//3. 定義中間變量，將數(shù)組分半【如果有7個元素，下標(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ù)傳入，有則拋出錯誤
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)左右子序列尚未到頭時，循環(huán)
while (leftIndex <= middle && rightIndex <= end)
{
//4. 兩兩對比判斷，誰大誰就放入輔助數(shù)組，同時指針后移
if (numbers[leftIndex] < numbers[rightIndex])
temp[tempIndex] = numbers[leftIndex++];
else
temp[tempIndex] = numbers[rightIndex++];
//5. 輔助數(shù)組下標(biāo)++
++tempIndex;
}
//6. 當(dāng)左邊或右邊子序列尚未到頭時，直接放入輔助數(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;
}
多路
同理，將多個有序表合并，稱為多路歸并，和二路歸并幾乎一樣，就不贅述了，
非比較類
計(jì)數(shù)排序
計(jì)數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。 作為一種線性時間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
- 找出待排序的數(shù)組中最大和最小的元素；
- 統(tǒng)計(jì)數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)；
- 對所有的計(jì)數(shù)累加（從C中的第一個元素開始，每一項(xiàng)和前一項(xiàng)相加；
- 反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個元素就將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 << "請輸入數(shù)組中元素的個數(shù)：";
cin >> n;
cout << "請輸入元素: " << 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;
}時間復(fù)雜度是O(n+k)，空間復(fù)雜度也是O(n+k)，其排序速度快于任何比較排序算法。當(dāng)k不是很大并且序列比較集中時，計(jì)數(shù)排序是一個很有效的排序算法。
桶排序
桶排序是計(jì)數(shù)排序的升級版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個映射函數(shù)的確定。桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排）。
- 設(shè)置一個定量的數(shù)組當(dāng)作空桶；
- 遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個一個放到對應(yīng)的桶里去；
- 對每個不是空的桶進(jìn)行排序；
- 從不是空的桶里把排好序的數(shù)據(jù)拼接起來。
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000;
const int BUCKET_SIZE = 10;//默認(rèn)每個桶的范圍
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 << "請輸入數(shù)組中元素的個數(shù)：";
cin >> n;
cout << "請輸入元素: " << 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;
}桶排序最好情況下使用線性時間O(n)，桶排序的時間復(fù)雜度，取決與對各個桶之間數(shù)據(jù)進(jìn)行排序的時間復(fù)雜度，因?yàn)槠渌糠值臅r間復(fù)雜度都為O(n)。很顯然，桶劃分的越小，各個桶之間的數(shù)據(jù)越少，排序所用的時間也會越少。是一個用空間換時間的算法
基數(shù)排序
基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前。
- 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
- arr為原始數(shù)組，從最低位開始取每個位組成r數(shù)組；
- 對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 << "請輸入數(shù)組中元素的個數(shù)：";
cin >> n;
cout << "請輸入元素: " << 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)的時間復(fù)雜度，而且分配之后得到新的關(guān)鍵字序列又需要O(n)的時間復(fù)雜度。假如待排數(shù)據(jù)可以分為d個關(guān)鍵字，則基數(shù)排序的時間復(fù)雜度將是O(d*2n) ，當(dāng)然d要遠(yuǎn)遠(yuǎn)小于n，因此基本上還是線性級別的。基數(shù)排序的空間復(fù)雜度為O(n+k)，其中k為桶的數(shù)量。一般來說n>>k，因此額外空間需要大概n個左右。
最后
到此這篇關(guān)于十大排序算法的文章就介紹到這了,更多相關(guān)十大排序算法詳解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了VC創(chuàng)建DLL動態(tài)鏈接庫的方法,實(shí)例分析VC創(chuàng)建動態(tài)鏈接庫的完整步驟,需要的朋友可以參考下2015-05-05
在C++中,地址交換通常是指通過指針操作改變兩個變量之間的內(nèi)存地址引用,當(dāng)你有兩個指針分別指向兩個變量時,你可以通過某種機(jī)制交換這兩個指針的內(nèi)容,使得它們各自指向?qū)Ψ皆瓉淼奈恢?本介紹了關(guān)于C++地址交換的實(shí)現(xiàn),需要的朋友可以參考下2024-11-11
這篇文章主要介紹了C++實(shí)現(xiàn)二叉樹遍歷序列的求解方法,需要的朋友可以參考下2014-08-08
通常來說,我們對數(shù)據(jù)庫的操作更多地在于對數(shù)據(jù)庫表的操作,下面這篇文章主要給大家介紹了關(guān)于qt首次連接MYSQL驅(qū)動的各種問題,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-04-04
這篇文章主要為大家詳細(xì)介紹了基于C語言實(shí)現(xiàn)推箱子游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
本文給大家分享的是使用C語言實(shí)現(xiàn)的斗地主游戲的核心算法，主要實(shí)現(xiàn)了面向?qū)ο笤O(shè)計(jì)，洗牌、發(fā)牌、判斷牌型、比較牌的大小、游戲規(guī)則等算法。通過這個斗地主小項(xiàng)目的練習(xí)，提高了我的面向?qū)ο笤O(shè)計(jì)能力，加深了對算法的理解。最近把這些設(shè)計(jì)和算法分享給大家。2015-03-03
這篇文章主要介紹了直接插入排序與折半插入排序，有需要的朋友可以參考一下2013-12-12
string中c_str(),data(),copy(p,n)函數(shù)的用法總結(jié)
以下是對string中c_str(),data(),copy(p,n)函數(shù)的用法進(jìn)行了詳細(xì)的介紹，需要的朋友可以過來參考下2013-09-09
c++之解決char轉(zhuǎn)string時出現(xiàn)的亂碼問題
這篇文章主要介紹了c++之解決char轉(zhuǎn)string時出現(xiàn)的亂碼問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱2022-11-11