排序算法

Question

给定数组arr[n],其中n=10000,0<arr[i]<9999,-1<i<10000.
已知数组中的值时乱序的，且其值均匀分布在0-9999 区间，只有少量数值重复
请用js代码写一个函数，以最快的方式完成对该数组的升序排序，要求算法时间复杂度必须小于O(NLOG2N).

Answer 1

数据是均匀分布的，用桶排序挺合适，时间复杂度也必定小于NlogN。
对于N个待排数据，M个桶，桶排序平均时间复杂度为：O(N+N(logN/M)).
桶数越多，速度越快，但空间代价也越大。

具体算法就不写了。

//=======补充代码======

function insertSort(array) {
  var i = 1,
    j, temp, key, len = array.length;
  for (; i < len; i++) {
    temp = j = i;
    key = array[j];
    while (--j > -1) {
      if (array[j] > key) {
        array[j + 1] = array[j];
      } else {
        break;
      }
    }
    array[j + 1] = key;
  }
}
//**迭代快排**
function qs(arr){
    var stack = [];
    stack.push([0,arr.length-1]);
    var l,r,axis,o;
    while(stack.length){
        o = stack.pop();
        l = o[0],r = o[1];
        if( l >= r )
            continue;
        axis = once(arr,l,r);
        stack.push([l,axis-1]);
        stack.push([axis+1,r]);
    }

    function once(arr,l,r){
        var axisAtLeft = true, //left right sign, default left;
            temp;
        swap(arr,l, (r+l)/2 >> 0);  //以中值为轴值
        while(l<r){
            if( axisAtLeft ){
                if( arr[l] > arr[r] ){
                    swap(arr,l++,r);
                    axisAtLeft = false;
                }else  r--;
            }
            else{
                if( arr[l] > arr[r] ){
                    swap(arr,l,r--);
                    axisAtLeft = true;
                }else  l++;
            }
        }
        return l;
    }

    function swap(arr,l,r){
        var temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
    return arr;
}

function createArr(min, max, p ) {
    var arr = [];
    var c = max - min;
    var probability = p || 0.001; //不均匀分布的概率0.1%

    //打乱顺序
    var indexArr = [];
    for (var i = 0; i < c; i++) indexArr[i] = i;
    indexArr.sort(function(a, b) {
        return Math.random() > 0.5 ? 1 : -1;
    });

    for (var i = 0; i < c; i++) {
        if (Math.random() > probability) { //不均匀分布的概率0.1%
            arr.push( indexArr[i] + Math.random() );
        } else {
            arr.push( Math.random() * (c-1) );
        }
    }
    return arr;
}

function bucketSort(arr, min, max) {
    var N = arr.length,
        bucks = [],
        M = Math.floor(Math.sqrt(N)),  //桶的个数设为Math.sqrt(N),如N=10000，则桶数为100
        dis = (max - min) / M;

    //初始化桶
    for (var i = 0; i < M; i++) bucks[i] = [];

    //数据入桶
    for (var j = 0; j < N; j++) 
        bucks[ Math.floor((arr[j] - min) / dis) ].push(arr[j]);

    //各个桶的数据排序
    for (var i = 0; i < M; i++)
         insertSort(bucks[i]);

    //合并各个桶的数据
    var firstBucket = bucks[0];
    for (var i = 1; i < M; i++){
        var bucket_i = bucks[i];
        for(var j=0;j<bucket_i.length;j++){
            firstBucket.push(bucket_i[j]);
        }
    }

    return firstBucket
}

var min = 0,
    max = 10000,
    arr = createArr(min, max)

//桶排序
var d1 = new Date();
var narr = bucketSort(arr, min, max);
console.log(new Date() - d1);


var arr2 = createArr(min, max)
//快排
var d2 = new Date();
qs(arr2);
console.log(new Date() - d2);

在firefox中测试，10000条数据，桶排序快一倍以上。

Answer 2

采用一个类似于位图的结构来解决这个问题。首先，你的数据量不大，而且像你说的重复数目也不多，这里看作常数。可以声明一个10000字节大小的数组count[10000]，初始化为全0。扫描一遍你的待排序的数据，针对每一个值i，递增其对应的位置的数组值count[i]。扫描完毕后，再从头扫描一遍a[10000]，对于i，输出a[i]次即可。这样时间复杂度为O(n),
我js不怎么懂。勉强给你写个函数

function mySort(arr, length) {
    var count = new Array(length);
    for (var i = 0; i != length; i++) {
        count[i] = 0;
    }
    for (var i = 0; i != length; i++) {
        count[arr[i]]++;
    }
var index = 0;
    for (var i = 0; i != length; i++) {
        for (var j = 0; j < count[i]; j++) {
            arr[index ++] = i;
        }
    }
//alert(count); 
}
// An example
var arr = new Array(10);
arr[0] = 1;
arr[1] = 2;
arr[2] = 1;
arr[3] = 0;
arr[4] = 9;
arr[5] = 8;
arr[6] = 6;
arr[7] = 2;
arr[8] = 3;
arr[9] = 6;

mySort(arr, 10);

alert(arr);

Answer 3

楼主请认真自己做作业，都说了复杂度小 NlogN 了，肯定不是排序了，而是某种比较讨巧的作法。

有人赞，我就写代码

Answer 4

数据很小，不要求空间复杂度的话直接桶排。

var a = new Array;
for(var i=1;i<=10000;i++){
    a[arr[i]]++;
}
//排序完成，可以输出了
for(var i=1;i<=10000;i++){
    for(var j=1;j<=a[i];j++){
        alert(i);
    } 
}