這是基數排序ppt，包括了基數排序原理，一種基于分配—收集的排序算法一種穩(wěn)定的排序算法，基數排序算法的具體實現，鏈式的基數排序算法等內容，歡迎點擊下載。

基數排序ppt是由紅軟PPT免費下載網推薦的一款課件PPT類型的PowerPoint.

基數排序(Radix sort) 基數排序原理： 將所有待比較數值（正整數）統(tǒng)一為同樣的數位長度，這里采取數位較短的數前面補零。 從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后， 數列就變成一個有序序列。 基數排序的時間復雜度是 O(n)， 更準確的說是O(kn)，其中n是排序元素個數，k是數字位數。 一種基于分配—收集的排序算法一種穩(wěn)定的排序算法 擴展：穩(wěn)定的排序算法： 計數排序 插入排序 歸并排序 最低位優(yōu)先法： 首先是按照最低有效位數字進行排序，然后再按次低有效位，知道對所有的數字都進行排序。對于d位數來說，僅需d遍就可以將一個數組排好序 Eg1.待排序數組[62，14，59，88，16] 分配10個可重復利用的桶，桶編號為0-9，以個位數數字為桶編號依次入桶，變成下邊這樣 |  0  |  0  | 62 |  0  | 14 |  0  | 16 |  0  |  88 | 59 | |  0  |  1  |  2  |  3  |  4 |  5  |  6  |  7  |  8  |  9  |桶編號 將桶里的數字順序取出來，輸出結果:[62，14，16，88，59] 再次入桶，不過這次以十位數的數字為準，進入相應的桶，變成下邊這樣:由于前邊做了個位數的排序，所以當十位數相等時，個位數字是由小到大的順序入桶的，就是說，入完桶還是有序 |  0  | 14，16 |  0  |  0  |  0  | 59 | 62  | 0  | 88  |  0  | |  0  |  1      |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |桶編號 因為沒有大過100的數字，沒有百位數，所以到這排序完畢，順序取出即可 最后輸出結果:[14，16，59，62，88] 基數排序過程圖示：紅色表示當前正被排序的數位。 void RadixSort(int *list， int begin， int end， int digit) { int radix = 10; //基數 int i = 0， j = 0; int * count = new int[radix]; //存放各個桶的數據存放個數 int * bucket = new int[end - begin + 1]; for (int d = 1; d <= digit; d++) { for ( i = 0; i < radix; i++) count[i] = 0; //置空各個桶的統(tǒng)計數據 for (i = begin; i <= end; i++) { j = getDigit(list[i]， d); count[j]++; } for (i = 1; i < radix; i++) count[i] = count[i] + count[i - 1]; //count[i]表示第i個桶的右邊界索引 //將數據依次裝入桶中，保證數據的穩(wěn)定性，此步即為基數排序的分配 for (i = end; i >= begin; i--) { j = getDigit(list[i]， d); bucket[count[j] - 1] = list[i]; count[j]--; } //基數排序的收集 //把桶中的數據再倒出來 for (i = begin， j = 0; i <= end; i++， j++) list[i] = bucket[j]; } } 其中 //此函數的目的是取得數據每個位上的數值 //i為待取的數據 int getDigit(int i， int d) //d的值為1、2、3...，表示要求取的相應位的值，1表示求取個位， { //2表示十分位，類推 int val; while (d--) { val = i % 10; i /= 10; } return val; } 算法實現中， 我們用了兩個數組：count[radix]， bucket[end-begin+1]。 radix為基數，即桶的個數， 首先用第一個for循環(huán)，count[i]表示第i個桶中裝入了幾個數據， 接著用第二個for循環(huán)，標記在每個桶中，最后一個數據在整個數組中的右邊界。 例如：第一個for循環(huán)結束后，count[0]=1，count[1]=count[2]=0，count[3]=2；在第二個for循環(huán)后，count[0]=1，count[1]=count[2]=1，count[3]=3，表示第三個桶中最后一個元素在數組中第三個位置。 其中 bucket[]的大小與待排序數組大小一樣，是在排序中做收集步驟用。 digit表示各個數據的最大位數。 鏈式的基數排序算法 原理： 1、以靜態(tài)鏈表存儲待排記錄，并令表頭指針指向第一個記錄；  2、“分配” 時，按當前“關鍵字位”所取值，將記錄分配到不同的 “鏈隊列” 中，每個隊列中記錄的 “關鍵字位” 相同； 3、“收集”時，按當前關鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表；  4、對每個關鍵字位均重復 2 和 3 兩步。  Eg3.待排序序列[278，109，063，589，184，505，269，608，083] 鏈式基數排序，下面以靜態(tài)鏈表存儲待排記錄，并令表頭指針指向第一個記錄 “分配” 時，按當前“關鍵字位”所取值，將記錄分配到不同的“鏈隊列”中，每個隊列中記錄的 “關鍵字位” 相同。 因為是 LSD，故從地位開始 ，也就是kd-1位開始，進行一趟分配： 然后xx9，xx3，xx0 又遇到了 xx9，那么按照鏈式隊列的存儲方式，先進先出的入隊（類似一個桶，數據從上面進入，從下面露出） 第一趟收集：按當前關鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表；（從隊列的下面出去，先進先出） 進行第二趟分配，kd-2位 進行第二題收集 進行第三趟分配，也就是 kd-3位。本例子是 k1位關鍵字 進行第三趟收集 序列按照多關鍵字從小到大的排序有序了 鏈式隊列的基數排序算法 void RadixSort(Queue& que) { //聲明一個指針數組，該指針數組中存放十個指針，這十個指針需要分別指向十個隊列，這是模擬10個桶，因為是0-9的數字，取值范圍為10 Queue *arr[10]; //初始化這十個隊列 for (int i = 0; i < 10; i++) { //初始化建立頭結點 arr[i] = new Queue; } //取得待排序數據元素中的最大位數 int maxLen = que.lengthData(); //因為是 LSD 方式，從后到前，開始比較關鍵字，然后分配再收集，故開始設置數據分離算法中的除數為 1 int d = 1; //將初始隊列中的元素分配到十個隊列中，maxlen 代表了需要分配和收集的次數 for(int i = 0; i < maxLen; i++) { Node *p = que.front->next; //輔助指針 q Node *q; //余數為k，則存儲在arr[k]指向的鏈式隊列（桶）中 int k; //遍歷原始序列 while (p != NULL) { //重要的技巧，數據分離算法過程，最后勿忘模10，取余數，分離出需要的關鍵字位 k = (p->data / d) % 10; q = p->next; //把本結點 p 加入對應的隊列中 arr[k]->push(p); //指針后移，指向下一個結點 p = q; } //清空原始隊列 que.clear(); //分配完畢，馬上將十個隊列中的數據收集到原始隊列中 for (int i = 0; i < 10; i++) { if (!arr[i]->empty()) { //從首節(jié)點開始遍歷，不是頭結點開始 Node *p = arr[i]->front->next; //輔助指針 q Node *q; while (p != NULL) { q = p->next; //收集到原始隊列中，這就是為什么每次分配完畢，需要清除原始隊列 que.push(p); p = q; } } } //一趟的分配收集完畢，最后要清空十個隊列 for (int i = 0; i < 10; i++) { arr[i]->clear(); } //進行下一趟的分配和收集 d *= 10; } //輸出隊列中排好序的元素 print(que); 鏈式基數排序的時間復雜度和空間復雜度分析 假設：n —— 記錄數 ， d —— 關鍵字數，  rd —— 關鍵字取值范圍（如十進制為10） 分配（每趟）：T(n)=O(n) ，每次分配，分配的都是所有的關鍵字，故是 n 收集（每趟）：T(n)=O(rd) ，收集的是桶里的數據，也就是關鍵字的取值范圍大小rd，是桶的數目 總的時間復雜度：因為一次完整的排序是分配+收集，也就是 n+rd ，而一共需要的排序趟數，恰恰就是關鍵字的數目 d，故T(n)=O(d(n+rd))  空間復雜度：S(n)=2rd 個隊列指針 + n 個指針域空間，因為一個桶本質是一個鏈式隊列，一共 rd 個桶，每個隊列有隊頭和隊尾兩個指針，就是2rd 個隊列指針。又原來的代拍序列是一個單鏈表，那么自然需要 n 個next指針控件。Ccw紅軟基地

英語基數詞ppt：這是英語基數詞ppt，包括了基數詞表示數目的詞稱為基數詞，熱門考點，序數詞，分數，小數，百分比，時間和鐘點，時刻表示法，日期和年份等內容，歡迎點擊下載。

基數詞和序數詞ppt：這是基數詞和序數詞ppt，包括了一至十二的數，十幾的數:都是以-teen\ti:n\結尾，整十數都是以ty \ ti \結尾，幾十幾的數，1-12的數，基變序歌訣等內容，歡迎點擊下載。

序數詞和基數詞ppt：這是序數詞和基數詞ppt，包括了數詞：數目多少：如1，2，3，4，序數詞：順序先后，如第1，第2，第3，第4，基數詞變?yōu)樾驍翟~口訣，解析口訣等內容，歡迎點擊下載。