數(shù)據(jù)結構與算法篇-基數(shù)排序
時間：2021-08-19 15:30:18
手機看文章
掃描二維碼
隨時隨地手機看文章
[導讀]01—基數(shù)排序算法思想輸入n個d位數(shù)，現(xiàn)在要對n個數(shù)進行排序，就需要設計一個排序算法法?；鶖?shù)排序算法思想：先對最低有效位采用穩(wěn)定排序算法進行排序，然后從次最低有效位到最高有效位依次采用穩(wěn)定排序算法進行排序，處理完最高有效位后則是最終排序后的結果。這里說明一下什么是穩(wěn)定排序算法和不...
01—基數(shù)排序算法思想
輸入n個d位數(shù)，現(xiàn)在要對n個數(shù)進行排序，就需要設計一個排序算法法。基數(shù)排序算法思想：先對最低有效位采用穩(wěn)定排序算法進行排序，然后從次最低有效位到最高有效位依次采用穩(wěn)定排序算法進行排序，處理完最高有效位后則是最終排序后的結果。這里說明一下什么是穩(wěn)定排序算法和不穩(wěn)定排序算法：大小相同的數(shù)字A和B分別在原始序列中的索引是x和y，且x>y。經(jīng)過排序后A和B分別所在輸出序列的索引是x1和y1，如果x1>y1，那么這個排序算法是穩(wěn)定的，如果x1
02—基數(shù)排序算法實現(xiàn)基數(shù)排序算法的實現(xiàn)最重要的是各個有效位使用的排序算法，已知計數(shù)排序算法的時間復雜度是O(n k)，如果基數(shù)排序采用計數(shù)排序?qū)個d位的數(shù)字進行排序，那么時間復雜度是O(d(n k))，現(xiàn)在我們用計數(shù)排序算法實現(xiàn)基數(shù)排序算法。
//求取最大值
static?int?get_max(int?*arr, int?length){
????int?i = 0;
????int?max = 0;
????max = arr[0];
????for(i = 1; i < length; i ){
????????if(arr[i] > max){
????????????max = arr[i];
????????}
????}
????return?max;
}
//計數(shù)排序
void?count_sort(int?*arr, int?length, int?exp){
????if(arr == NULL?|| length <= 0?|| exp?<= 0){
????????return;
????}
????int?bucket[10] = {0};
????int?*output = (int?*)malloc(sizeof(int) * length);
????if(output == NULL){
????????return;
????}
????memset(output, 0, sizeof(int) * length);
????int?i = 0;
????for(i = 0; i < length; i ){
????????bucket[(arr[i] / exp) % 10] ;
????}
????for(i = 1; i < length; i ){
????????bucket[i] = bucket[i - 1];
????}
????for(i = length - 1; i >= 0; i--){
????????output[bucket[(arr[i] / exp) % 10] - 1] = arr[i];
????????bucket[(arr[i] / exp) % 10]--;
????}
????for(i = 0; i < length; i ){
????????arr[i] = output[i];
????}
????free(output);
}
//基數(shù)排序
void?radix_sort(int?*arr, int?length){
????if(arr == NULL?|| length <= 0){
????????return;
????}
????int?exp?= 0;
????int?max = get_max(arr, length);
????for(exp?= 1; max / exp; exp?*= 10){
????????count_sort(arr, length, exp);
????}
}最后寫一個小程序驗證算法的正確性。
#include?
#include?"radix_sort.h"
int?main()?{
????int?arr[10] = {873, 12, 89, 256, 978, 67, 56434, 654, 24345, 9};
????radix_sort(arr, 10);
????int?i = 0;
????printf("基數(shù)排序結果\n");
????for(i = 0; i < 10; i ){
????????printf("%d ", arr[i]);
????}
????printf("\n");
????return?0;
}編譯運行輸出如下：
基數(shù)排序結果
9 12 67 89 256 654 873 978 24345 56434輸出完全正確。
版權申明：內(nèi)容來源網(wǎng)絡，版權歸原創(chuàng)者所有。除非無法確認，都會標明作者及出處，如有侵權煩請告知，我們會立即刪除并致歉。謝謝!
下載文檔
