C++線性時光的排序算法剖析。本站提示廣大學習愛好者：（C++線性時光的排序算法剖析）文章只能為提供參考，不一定能成為您想要的結果。以下是C++線性時光的排序算法剖析正文
後面的文章曾經引見了幾種排序算法，如拔出排序（直接拔出排序，折半拔出排序，希爾排序）、交流排序（冒泡排序，疾速排序）、選擇排序（簡略選擇排序，堆排序）、2-路合並排序（可以參考前一篇文章：各類外部排序算法的完成）等，這些排序算法都有一個配合的特色，就是基於比擬。
本文將引見三種非比擬的排序算法：計數排序，基數排序，桶排序。它們將沖破比擬排序的Ω(nlgn)下界，以線性時光運轉。
1、比擬排序算法的時光下界
所謂的比擬排序是指經由過程比擬來決議元素間的絕對順序。
“定理：關於含n個元素的一個輸出序列，任何比擬排序算法在最壞情形下，都須要做Ω(nlgn)次比擬。”
也就是說，比擬排序算法的運轉速度不會快於nlgn，這就是基於比擬的排序算法的時光下界。
經由過程決議計劃樹（Decision-Tree）可以證實這個定理，關於決議計劃樹的界說和證實進程在這裡就不贅述了。讀者可以本身去查找材料，這裡推舉年夜家看一看麻省理工學院地下課：算法導論的《MIT地下課：線性時光排序》。
依據下面的定理，我們曉得任何比擬排序算法的運轉時光不會快於nlgn。那末我們能否可以沖破這個限制呢？固然可以，接上去我們將引見三種線性時光的排序算法，它們都不是經由過程比擬來排序的，是以，下界Ω(nlgn)對它們不實用。
2、計數排序（Counting Sort）
計數排序的根本思惟就是對每個輸出元素x，肯定小於x的元素的個數，如許便可以把x直接放在它在終究輸入數組的地位上，例如：
算法的步調年夜致以下：
①.找出待排序的數組中最年夜和最小的元素
②.統計數組中每一個值為i的元素湧現的次數，存入數組C的第i項
③.對一切的計數累加（從C中的第一個元素開端，每項和前一項相加）
④.反向填充目的數組：將每一個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1
C++代碼以下：
/*************************************************************************
> File Name: CountingSort.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
using namespace std;
/*
*計數排序：A和B為待排和目的數組，k為數組中最年夜值,len為數組長度
*/
void CountingSort(int A[], int B[], int k, int len)
{
int C[k+1];
for(int i=0; i<k+1; ++i)
C[i] = 0;
for(int i=0; i<len; ++i)
C[A[i]] += 1;
for(int i=1; i<k+1; ++i)
C[i] = C[i] + C[i-1];
for(int i=len-1; i>=0; --i)
{
B[C[A[i]]-1] = A[i];
C[A[i]] -= 1;
}
}
/* 輸入數組 */
void print(int arr[], int len)
{
for(int i=0; i<len; ++i)
cout << arr[i] << " ";
cout << endl;
}
/* 測試 */
int main()
{
int origin[8] = {4,5,3,0,2,1,15,6};
int result[8];
print(origin, 8);
CountingSort(origin, result, 15, 8);
print(result, 8);
return 0;
}
當輸出的元素是0到k之間的整數時，時光龐雜度是O(n+k)，空間龐雜度也是O(n+k)。當k不是很年夜而且序列比擬集中時，計數排序是一個很有用的排序算法。計數排序是一個穩固的排序算法。
能夠你會發明，計數排序仿佛饒了點彎子，好比當我們方才統計出C，C[i]可以表現A中值為i的元素的個數，此時我們直接次序地掃描C，便可以求出排序後的成果。切實其實是如許，不外這類辦法不再是計數排序，而是桶排序，確實地說，是桶排序的一種特別情形。
3、桶排序（Bucket Sort）
桶排序（Bucket Sort）的思惟是將數組分到無限數目的桶子裡。每一個桶子再個體排序（有能夠再應用其余排序算法）。當要被排序的數組內的數值是平均分派的時刻，桶排序可以以線性時光運轉。桶排序進程動畫演示：Bucket Sort，桶排序道理圖以下：
C++代碼以下：
/*************************************************************************
> File Name: BucketSort.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
using namespace std;
/* 節點 */
struct node
{
int value;
node* next;
};
/* 桶排序 */
void BucketSort(int A[], int max, int len)
{
node bucket[len];
int count=0;
for(int i=0; i<len; ++i)
{
bucket[i].value = 0;
bucket[i].next = NULL;
}
for(int i=0; i<len; ++i)
{
node *ist = new node();
ist->value = A[i];
ist->next = NULL;
int idx = A[i]*len/(max+1); // 盤算索引
if(bucket[idx].next == NULL)
{
bucket[idx].next = ist;
}
else /* 按年夜小次序拔出鏈表響應地位 */
{
node *p = &bucket[idx];
node *q = p->next;
while(q!=NULL && q->value <= A[i])
{
p = q;
q = p->next;
}
ist->next = q;
p->next = ist;
}
}
for(int i=0; i<len; ++i)
{
node *p = bucket[i].next;
if(p == NULL)
continue;
while(p!= NULL)
{
A[count++] = p->value;
p = p->next;
}
}
}
/* 輸入數組 */
void print(int A[], int len)
{
for(int i=0; i<len; ++i)
cout << A[i] << " ";
cout << endl;
}
/* 測試 */
int main()
{
int row[11] = {24,37,44,12,89,93,77,61,58,3,100};
print(row, 11);
BucketSort(row, 235, 11);
print(row, 11);
return 0;
}
4、基數排序（Radix Sort）
基數排序（Radix Sort）是一種非比擬型排序算法，它將整數按位數切割成分歧的數字，然後按每一個位分離停止排序。基數排序的方法可以采取MSD（Most significant digital）或LSD（Least significant digital），MSD是從最高有用位開端排序，而LSD是從最低有用位開端排序。
固然我們可以采取MSD方法排序，按最高有用位停止排序，將最高有用位雷同的放到一堆，然後再按下一個有用位對每一個堆中的數遞歸地排序，最初再將成果歸並起來。然則，如許會發生許多中央堆。所以，平日基數排序采取的是LSD方法。
LSD基數排序完成的根本思緒是將一切待比擬數值（正整數）同一為異樣的數位長度，數位較短的數後面補零。然後，從最低位開端，順次停止一次排序。如許從最低位排序一向到最高位排序完成今後, 數列就釀成一個有序序列。須要留意的是，對每個數位停止排序的算法必需是穩固的，不然就會撤消前一次排序的成果。平日我們應用計數排序或許桶排序作為基數排序的幫助算法。基數排序進程動畫演示：Radix Sort
C++完成（應用計數排序）以下：
/*************************************************************************
> File Name: RadixSort.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
using namespace std;
// 找出整數num第n位的數字
int findIt(int num, int n)
{
int power = 1;
for (int i = 0; i < n; i++)
{
power *= 10;
}
return (num % power) * 10 / power;
}
// 基數排序（應用計數排序作為幫助）
void RadixSort(int A[], int len, int k)
{
for(int i=1; i<=k; ++i)
{
int C[10] = {0}; // 計數數組
int B[len]; // 成果數組
for(int j=0; j<len; ++j)
{
int d = findIt(A[j], i);
C[d] += 1;
}
for(int j=1; j<10; ++j)
C[j] = C[j] + C[j-1];
for(int j=len-1; j>=0; --j)
{
int d = findIt(A[j], i);
C[d] -= 1;
B[C[d]] = A[j];
}
// 將B中排好序的拷貝到A中
for(int j=0; j<len; ++j)
A[j] = B[j];
}
}
// 輸入數組
void print(int A[], int len)
{
for(int i=0; i<len; ++i)
cout << A[i] << " ";
cout << endl;
}
// 測試
int main()
{
int A[8] = {332, 653, 632, 5, 755, 433, 722, 48};
print(A, 8);
RadixSort(A, 8, 3);
print(A, 8);
return 0;
}
基數排序的時光龐雜度是 O(k·n)，個中n是排序元素個數，k是數字位數。留意這不是說這個時光龐雜度必定優於O(nlgn)，由於n能夠具有比擬年夜的系數k。
別的，基數排序不只可以對整數排序，也能夠對有多個症結字域的記載停止排序。例如，依據三個症結字年、月、日來對日期停止排序。
