原視頻為左程云的B站教學(xué)

1 冒泡排序 O ( N 2 ) O(N^2) O(N2)（與數(shù)據(jù)狀況無關(guān)）

外層循環(huán)：n個(gè)數(shù)需要冒n-1個(gè)泡上去，剩下的一個(gè)必然是最小的。所以外層循環(huán)執(zhí)行n-1輪
內(nèi)層循環(huán)：比大小，第1個(gè)泡需要比n-1次，第2個(gè)泡,比較n-2次…

#incldue <vector>
#include <utility>
void bubbleSort(std::vector<int>& arr) 
{
    for (int i = 0; i < arr.size() - 1; i++) {
        for (int j = 0; j < arr.size() - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相鄰元素兩兩對(duì)比
				std::swap(arr[j], arr[j+1]);
            }
        }
    }
}

2 選擇排序 O ( N 2 ) O(N^2) O(N2)（與數(shù)據(jù)狀況無關(guān)）

選擇： 每次從待排序序列中選擇最小的一個(gè)放在已排序序列的后一個(gè)位置

#include <vector>
#include <utility>
void selectionSort(std::vector<int>& arr){
	int len = arr.size();
	if (arr.empty() || len < 2) return;

	for (int i = 0; i < len -1; i++) { 		// len -1 位置不用再選了，沒得選
		int minIndex = i;		
		for (int j = i + 1; j < len; j++) {	// 在[i+1,len-1]上尋找最小值的下標(biāo)
			minIndex = arr[j] < arr[minIndex] ? j : minIndex;
		}
		std::swap(arr[minIndex], arr[i]);
	}
}

3 插入排序 O ( N 2 ) O(N^2) O(N2)（與數(shù)據(jù)狀況相關(guān)）

原理類似于對(duì)撲克牌手牌進(jìn)行排序的過程。將未排序的元素逐個(gè)插入到已排序部分的合適位置。

邏輯順序?yàn)橄茸龅?~0有序， 然后0~1有序， 0~2 … 0~n-1有序

算法流程為：

• 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序。
• 從未排序部分取第一個(gè)值，插入到已排序部分的適當(dāng)位置。這個(gè)位置的選取方式為：把當(dāng)前未排序值與左鄰值對(duì)比，如果更小則交換位置。直到遇到邊界或不比左鄰值小則結(jié)束。（內(nèi)循環(huán)：找適當(dāng)位置插入）
• 重復(fù)步驟2，直到所有元素都被插入到已排序序列中。（外循環(huán)：遍歷每個(gè)未排序的數(shù)）

這個(gè)不像冒泡排序和選擇排序是固定操作(數(shù)據(jù)狀況無關(guān))。插入排序中，如果給的就是有序的，那就外層每層循環(huán)做一次比較就完成了，所以會(huì)是O(N), 但我們說時(shí)間復(fù)雜度都是 worst case 所以還是 $O(N^2)$

#include <vector>
#include <utility>
void insertionSort(std::vector<int>& arr)
{
	int len = arr.size();
	if (arr.empty() || len < 2) return;
	// 0~0已經(jīng)有序了
	for (int i = 1; i < len; i++){ 	// 0~i做到有序
		// 把當(dāng)前值(j+1)對(duì)比左鄰值(j)，比他小則交換，不滿足循環(huán)條件則說明找到合適位置了
		for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--){ 
			std::swap(arr[j+1], arr[j]);
		}
	}
}

在內(nèi)層循環(huán)中，我們將當(dāng)前元素 arr[j + 1] 與其左鄰元素 arr[j] 進(jìn)行比較，更小則換位，直到找到合適的插入位置。
循環(huán)結(jié)束（找到合適的位置）條件為：達(dá)到左邊界 or 當(dāng)前值比左鄰值大

繼續(xù)往下看建議先掌握 二分查找和基礎(chǔ)遞歸

4 歸并排序 O ( N l o g N ) O(NlogN) O(NlogN)（數(shù)據(jù)狀況無關(guān)）

它的核心思想是將待排序的序列不斷劃分成更小的子序列，直到每個(gè)子序列只有一個(gè)元素，然后再將這些子序列兩兩合并，直到最終整個(gè)序列有序。

下面是歸并排序的一般步驟：

