時間復(fù)雜度是 O(n) 的排序算法：桶排序、計數(shù)排序、基數(shù)排序，也稱線性排序，他們都不是基于比較的排序算法。

一、桶排序

1、基本思想

將要排序的數(shù)據(jù)分到幾個有序的桶里，每個桶里的數(shù)據(jù)再單獨(dú)進(jìn)行進(jìn)行排序。桶內(nèi)排完序之后，再把每個桶里的數(shù)據(jù)按照順序依次取出，從而形成有序序列。

2、桶排序?qū)σ判驍?shù)據(jù)的要求非常苛刻

• 要排序的數(shù)據(jù)需要很容易就能劃分成 m 個桶，并且，桶與桶之間有著天然的大小順序。 ==》每個桶內(nèi)的數(shù)據(jù)都排序完之后，桶與桶之間的數(shù)據(jù)不需要再進(jìn)行排序。
• 數(shù)據(jù)在各個桶之間的分布是比較均勻的。==》若數(shù)據(jù)不均勻 ==》時間復(fù)雜度就將退化為 O(nlogn) 的排序算法。

3、應(yīng)用

適用于 外部排序。外部排序：數(shù)據(jù)存儲在外部磁盤中，數(shù)據(jù)量比較大，內(nèi)存有限，無法將數(shù)據(jù)全部加載到內(nèi)存中。

示例：有 10GB 的訂單數(shù)據(jù)，我們希望按訂單金額（假設(shè)金額都是正整數(shù)）進(jìn)行排序，但是我們的內(nèi)存有限，只有幾百 MB，沒辦法一次性把 10GB 的數(shù)據(jù)都加載到內(nèi)存中。這個時候該怎么辦呢？

思路：

• 先掃描一遍文件，看訂單金額所處的數(shù)據(jù)范圍。==》1元 ~ 10萬元
• 將所有訂單根據(jù)金額劃分到 100 個桶里，第一個桶我們存儲金額在 1 元到 1000 元之內(nèi)的訂單，第二桶存儲金額在 1001 元到 2000 元之內(nèi)的訂單，以此類推。每一個桶對應(yīng)一個文件，并且按照金額范圍的大小順序編號命名（00，01，02…99）。
  • 理想情況：
    • 訂單金額在 1 到 10 萬之間均勻分布，那訂單會被均勻劃分到 100 個文件中，每個小文件中存儲大約 100MB 的訂單數(shù)據(jù)
    • ==》可以將這 100 個小文件依次放到內(nèi)存中，用快排來排序。
    • ==》 等所有文件都排好序之后，我們只需要按照文件編號，從小到大依次讀取每個小文件中的訂單數(shù)據(jù)，并將其寫入到一個文件中，那這個文件中存儲的就是按照金額從小到大排序的訂單數(shù)據(jù)了。
  • 實(shí)際情況：不均勻分布 ==》針對這些劃分之后還是比較大的文件，繼續(xù)劃分。==》直到所有文件都能讀入內(nèi)存位置。
    • eg：訂單金額在 1 元到 1000 元之間的比較多，我們就將這個區(qū)間繼續(xù)劃分為 10 個小區(qū)間，1 元到 100元，101 元到 200 元，201 元到 300 元…901 元到 1000 元。

4、實(shí)現(xiàn)

#include <iostream> using namespace std;void BucketSort(int *A, int Max, int Size){int B[Max+1];int i,j,count = 0;memset(B, 0, (Max+1)*sizeof(int));for (i = 0; i < Size; i++) {j = A[i];B[j] += 1;}for (i = 0; i <= Max; i++) {if (B[i] > 0) {for (j = 0; j < B[i]; j++) {A[count] = i;count++;}}} }int main(int argc, const char * argv[]) {int A[]={1, 2, 2, 7, 4, 9, 3, 5};// 這里可以用一個O(n)的函數(shù)來實(shí)現(xiàn)，假如數(shù)組的手動輸入的，則在輸入的時候就可以獲取到。// 這里直接賦值是為了排出別的因素，看著簡單。int Max = 9; int Size = sizeof(A)/sizeof(int);BucketSort(A, Max, Size);for (int i = 0; i < Size; i++) {printf("%d ",A[i]);}printf("\n");return 0; }

二、計數(shù)排序(Counting Sort)

1、基本思想

基本思路：通過對待排序序列中的每種元素的個數(shù)進(jìn)行計數(shù)，然后獲得每個元素在排序后的位置的信息的排序算法。

桶排序的特殊情況：桶的大小粒度不一樣，每個桶內(nèi)的數(shù)據(jù)值都是相同，省去了桶內(nèi)排序的時間

2、適用性

只適用于在數(shù)據(jù)范圍不大的場景中，而且只能給非負(fù)整數(shù)排序或在不改變相對大小的情況下可轉(zhuǎn)化為非負(fù)整數(shù)。

3、實(shí)現(xiàn)

#include <iostream> #include <vector> using namespace std;void CountSort(vector<int> &arr, int maxVal) {int len = arr.size();if (len < 1)return;vector<int> count(maxVal+1, 0);vector<int> tmp(arr);for (auto x : arr)count[x]++;for (int i = 1; i <= maxVal; ++i)count[i] += count[i - 1];for (int i = len - 1; i >= 0; --i) {arr[count[tmp[i]] - 1] = tmp[i];count[tmp[i]]--; //注意這里要減1} }int main() {vector<int> arr = { 1,5,3,7,6,2,8,9,4,3,3 };int maxVal = 9;CountSort(arr,maxVal);for (auto x : arr)cout << x << " ";cout << endl;return 0; }

三、基數(shù)排序(Radix Sort)

1、基本思想

基數(shù)排序是桶排序的擴(kuò)展。

基本思想：將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。

具體做法：將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列。

2、不同的情形

• 數(shù)字的排序中，若存在不同長度的問題 ==》在位數(shù)短的前面補(bǔ)零
  
• 字符串的排序，若存在不同長度的問題 ==》位數(shù)不夠的可以在后面補(bǔ)“0”
  • 根據(jù)ASCII 值，所有字母都大于“0”，所以補(bǔ)“0”不會影響到原有的大小順序。
    
• 其他含義序列中，若存在不同長度的問題 ==》具體情況具體分析

總結(jié)

以上是生活随笔為你收集整理的七、排序(3)——线性排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。