线性排序算法 [英] Linear sorting algorithms

问题描述

我是一个新手，学习算法 - 我也不是计算机专业毕业
。 然而，同时通过线性排序非比较算法读书，我可以理解，基数排序是计数形式的扩展。
什么我不清楚的是计数排序的限制。
为什么我会去为基数排序，当计数排序似乎成为永远在那里我需要避免一个O（N * LOGN）比较的目的是什么？
这似乎是一个非常简单的实现是肯定的。

I am a newbie to studying algorithms - nor am I a computer science grad.
However,while reading through the linear sorting non-comparison algorithms,I could understand that the radix sort is a extension of the counting sort.
What I am unclear about is the limitation of counting sort.
Why would I go for radix sort when counting sort seems to serve the purpose where ever I need to avoid a O(n*logn) comparison?
It does seem to be a much simpler implementation for sure.

推荐答案

想象一下，有人给了你一个整数列表进行排序。你对它一无所知，除了它包含的整数。

Imagine someone gave you a list of integers to sort. You know nothing about it except that it contains integers.

如果你幸运的话，在列表中可能包含在一个相当紧密结合的数字。如果你选的整型都在-100到100，以做计数排序不会坏的创造与大小的数组。

If you're lucky, the list might contain numbers within a fairly tight bound. If you're sorting integers that are all between -100 and 100, creating an array with that size in order to do counting sort wouldn't be bad at all.

但是，如果连一个数字是非常大或非常小的，你现在必须对数组的边界延伸，以做计数排序在整个输入。如果你真的想所有可能的整数排序（你不知道值的范围在创建前阵，除非你先找到它），你需要做大小的数组 2 * MAX_INT （负和正整数）。

But if even one number is very large or very small, you now have to extend the bounds of the array in order to do counting sort on the whole input. If you really want to sort all possible integers (and you don't know the range of the values before you create the array, unless you go find it first), you would need to make an array of size 2 * max_int (for negative and positive integers).

基数排序是好事，因为你永远需要创建尺寸大于数字的范围（0-9）的阵列。

Radix sort is good because you never need to create an array with size greater than the range of digits (0-9).

这篇关于线性排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！