排序算法之桶排序的深入理解以及性能分析

[63,157,189,51,101,47,141,121,157,156,194,117,98,139,67,133,181,13,28,109] 

var bucketSort = function(arr, bucketCount) {
    if (arr.length <= 1) {
        return arr;
    }
    bucketCount = bucketCount || 10;
    //初始化桶
    var len = arr.length,
    buckets = [],
    result = [],
    max = arr[0],
    min = arr[0];
    for (var i = 1; i < len; i++) {
        min = min <= arr[i] ? min: arr[i];
        max = max >= arr[i] ? max: arr[i];
    }
    //求出每一个桶的数值范围
    var space = (max - min + 1) / bucketCount;
    //将数值装入桶中
    for (var i = 0; i < len; i++) {
        //找到相应的桶序列
        var index = Math.floor((arr[i] - min) / space);
        //判断是否桶中已经有数值
        if (buckets[index]) {
            //数组从小到大排列
            var bucket = buckets[index];
            var k = bucket.length - 1;
            while (k >= 0 && buckets[index][k] > arr[i]) {
                buckets[index][k + 1] = buckets[index][k];
                k--
            }
            buckets[index][k + 1] = arr[i];
        } else {
            //新增数值入桶，暂时用数组模拟链表
            buckets[index] = [];
            buckets[index].push(arr[i]);
        }
    }
    //开始合并数组
    var n = 0;
    while (n < bucketCount) {
        if (buckets[n]) {
            result = result.concat(buckets[n]);
        }
        n++;
    }
    return result;
};
//开始排序
arr = bucketSort(arr, self.bucketCount);

var L = require('linklist'); //链表
var sort = function(arr, bucketCount) {
	if(arr.length <= 1) {
		return arr;
	}
	bucketCount = bucketCount || 10;
	//初始化桶
	var len = arr.length,
		buckets = [],
		result = [],
		max = arr[0],
		min = arr[0];
	for(var i = 1; i < len; i++) {
		min = min <= arr[i] ? min : arr[i];
		max = max >= arr[i] ? max : arr[i];
	}
	//求出每一个桶的数值范围
	var space = (max - min + 1) / bucketCount;
	//将数值装入桶中
	for(var i = 0; i < len; i++) {
		//找到相应的桶序列
		var index = Math.floor((arr[i] - min) / space);
		//判断是否桶中已经有数值
		if(buckets[index]) {
			//数组从小到大排列
			var bucket = buckets[index];
			var insert = false; //插入标石
			L.reTraversal(bucket, function(item, done) {
				if(arr[i] <= item.v) { //小于，左边插入
					L.append(item, _val(arr[i]));
					insert = true;
					done(); //退出遍历
				}
			});
			if(!insert) { //大于，右边插入
				L.append(bucket, _val(arr[i]));
			}
		} else {
			var bucket = L.init();
			L.append(bucket, _val(arr[i]));
			buckets[index] = bucket; //链表实现
		}
	}
	//开始合并数组
	for(var i = 0, j = 0; i < bucketCount; i++) {
		L.reTraversal(buckets[i], function(item) {
			// console.log(i+":"+item.v);
			result[j++] = item.v;
		});
	}
	return result;
};

//链表存储对象
function _val(v) {
	return {
		v: v
	}
}
//开始排序
arr = bucketSort(arr, self.bucketCount);

public static double[] bucketSort(double arr[], int bucketCount) {

    int len = arr.length;
    double[] result = new double[len];
    double min = arr[0];
    double max = arr[0];
    //找到最大值和最小值
    for (int i = 1; i < len; i++) {
        min = min <= arr[i] ? min: arr[i];
        max = max >= arr[i] ? max: arr[i];
    }
    //求出每一个桶的数值范围
    double space = (max - min + 1) / bucketCount;
    //先创建好每一个桶的空间,这里使用了泛型数组
    ArrayList < Double > [] arrList = new ArrayList[bucketCount];
    //把arr中的数均匀的的分布到[0,1)上，每个桶是一个list，存放落在此桶上的元素   
    for (int i = 0; i < len; i++) {
        int index = (int) Math.floor((arr[i] - min) / space);
        if (arrList[index] == null) {
            //如果链表里没有东西
            arrList[index] = new ArrayList < Double > ();
            arrList[index].add(arr[i]);
        } else {
            //排序
            int k = arrList[index].size() - 1;
            while (k >= 0 && (Double) arrList[index].get(k) > arr[i]) {
                if (k + 1 > arrList[index].size() - 1) {
                    arrList[index].add(arrList[index].get(k));
                } else {
                    arrList[index].set(k + 1, arrList[index].get(k));
                }
                k--;
            }
            if (k + 1 > arrList[index].size() - 1) {
                arrList[index].add(arr[i]);
            } else {
                arrList[index].set(k + 1, arr[i]);
            }
        }

    }

    //把各个桶的排序结果合并  ,count是当前的数组下标
    int count = 0;

    for (int i = 0; i < bucketCount; i++) {
        if (null != arrList[i] && arrList[i].size() > 0) {
            Iterator < Double > iter = arrList[i].iterator();
            while (iter.hasNext()) {
                Double d = (Double) iter.next();
                result[count] = d;
                count++;
            }
        }
    }
    return result;
}
//开始排序,其中arr为需要排序的数组
double[] result = bucketSort(arr,bucketCount);

O(N)+O(M*(N/M)*log(N/M))=O(N*(log(N/M)+1))

求M的极小值，具体计算为:(其中N可以看作一个很大的常数)
F(M) = log(N/M)+M/N) = LogN-LogM+M/N
它的导函数
F'(M) = -1/M + 1/N
因为导函数大于0代表函数递增，小于0代表函数递减
所以F(M)在(0,N) 上递减
在(N,+∞)上递增
所以当M=N时取到极小值