這是基數(shù)排序ppt，包括了基數(shù)排序原理，一種基于分配—收集的排序算法一種穩(wěn)定的排序算法，基數(shù)排序算法的具體實現(xiàn)，鏈?zhǔn)降幕鶖?shù)排序算法等內(nèi)容，歡迎點擊下載。

基數(shù)排序ppt是由紅軟PPT免費下載網(wǎng)推薦的一款課件PPT類型的PowerPoint.

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

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

基數(shù)詞和序數(shù)詞ppt：這是基數(shù)詞和序數(shù)詞ppt，包括了一至十二的數(shù)，十幾的數(shù):都是以-teen\ti:n\結(jié)尾，整十?dāng)?shù)都是以ty \ ti \結(jié)尾，幾十幾的數(shù)，1-12的數(shù)，基變序歌訣等內(nèi)容，歡迎點擊下載。

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