• 分割：將待排序的序列從中間位置分割成兩個(gè)子序列，不斷遞歸地將每個(gè)子序列繼續(xù)分割，直到每個(gè)子序列只剩下一個(gè)元素。
• 合并：將兩個(gè)有序的子序列合并成一個(gè)有序序列。從兩個(gè)子序列的第一個(gè)元素開始比較，將較小的元素放入臨時(shí)數(shù)組中，并將對(duì)應(yīng)子序列的索引向后移動(dòng)一位，直到其中一個(gè)子序列的元素全部放入臨時(shí)數(shù)組中。然后將另一個(gè)子序列的剩余元素直接放入臨時(shí)數(shù)組中。
• 重復(fù)合并：重復(fù)進(jìn)行合并操作，直到所有子序列都合并為一個(gè)有序序列。

始終都是 O(NlogN) 的時(shí)間復(fù)雜度，與數(shù)據(jù)無關(guān)。雖然相對(duì)前面的冒泡、選擇、插入排序更快，但是空間復(fù)雜度為O(N)

#include <vector>
#include <utility>
// 第二階段：merge階段時(shí)，L~M 和 M~R 之間的數(shù)必然有序
void merge(std::vector<int>& arr, int L, int M, int R)
{
	std::vector help(R - L + 1);
	int i = 0;		// 臨時(shí)數(shù)組的起始索引
	int p1 = L;		// 左半部分的起始索引
	int p2 = M + 1;	// 右半部分的起始索引

	//外排序，把兩個(gè)子數(shù)組中的元素從小到大放到help數(shù)組
	while (p1 <= M && p2 <= R){ 
		help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
	}

 	// 如果左邊部分還有剩的，全部依次加到help的末尾
	while (p1 <= M){
		help[i++] = arr[p1++];
	}
	// 同理如果右邊還有剩的
	while (p2 <= R){ 
		help[i++] = arr[p2++];
	}

	// 結(jié)束，把臨時(shí)數(shù)組的內(nèi)容覆蓋到原數(shù)組中
	for (i = 0; i < R - L + 1; i++){
		arr[L + i] = help[i]; // 注意arr從L位置開始寫入的
	}
}

// 第一階段拆分
void mergeSort(std::vector<int>& arr, int L, int R)
{
	if (L == R) return;	// 拆分完畢，不能再拆了
	
	int mid = L + ((R - L) >> 1);
	mergeSort(arr, L, mid);
	mergeSort(arr, mid+1, R);
	merge(arr, L, mid, R);  
}

時(shí)間復(fù)雜度（參考2.1 master公式）

• $T(N)=2?T(\frac{N}{2})+O(N)$
• a = 2; b = 2; d = 1
• $lo{g}_{a}b=1=d$，所以時(shí)間復(fù)雜度為$O(N?logN)$

空間復(fù)雜度：$O(N)$ 。因?yàn)槊看蝝erge的時(shí)候開辟一塊空間，大小為N

4.1 擴(kuò)展：求數(shù)組小和

題目：在一個(gè)數(shù)組中，每一個(gè)數(shù)左邊比當(dāng)前數(shù)小的數(shù)累加起來，叫做這個(gè)數(shù)組的小和。求一個(gè)數(shù)組的小和。
例子：[1,3,4,2,5]
1左邊比1小的數(shù)，無
3左邊比3小的數(shù)，1
4左邊比4小的數(shù)，1、3
2左邊比2小的數(shù)，1
5左邊比5小的數(shù)，1、3、4、2
所以小和為1+1+3+1+1+3+4+2=16

要求時(shí)間復(fù)雜度O(NlogN)，空間復(fù)雜度O(N)

• 如果每個(gè)位置的元素都遍歷一遍左邊所有元素，找出比它小的數(shù)，求和，很簡單就能得到結(jié)果，時(shí)間復(fù)雜度為$O(N^2)$
• 轉(zhuǎn)變思維：不是找左邊有多少比當(dāng)前位置的數(shù)更小的數(shù)，然后求和，而是統(tǒng)計(jì)右邊有多少個(gè)比當(dāng)前位置的數(shù)更大的數(shù)，當(dāng)前數(shù)就該累加多少次，而這個(gè)過程在歸并排序中的外排序中就可以做到。
• 歸并排序過程中，從下往上看，每次合并兩個(gè)有序數(shù)組時(shí)，就能知道每個(gè)數(shù)的當(dāng)前比他大的數(shù)有多少個(gè)，然后累加，歸并排序結(jié)束，則小和也計(jì)算結(jié)束

