首页 > 基础算法 > 排序 > 基数排序(Radix Sorting)
2014
04-08

基数排序(Radix Sorting)

基数排序(radix sorting)将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。 然后 从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。具体过程可以参考动画演示

假设我们有一些二元组(a,b),要对它们进行以a为首要关键字,b的次要关键字的排序。我们可以先把它们先按照首要关键字排序,分成首要关键字相同的若干堆。然后,在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起,使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。第二种方式是从最低有效关键字开始排序,称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序,然后对所有的数据按照首要关键字排序。要注意的是,使用的排序算法必须是稳定的,否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序,LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。

基数排序的简单描述就是将数字拆分为个位十位百位,每个位依次排序。因为这对算法稳定要求高,所以我们对数位排序用到上一个排序方法计数排序。因为基数排序要经过d (数据长度)次排序, 每次使用计数排序, 计数排序的复杂度为 On),  d 相当于常量和N无关,所以基数排序也是 O(n)。基数排序虽然是线性复杂度, 即对n个数字处理了n次,但是每一次代价都比较高, 而且使用计数排序的基数排序不能进行原地排序,需要更多的内存, 并且快速排序可能更好地利用硬件的缓存, 所以比较起来,像快速排序这些原地排序算法更可取。对于一个位数有限的十进制数,我们可以把它看作一个多元组,从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序

例如我们将一个三位数分成,个位,十位,百位三部分。我们要对七个三位数来进行排序,依次对其个位,十位,百位进行排序,如下图:

radix sorting

很显然,每一位的数的大小都在[0,9]中,对于每一位的排序用计数排序再适合不过。

Java代码实现:

package sort;

//基数排序:稳定排序
public class RadixSorting {

	// d为数据长度
	private static void radixSorting(int[] arr, int d) {
		// arr = countingSort(arr, 0);
		for (int i = 0; i < d; i++) {
			arr = countingSort(arr, i); // 依次对各位数字排序(直接用计数排序的变体)
			print(arr, i + 1, d);
		}
	}

	// 把每次按位排序的结果打印出来
	static void print(int[] arr, int k, int d) {
		if (k == d)
			System.out.println("最终排序结果为:");
		else
			System.out.println("按第" + k + "位排序后,结果为:");
		for (int t : arr) {
			System.out.print(t + " ");
		}
		System.out.println();
	}

	// 利用计数排序对元素的每一位进行排序
	private static int[] countingSort(int[] arr, int expIndex) {
		int k = 9;
		int[] b = new int[arr.length];
		int[] c = new int[k + 1]; // 这里比较特殊:数的每一位最大数为9

		for (int i = 0; i < k; i++) {
			c[i] = 0;
		}
		for (int i = 0; i < arr.length; i++) {
			int d = getBitData(arr[i], expIndex);
			c[d]++;
		}
		for (int i = 1; i <= k; i++) {
			c[i] += c[i - 1];
		}
		for (int i = arr.length - 1; i >= 0; i--) {
			int d = getBitData(arr[i], expIndex);
			b[c[d] - 1] = arr[i];// C[d]-1 就代表小于等于元素d的元素个数,就是d在B的位置
			c[d]--;
		}
		return b;
	}

	// 获取data指定位的数
	private static int getBitData(int data, int expIndex) {
		while (data != 0 && expIndex > 0) {
			data /= 10;
			expIndex--;
		}
		return data % 10;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = new int[] { 326, 453, 608, 835, 751, 435, 704, 690, 88, 79,
				79 };// { 333, 956, 175, 345, 212, 542, 99, 87 };
		System.out.println("基数排序前为:");
		for (int t : arr) {
			System.out.print(t + " ");
		}
		System.out.println();
		radixSorting(arr, 4);
	}

}

输出:

基数排序前为:
326 453 608 835 751 435 704 690 88 79 79 
按第1位排序后,结果为:
690 751 453 704 835 435 326 608 88 79 79 
按第2位排序后,结果为:
704 608 326 835 435 751 453 79 79 88 690 
按第3位排序后,结果为:
79 79 88 326 435 453 608 690 704 751 835 
最终排序结果为:
79 79 88 326 435 453 608 690 704 751 835

效率

基数排序的时间复杂度是 O(k·n),其中n是排序元素个数,k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n)),因为k的大小一般会受到 n 的影响。 以排序n个不同整数来举例,假定这些整数以B为底,这样每位数都有B个不同的数字,k就一定不小于logB(n)。由于有B个不同的数字,所以就需要B个不同的桶,在每一轮比较的时候都需要平均n·log2(B) 次比较来把整数放到合适的桶中去,所以就有:

  • k 大于或等于 logB(n)
  • 每一轮(平均)需要 n·log2(B) 次比较

所以,基数排序的平均时间T就是:

T ≥ logB(nn·log2(B) = log2(n)·logB(2n·log2(B) = log2(n)·n·logB(2)·log2(B) = n·log2(n)

所以和比较排序相似,基数排序需要的比较次数:T ≥ n·log2(n)。 故其时间复杂度为 Ω(n·log2(n)) = Ω(n·log n) 。

参考:http://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

http://www.cnblogs.com/ttltry-air/archive/2012/08/04/2623302.html


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。