JS中几种常用数组排序方式分析比较

arr.sort();	
			

arr.sort(function(a,b){
	return a - b;
});	
			

var len = arr.length;
for (var i = 0; i < len; i++) {
    for (var j = 0; j < len; j++) {
        if (arr[i] < arr[j]) {
            var tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
}	
			

var len = arr.length,
pos;
for (var i = len - 1; i > 0; i = pos) {
    //每次默认为没有交换
    pos = 0;
    for (var j = 0; j < i; j++) {
        if (arr[j] > arr[j + 1]) {
            var tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
            pos = j;
        }
    }
}
			

var len = arr.length,
j;
//设置一个低位，一个高位
var low = 0,
high = len - 1; //设置变量的初始值	
while (low < high) {
    for (j = low; j < high; ++j) {
        //正向冒泡,找到最大
        if (arr[j] > arr[j + 1]) {
            tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
        }
    }--high; //修改high值, 前移一位
    for (j = high; j > low; --j) {
        //反向冒泡,找到最小
        if (arr[j] < arr[j - 1]) {
            tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
        }
    }++low; //修改low值,后移一位
}
			

var len = arr.length,
minIndex;
for (var i = 0; i < len - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < len; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    var tmp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = tmp;
}
			

//quick的递归函数	
var quick = function(arr) {
    var len = arr.length;
    if (len <= 1) {
        return arr;
    }
    var index = Math.floor(len / 2),
    //向下取整 根据中间的值作为比较对象  
    pindex = arr.splice(index, 1)[0],
    //需要删除中间值，以缩小排序的数组大小  
    left = [],
    //定义左右两个数组 左大右小  
    right = [];
    for (i = 0; i < len - 1; i++) { //遍历整个数组 大放右 小放左  
        if (arr[i] >= pindex) {
            right.push(arr[i]);
        } else {
            left.push(arr[i]);
        }
    }
    return quick(left).concat([pindex], quick(right)); //继续递归并将数组合并  
};
arr = quick(arr);
			

var len = arr.length,key;
for (var i = 1; i < len; i++) {
    key = arr[i];
    var j = i - 1;
    while (arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}
			

var len = arr.length,
key, left, right, middle;
for (var i = 1; i < len; i++) {
    key = arr[i],
    left = 0,
    right = i - 1;
    while (left <= right) {
        middle = parseInt((left + right) / 2);
        if (key < arr[middle]) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    for (var j = i - 1; j >= left; j--) {
        arr[j + 1] = arr[j];
    }
    arr[left] = key;
}
			

var gap = 1,
key, i, j, tmp;
var len = arr.length;
//动态定义间隔序列
while (gap < len / 5) {
    gap = gap * 5 + 1;
}
for (; gap > 0; gap = Math.floor(gap / 5)) {
    for (i = gap; i < len; i++) {
        tmp = arr[i];
        for (j = i - gap; j >= 0 && arr[j] > tmp; j -= gap) {
            arr[j + gap] = arr[j];
        }
        arr[j + gap] = tmp;
    }
}
			

var merge = function(left, right) {
    var result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length) result.push(left.shift());
    while (right.length) result.push(right.shift());
    return result;
};
var mergeSort = function(arr) {
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
};
arr = mergeSort(arr);
			

//维护堆
var heapify = function(arr, x, len) {
    var l = 2 * x + 1,
    r = 2 * x + 2,
    largest = x,
    temp;
    if (l < len && arr[l] > arr[largest]) {
        largest = l;
    }
    if (r < len && arr[r] > arr[largest]) {
        largest = r;
    }
    if (largest != x) {
        temp = arr[x];
        arr[x] = arr[largest];
        arr[largest] = temp;
        heapify(arr, largest, len);
    }
};
var heapSort = function(arr) {
    //建堆
    var heapSize = arr.length,
    temp;
    for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
        heapify(arr, i, heapSize);
    }
    //堆排序
    for (var j = heapSize - 1; j >= 1; j--) {
        temp = arr[0];
        arr[0] = arr[j];
        arr[j] = temp;
        heapify(arr, 0, --heapSize);
    }
    return arr;
};
arr = heapSort(arr);
			

var countingSort = function(arr) {
    //额外开辟空间
    var B = [],
    C = [],
    min = arr[0],
    max = arr[0];
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        min = min <= arr[i] ? min: arr[i];
        max = max >= arr[i] ? max: arr[i];
        C[arr[i]] = C[arr[i]] ? C[arr[i]] + 1 : 1;
    }
    for (var j = min; j < max; j++) {
        C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
    }
    for (var k = len - 1; k >= 0; k--) {
        B[C[arr[k]] - 1] = arr[k];
        C[arr[k]]--;
    }
    return B;
};
arr = countingSort(arr);
			

//只适用于数字
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) {
        result = result.concat(buckets[n]);
        n++;
    }
    return result;
};
arr = bucketSort(arr, self.bucketCount);
			

var bucketSort = function(arr, bucketCount) {
    if (arr.length <= 1) {
        return arr;
    }
    bucketCount = bucketCount || 10;
    //初始化桶
    var len = arr.length,
    buckets = [],
    result = [],
    max = Math.max.apply(null, arr),
    min = Math.min.apply(null, arr);
    //求出每一个桶的数值范围
    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]) {
                k--
            }
            //js中可以使用自己的api,splice
            buckets[index].splice(k + 1, 0, 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 len = arr.length,
buckets = [],
result = [],
max = Math.max.apply(null, arr),
min = Math.min.apply(null, arr);
var bucketCount = self.bucketCount;
//每一个都创建一个数组
for (var i = 0; i < bucketCount; i++) {
    buckets[i] = [];
}
//只适用于数字
var bucketSort = function(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    //求出每一个桶的数值范围
    var space = (max - min + 1) / bucketCount;

    //将数值装入桶中
    for (var i = 0; i < len; i++) {
        //找到相应的桶序列
        var index = Math.floor((arr[i] - min) / space);
        //判断是否桶中已经有数值
        if (buckets[index].length > 0) {
            //数组从小到大排列
            var bucket = buckets[index];
            var k = bucket.length - 1;
            while (k >= 0 && buckets[index][k] > arr[i]) {
                k--
            }
            //js中可以使用自己的api,splice
            buckets[index].splice(k + 1, 0, arr[i]);
        } else {
            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);
			

var L = linklist;
//只适用于数字
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 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;
};

//链表存储对象
var _val = function(v) {
    return {
        v: v
    }
};

arr = bucketSort(arr, self.bucketCount);
			

var radixSort = function(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    var counter = [];
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for (var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if (counter[bucket] == null) {
                counter[bucket] = []
            }
            counter[bucket].push(arr[j])
        }
        var pos = 0;
        for (var j = 0; j < counter.length; j++) {
            var value = null;
            if (counter[j] != null) {
                while ((value = counter[j].shift()) != null) {
                    arr[pos++] = value
                }
            }
        }
    }
    return arr
}
arr = radixSort(arr, 5);