具體講解視頻精準(zhǔn)空降，比看文字可好多了

#include <iostream>
#include <vector>

// 左右兩組合并
long long merge(std::vector<int>& arr, int left, int mid, int right) 
{
    std::vector<int> temp(right - left + 1); // 臨時(shí)數(shù)組用于存儲(chǔ)合并后的結(jié)果
    int i = 0; // 臨時(shí)數(shù)組的起始索引
    int p1 = left; // 左半部分的起始索引
    int p2 = mid + 1; // 右半部分的起始索引
    long long count = 0; // 記錄小和的累加和

    while (p1 <= mid && p2 <= right) {
    	// 只有在左組比右組小時(shí)產(chǎn)生小和
    	count += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
		
		help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }

    while (p1 <= mid) temp[i++] = arr[p1++];
    while (p2 <= right) temp[i++] = arr[p2++];

    // 將臨時(shí)數(shù)組的結(jié)果復(fù)制回原數(shù)組
    for (i = 0; i < R - L + 1; i++) {
        arr[left + i] = temp[i];
    }

    return count;
}

long long process(std::vector<int>& arr, int left, int right) 
{
    if (left >= right) {
        return 0;
    }
    int mid = left + ((right - left) >> 1);
    long long leftCount = process(arr, left, mid); // 左半部分的小和
    long long rightCount = process(arr, mid + 1, right); // 右半部分的小和
    long long mergeCount = merge(arr, left, mid, right); // 左右側(cè)merge過程中產(chǎn)生的小和

    return leftCount + rightCount + mergeCount; // 總的小和
}

long long calculateSmallSum(std::vector<int>& arr) 
{
    if (arr == nullptr || arr.size() < 2) 
    	return 0;

    return process(arr, 0, arr.size() - 1);
}
int main() 
{
    std::vector<int> arr = {3, 1, 4, 2, 5};
    long long smallSum = calculateSmallSum(arr);
    std::cout << "Small Sum: " << smallSum << std::endl;
    return 0;
}

4.2 擴(kuò)展：求數(shù)組中逆序?qū)Φ臄?shù)量

一個(gè)數(shù)組為3，2，4，5，0，則逆序?qū)?code>{(3,2), (3,0), (2,0), (4,0), (5,0)}5對(duì)。

這個(gè)題與4.1完全等效。4.1求的是右邊有多少個(gè)數(shù)比當(dāng)前元素大，而這里需要求的是右邊
有多少個(gè)數(shù)比當(dāng)前數(shù)更小。右邊有多少個(gè)小的數(shù)，就能跟當(dāng)前數(shù)組成多少個(gè)逆序?qū)Α?/p>

5 快速排序 O ( N l o g N ) O(NlogN) O(NlogN)

3.0版本快排，隨機(jī)選擇中樞值，并放到數(shù)組末尾。后面的流程與正?？炫畔嗤?。比較詳細(xì)的文章請(qǐng)參考這里

#include <iostream>
#include <vector>
#include <random> // 包含隨機(jī)數(shù)生成器的頭文件
#include <utility>

// 隨機(jī)選擇中樞元素
int selectPivot(std::vector<int>& arr, int low, int high) 
{
    // 創(chuàng)建一個(gè)隨機(jī)數(shù)引擎
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(low, high); // 創(chuàng)建一個(gè)分布，指定范圍
    
    int randomIndex = dis(gen); // 生成一個(gè)隨機(jī)索引
    std::swap(arr[randomIndex], arr[high]); // 將中樞元素放在數(shù)組末尾
    
    return arr[high];
}

