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