首页 > 剑指offer > 线性时间内对范围在0-n^2内的数排序
2014
04-19

线性时间内对范围在0-n^2内的数排序

这是一个面试题。问题描述:给一个大小为n的数组arr,每个元素都是范围在 0 到 n^2-1内的数字,如何在线性时间内对齐排序?

例子:
假设有5个元素,每个元素范围在 0 - 24.
Input: arr[] = {0, 23, 14, 12, 9}
Output: arr[] = {0, 9, 12, 14, 23}

假设有3个元素,每个元素范围在 0 - 8.
Input: arr[] = {7, 0, 2}
Output: arr[] = {0, 2, 7}

分析:基于比较的排序肯定是不能用了,最低复杂度为O(nlogn),而题目要求为O(n)。复杂度为O(n) 的排序算法常见的有计数排序基数排序桶排序

如果数据的范围都在0-n ,就可以直接用计数排序了,空间复杂度为O(n)。在考虑下基数排序,一般来说复杂度为 O(nk),其中n是排序元素个数,k是数字位数,k的大小是取决于我们选取的底(基数),一般对十进制数的话就选取的10.  这里为了把k变为常数,就可以取n为底,k就为2. 这样复杂度就为 O(n)了。即把这些数都看成是n进制的,位数则不会超过2

arr[] = {0, 10, 13, 12, 7}

假设以5为底(即5进制).  十进制的13 就为 23,十进制的 7为 12.
arr[] = {00(0), 20(10), 23(13), 22(12), 12(7)}

第一边遍历后 (根据最低位排序)
arr[] = {00(0), 20(10), 12(7), 22(12), 23(13)}

第二遍遍历后
arr[] = {00(0), 12(7), 20(10), 22(12), 23(13)}

其中,基数排序的实现,又要依赖稳定的计数排序,所以需要O(n)的空间来计数。就是两次计数排序。

代码实现如下:

#include<iostream>
using namespace std;

//对数组arr[]计数排序,根据 exp 指定的位
int countSort(int arr[], int n, int exp)
{
    int output[n]; // 结果数组
    int i, count[n] ;
    for (int i=0; i < n; i++)
       count[i] = 0;

    // count[]记录出现的次数
    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%n ]++;

    for (i = 1; i < n; i++)
        count[i] += count[i - 1];

    // 得到结果数组
    for (i = n - 1; i >= 0; i--)
    {
        output[count[ (arr[i]/exp)%n] - 1] = arr[i];
        count[(arr[i]/exp)%n]--;
    }

    // 再将排序结果复杂到 arr
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

// 使用基数排序
void sort(int arr[], int n)
{
    // 按最后一位排序,即 exp (n^0 = 1) 
    countSort(arr, n, 1);

    //按高位排序,即exp (n^1 = n )
    countSort(arr, n, n);
}

//打印数组
void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

// 测试
int main()
{
    // 元素个数7, 范围在 0 - 48
    int arr[] = {40, 12, 45, 32, 33, 1, 22};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Given array is \n";
    printArr(arr, n);
    sort(arr, n);

    cout << "\nSorted array is \n";
    printArr(arr, n);
    return 0;
}

输出:

Given array is
40 12 45 32 33 1 22
Sorted array is
1 12 22 32 33 40 45

如何对 范围在1 – n^2 的数字排序呢?很简单,先每个数字减1,再排序。同理我们也可以对 范围在 0 – n^3 -1 的数字排序,通过调用3次计数排序。


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?