// 快速排序函數(shù)
void quickSort(std::vector<int>& arr, int low, int high) 
{
    if (low < high) {
        // 選取樞軸元素----如果是基礎(chǔ)快排，這里直接選擇第1個(gè)或最后一個(gè)作為中樞即可
        int pivot = selectPivot(arr, low, high);
        
        // 將小于樞軸的元素放在數(shù)組的前面，大于樞軸的元素放在數(shù)組后面
        int i = low - 1; // i充當(dāng)一個(gè)指針，指向數(shù)組的前面部分
        for (int j = low; j < high; ++j) {
            if (arr[j] < pivot) {
                ++i;
                std::swap(arr[i], arr[j]);
            }
        }
        // 最后才將樞軸元素放在正確的位置，i+1左邊的數(shù)都比i位置小，i+1右邊的都比它大
        std::swap(arr[i + 1], arr[high]); 
        
        // 遞歸地對(duì)樞軸左側(cè)和右側(cè)的子數(shù)組進(jìn)行排序
        quickSort(arr, low, i);
        quickSort(arr, i + 2, high);
    }
}

6 堆排序 O ( N l o g N ) O(NlogN) O(NlogN)

更詳細(xì)的講解，請(qǐng)參考此文章

堆結(jié)構(gòu)本身比堆排序的意義更加重大

堆的性質(zhì)：

• 是一棵完全二叉樹
• 每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，為大根堆；反之為小根堆。構(gòu)建大根堆的時(shí)間復(fù)雜度為O(N)
• 一般用數(shù)組來表示。數(shù)組下標(biāo)與堆的邏輯對(duì)應(yīng)關(guān)系
  • 位置 $i$ 的左孩子節(jié)點(diǎn)：$2i+1$
  • 位置 $i$ 的右孩子節(jié)點(diǎn)：$2i+2$
  • 位置 $i$ 的父節(jié)點(diǎn)：$\frac{i?1}{2}$
• 優(yōu)先級(jí)隊(duì)列不是隊(duì)列，是堆

大根堆（可不看）

• 只能保證每個(gè)節(jié)點(diǎn)是以該節(jié)點(diǎn)為根的二叉樹的最大值，其下所有節(jié)點(diǎn)并沒有任何順序可言（左子樹和右子樹的數(shù)沒啥關(guān)系）。
• 主要應(yīng)用是快速獲取一堆數(shù)中的最大值。因?yàn)榇蟾汛_保根節(jié)點(diǎn)是整個(gè)堆中的最大值，所以可以在常數(shù)時(shí)間內(nèi)（O(1)）獲取堆中的最大元素。應(yīng)用包括但不限于：
  • 優(yōu)先隊(duì)列：在優(yōu)先隊(duì)列中，每個(gè)元素都有一個(gè)相關(guān)的優(yōu)先級(jí)，而大根堆允許高優(yōu)先級(jí)的元素優(yōu)先出隊(duì)。所以優(yōu)先級(jí)隊(duì)列不是隊(duì)列，是堆
  • 堆排序：堆排序是一種基于大根堆的排序算法。它使用大根堆來不斷取出最大值并將其放入已排序的部分，從而實(shí)現(xiàn)排序。
  • Top K 問題：尋找一堆數(shù)中的前 K 個(gè)最大值或最小值是一個(gè)常見的問題，大根堆可以幫助高效解決這類問題。
  • 滑動(dòng)窗口問題：需要在一個(gè)移動(dòng)的窗口內(nèi)快速找到最大值或最小值，大根堆可以幫助高效地維護(hù)窗口內(nèi)的元素，并快速獲取最大值或最小值。

堆結(jié)構(gòu)的兩個(gè)操作

