基数排序，基数排序是稳定的吗

编程之家2024-05-31116次浏览

基数词是表示数量的词，如一、二、三、四、五等，它们用来表示具体的数量，如一本书、三个苹果等。

而序数词是表示顺序的词，如第一、第二、第三、第四、第五等，它们用来表示事物的排列顺序，如第一名、第二页等。基数词和序数词都是表示数量的词语，但它们的运用场合和语法结构不同。在日常生活中，基数词和序数词都是非常常见的，我们需要根据不同的语境和语法要求，正确地使用它们。

基数排序的算法思想是按照整数的位数，从最低位到最高位依次排序,如果关键字的该位数不存在则视作为0。

比如我们给定一组待排序的关键字[52,314,68,9,115,20,17]。这组关键字的最高位数是百位，所以我们分别对个位，十位，百位进行排序。

先对个位进行排序得：[20,52,314,115,17,68,9];

再对十位进行排序得：[9,314,115,17,20,52,68];

再对百位进行排序得：[9,17,20,52,68,115,314];

最高位数排列完成后，我们得到的就是一个有序的数列。那么在遇到关键字中含有负数或零的时候我们该怎么处理呢？我采用的一种解决思想是：

对于零我们可以把基数排序中需要用到的辅助数组初始化为-1。

对于负数我们可以把这一组关键字加上这个最小负数的绝对值，这样这组关键字就变成了一组非负数的关键字，我们再对这组非负数的关键字进行排序，排序后我们在让关键字减去排序前加上的最小负数的绝对值就可以了。

基数词的排序是根据数字的大小来确定的。比如：one（1）比two（2）小，所以one排在two之前。

序数词的排序是根据字母的顺序来确定的。比如：first（第一）比second（第二）靠前，所以first排在second之前。