中国建设教育协会官方网站查,网站导航设计原则,如何添加网站板块,上海网站制作网站建设基数排序
时间复杂度#xff1a;Θ(d(nk)) d#xff1a;元素的位数#xff0c;k元素中每位数的取值区间大小 非原址排序 1⃣️特点该排序只能每次为基数为1位数进行排序
void radix_sort(int *array,int length,int digits){vectorKeyValuePair temp_array(length…基数排序
时间复杂度Θ(d(nk)) d元素的位数k元素中每位数的取值区间大小 非原址排序 1⃣️特点该排序只能每次为基数为1位数进行排序
void radix_sort(int *array,int length,int digits){vectorKeyValuePair temp_array(length);for (int i 0; i length; i) {temp_array[i].value array[i];}for (int i 0; i digits; i) {for (int j 0; j length; j){temp_array[j].key (temp_array[j].value / (int) pow(10,i)) % 10;}counting_sort_by_key(temp_array);}for (int i 0; i length; i) {array[i] temp_array[i].value;}
}辅助类KeyValuePair 链接地址 辅助排序 counting_sort_by_key 链接地址
2⃣️以多位数 r 为基础进行排序(rb,b为总位数不在是一位一位的排序 时间复杂度Θ((b/r)(n2^r))。 通常情况下若b O(lgn)取r≈lgn则基数排序的运行时间为Θ(n)。
void radix_sort(int *array,int length,int total_digits,int single_digit){vectorKeyValuePair temp_array(length);for (int i 0; i length; i) {temp_array[i].value array[i];}for (int i 0 ; i total_digits; i single_digit) {for (int j 0; j length; j){temp_array[j].key (temp_array[j].value / (int) pow(10,i)) % ((int) pow(10,single_digit));}counting_sort_by_key(temp_array,-(int) pow(10,single_digit),(int) pow(10,single_digit));}for (int i 0; i length; i) {array[i] temp_array[i].value;}
}3⃣️基数排序的诡异版本 基数排序的不在以10进制分割而是以任意大于1的自然数代码中的range分割。 参数 range 取值大于n时一定成功小于n时不一定成功。有兴趣的同学可以共同探讨下。 时间复杂度Θ(log(range,max{ |array中元素|})(n2range))
void radix_sort_by_range(int *array,int length,int range)
{vectorKeyValuePair temp_array(length);for (int i 0; i length; i) {temp_array[i].value array[i];}int i 0;bool interrupt true;while (true){interrupt true;for (int j 0; j length; j){temp_array[j].key (temp_array[j].value / (int) pow(range,i)) % range;interrupt interrupt !temp_array[j].key;}if(interrupt)break;i;counting_sort_by_key(temp_array,-range,range);}for (int i 0; i length; i) {array[i] temp_array[i].value;}
}vector容器版本
void radix_sort(vectorint array,int digits)
{vectorKeyValuePair temp_array(array.size());for (int i 0; i array.size(); i) {temp_array[i].value array[i];}for (int i 0; i digits; i) {for (int j 0; j array.size(); j){temp_array[j].key (temp_array[j].value / (int) pow(10,i)) % 10;}counting_sort_by_key(temp_array);}for (int i 0; i array.size(); i) {array[i] temp_array[i].value;}
}