• heapInsert： 在已有的大根堆中插入一個(gè)新的元素，從下往上冒。注意新的元素在大根堆范圍的緊后一個(gè)位置索引（比如大根堆是0~9號(hào)索引，則待插入元素應(yīng)該放置在10號(hào)索引位置）

  void heapInsert(std::vector<int>& arr, int index)
  {
  	while (arr[index] > arr[(index - 1) / 2]{
  		swap(arr[index], arr[(index-1) / 2]);
  		index = (index - 1) / 2;
  	}
  }
  

• heapify： 將一個(gè)以 index 為根節(jié)點(diǎn)的子樹或子堆調(diào)整為最大堆，通過不斷調(diào)用這個(gè)函數(shù)，可以將整個(gè)數(shù)組轉(zhuǎn)換為最大堆

  void heapify(std::vector<int>& arr, int index, int heapSize) 
  {
      int largest = index; 
      int left = 2 * index + 1; // 左孩子下標(biāo)
      
      while (left < heapSize){
  		// 兩個(gè)孩子中較大的，下標(biāo)給largest，注意判斷右孩子不能越界，=heapSize是越界
      	largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
  		// 父和孩子比較
  		largest = arr[largest] > arr[index] ? largest : index;
  		if (largest == index)
  			break;
  		swap(arr[largest],arr[index]);
  		index = largest;
  		left = index * 2 + 1;
  }
  

  這段代碼復(fù)雜度為$logN$（完全二叉樹層數(shù)：$ceil(log2(N)+1)$）

堆排序步驟

1. 先把數(shù)組構(gòu)建為大根堆

   • 思路1：從0到N-1由前到后逐步構(gòu)建大根堆，相當(dāng)于每次在已有大根堆范圍新增一個(gè)數(shù)，調(diào)用heapInsert()從下晚上找合適的位置插入，向后擴(kuò)大堆的范圍。構(gòu)建完畢后，heapSize應(yīng)該等于數(shù)組長度
   • 思路2（更快一點(diǎn)）：循環(huán)每次都將堆的范圍逐步向前擴(kuò)展，同時(shí)將當(dāng)前循環(huán)迭代中選擇的數(shù)組元素作為新的根節(jié)點(diǎn)，然后調(diào)用 heapify()進(jìn)行堆的調(diào)整。視頻地址

2. 然后，把數(shù)組0位置（根節(jié)點(diǎn)）的數(shù)與數(shù)組末尾的數(shù)做交換，這里就提取到了第一個(gè)最大值。然后將堆的范圍縮小1，即heapSize–。heapSize用于表示堆的范圍，必須用一個(gè)變量存儲(chǔ)

3. 對(duì)根節(jié)點(diǎn)執(zhí)行heapify()，重新構(gòu)建大根堆

4. 重復(fù)2、3步驟即可升序排好！

void heapInsert(std::vector<int>& arr, int index); // 如果用法2則不需要這個(gè)函數(shù)
void heapify(std::vector<int>& arr, int index, int heapSize);

// 堆排序函數(shù)
void heapSort(std::vector<int>& arr) 
{
	if (arr.size() < 2)
		return;
    // 1.構(gòu)建大根堆(法1)，每次把堆邊界后一個(gè)位置的數(shù)插入堆中（從下往上冒）
	for (int i = 0; i < arr.size(); i++){ // O(N)
		heapInsert(arr, i);	// O(logN)
	}
	// 1.構(gòu)建大根堆(法2)，從后往前，新元素作為根節(jié)點(diǎn)，調(diào)用heapify從上往下找位置放
	for (int i = arr.size() - 1; i >= 0; i--){
		heapify(arr, i, arr.size());
	}
	
	// 2.提出根節(jié)點(diǎn)最大值（與數(shù)組最后一個(gè)元素交換），并縮小堆的邊界
	int heapSize = arr.size(); // 這個(gè)變量必須有，作為堆的邊界
	std::swap(arr[0], arr[--heapSize]; 
	
	// 3.重新構(gòu)建大根堆，除了新來的根節(jié)點(diǎn)，下面的子樹都還是滿足大頂堆的
	while(heapSize > 0){ // O(N)
		heapify(arr, 0, heapSize); 
		std::swap(arr[0], arr[--heapSize]);
	}
}

6.1 擴(kuò)展：小范圍排序 N l o g K NlogK NlogK

題目： 已知一個(gè)幾乎有序的數(shù)組，幾乎有序是指，如果把數(shù)組排好順序的話，每個(gè)元素移動(dòng)的距離可以不超過k，并且k相對(duì)于數(shù)組來說比較小。請(qǐng)選擇一個(gè)合適的排序算法針對(duì)這個(gè)數(shù)據(jù)進(jìn)行排序。

解題思路：

• 整個(gè)數(shù)組的最小值肯定在(0,k-1)范圍，在該范圍構(gòu)建小根堆。把堆頂(最小值)彈出放在數(shù)組位置0上，跟堆排序類似，把緊后位置k上的數(shù)放到小根堆的堆頂
• 調(diào)整位置，重新構(gòu)建小根堆。然后第二小的數(shù)會(huì)出現(xiàn)在堆頂，再把堆頂放在數(shù)組的位置1 上
• 反復(fù)操作，如此彈出堆頂?shù)捻樞蚓褪菙?shù)組排好序的順序。

• 建堆階段：O(K)
• 插入元素階段：從下標(biāo)為k的元素開始，將它們插入到小根堆中。O(logK)，因?yàn)樾「训母叨仁?logK。由于需要插入 N-K 個(gè)元素，所以這個(gè)階段的時(shí)間復(fù)雜度是 O((N-K)logK)。
• 因?yàn)镵相對(duì)N來說足夠小，因此忽略不計(jì)，直接看做$NlogK$

#include <vector>
#include <queue>	 
#include <algorithm> //std::min
void sortedArrDistanceLessK(std::vector<int> arr, int k)
{
	// 默認(rèn)小根堆，即參數(shù)3默認(rèn)為std::less<T>
	std::priority_queue<int, std::vector<int>, std::less<int>> minHeap;
	// 構(gòu)建 O(K)
	int index = 0;
	for (; index < std::min(arr.size(), k); index++){
		minHeap.push(arr[index]);
	}

	int i = 0;
	for (; index < arr.size(); i++; index++){
		minHeap.push(arr[index]);// 把數(shù)組中，堆范圍后的一個(gè)元素壓入，內(nèi)部會(huì)自動(dòng)找位置插入
		arr[i] = minHeap.top(); // 拿到堆頂元素
		minHeap.pop();   		// 彈出堆頂元素后，會(huì)自動(dòng)重新構(gòu)建大根堆
	}
	

	// 彈出剩余的元素
	while (!minHeap.empty()){
		arr[i++] = minHeap.top();
		minHeap.pop(); // 注意這里pop操作之后會(huì)自動(dòng)調(diào)整數(shù)據(jù)布局，以滿足大根堆性質(zhì) 		
	}
}

7 基數(shù)排序 O ( N ) O(N) O(N)

前面介紹的都是基于比較的排序，而這里則是不基于比較的。

計(jì)數(shù)排序(很少用)：對(duì)一定范圍內(nèi)的整數(shù)進(jìn)行排序。它的基本思想是通過統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)(需要輔助數(shù)組，長度與待排序數(shù)組的數(shù)值域范圍相同），然后根據(jù)計(jì)數(shù)結(jié)果將元素按順序放回原數(shù)組，從而實(shí)現(xiàn)排序。不適用于范圍很大甚至沒有范圍的排序，因?yàn)樾枰妮o助數(shù)組太大了。

基數(shù)排序： 必須有進(jìn)制，比計(jì)數(shù)排序好，不需要那么多輔助空間。具體講解視頻跳轉(zhuǎn)鏈接，文字說明在代碼部分的后面

#include <vector>
#include <algorithm>
#include <cmath> // pow()
// 最大值的位數(shù)
int maxbits(std::vector<int> arr)
{
	int max = *std::max_element(arr.begin(), arr.end());
	int bits = 0;
	while (max != 0){
		max /= 10; // 取個(gè)位數(shù)
		bits++;
	}
	return bits;
}
// 獲取數(shù)字 num 的第 bit 位數(shù)字
int getDigit(int num, int bit) {
	// 比如1423 n
    return (num / static_cast<int>(std::pow(10, bit - 1))) % 10;
}

void radixSort(std::vector<int> arr, int L, int R, int maxBits)
{
	cosnt int base = 10; // 基數(shù)為10，即按十進(jìn)制進(jìn)行排序
	int i = 0, j = 0;
	// 桶的長度和原數(shù)組長度相同
	int n = arr.size();
	std::vector<int> tmpArr(n);	
	
	// 這個(gè)bit是當(dāng)前十進(jìn)制位
	for (int bit = 1; bit <= maxBits; bit++){// 有多少位就進(jìn)出多少次
		std::vector<int> count(base, 0);
        // 統(tǒng)計(jì)當(dāng)前bit位上為0~9的的數(shù)分別有多少個(gè)
        for (i = 0; i <= R; i++) {
            j = getDigit(num, bit);	
            count[j]++;
        }
        // 將 count 數(shù)組變?yōu)榇娣琶總€(gè)數(shù)字應(yīng)該放置的位置索引(看說明1)
        // 下標(biāo)0~9分別表示<=當(dāng)前下標(biāo)數(shù)的元素個(gè)數(shù)
		// 比如count[5]，表示數(shù)組中所有數(shù)，在當(dāng)前bit位上的數(shù)<=5的個(gè)數(shù)
        for (i = 1; i < base; i++) {
            count[i] += count[i - 1];
        }
        // 原數(shù)組的數(shù)按當(dāng)前位進(jìn)行一次排序，放入臨時(shí)數(shù)組，從右往左遍歷原數(shù)組（看說明2）
        for (int i = n - 1; i >= 0; i--) {
            j = getDigit(arr[i], bit);
            tmpArr[count[j] - 1] = arr[i];
            count[j]--;
        }
        // 將排好序的臨時(shí)數(shù)組tmpArr拷貝回原數(shù)組 arr
        //std::copy(tmpArr.begin(), tmpArr.end(), arr.begin() + L);
        for (i = L, j = 0; i <= R; i++, j++){
        	arr[i] = tmpArr[j];
        }
	}
}
// 僅用于非負(fù)數(shù)排序
void radixSort(std::vector<int> arr)
{
	if (arr.size() < 2)
		return;
	radixSort(arr, 0, arr.size() - 1, maxbits(arr)); // 重載版本的sort
}

說明1： 計(jì)算每個(gè)數(shù)字在排序后應(yīng)該放在哪個(gè)位置，說白了就是對(duì)原數(shù)組針對(duì)當(dāng)前bit位做一次排序，里每個(gè)元素代表了該數(shù)字在排序后的位置的右邊界索引（排名）。

說明2： 通常基數(shù)排序算法是自右向左的，學(xué)術(shù)上稱之為“最低位優(yōu)先（Least significant digital，LSD）”，能保證基數(shù)排序是穩(wěn)定的，高位優(yōu)先也能保證穩(wěn)定，但寫起來非常麻煩。

舉例說明（結(jié)合代碼看）： 當(dāng)對(duì)數(shù)組 { 170, 045, 075, 090, 802,0 24, 002, 066 } 進(jìn)行基數(shù)排序時(shí)，數(shù)組中最大的數(shù)字是 802，它有3位。

• 初始狀態(tài)下，count 數(shù)組初始化為全零：count: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
• 第一輪排序（個(gè)位）：
  • 統(tǒng)計(jì)個(gè)位數(shù)字出現(xiàn)的次數(shù)：count: { 2, 2, 0, 1, 2, 1, 0, 0, 0, 0 }
  • 轉(zhuǎn)換為每個(gè)數(shù)字應(yīng)該放置的位置索引：count: { 2, 4, 4, 5, 7, 8, 8, 8, 8, 8 }
  • 排序結(jié)果：arr: { 170, 90, 802, 2, 24, 45, 75, 66 }
• 第二輪排序（十位）：
  • 統(tǒng)計(jì)十位數(shù)字出現(xiàn)的次數(shù)：count: { 0, 2, 0, 0, 1, 0, 1, 2, 1, 1 }
  • 轉(zhuǎn)換為每個(gè)數(shù)字應(yīng)該放置的位置索引：count: { 0, 2, 2, 2, 3, 3, 4, 6, 7, 8 }
  • 排序結(jié)果：arr: { 802, 2, 24, 45, 66, 170, 75, 90 }
• 第三輪排序（百位）：
  • 統(tǒng)計(jì)百位數(shù)字出現(xiàn)的次數(shù)：count: { 6, 1, 0, 0, 0, 0, 0, 0, 1, 0 }
  • 轉(zhuǎn)換為每個(gè)數(shù)字應(yīng)該放置的位置索引：count: { 6, 7, 7, 7, 7, 7, 7, 7, 8, 0 }
  • 排序結(jié)果：arr: { 2, 24, 45, 66, 75, 90, 170, 802 }

在每一輪排序中，count 數(shù)組統(tǒng)計(jì)了當(dāng)前位上數(shù)字出現(xiàn)的次數(shù)，并轉(zhuǎn)換為每個(gè)數(shù)字在排序后的位置索引。然后，根據(jù) count 數(shù)組的統(tǒng)計(jì)結(jié)果，將原數(shù)組中的元素按照當(dāng)前位的值放入臨時(shí)數(shù)組 tmpArr中。最后，將排好序的 tmpArr拷貝回原數(shù)組 arr，完成一輪排序。在所有位都排序完畢后，數(shù)組 arr 就是有序的。文章來源地址http://www.zghlxwxcb.cn/news/detail-509096.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法C++實(shí)現(xiàn)】3、排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！