JavaScript排序

1.希尔排序：建立在直接插入排序基础上。

比如数组[ 13, 14, 94,33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10]，设置步长5

13, 14, 94, 33, 82,

25, 59, 94, 65, 23,

45, 27, 73, 25, 39,

10

对每列进行插入排序：5列同时进行插入排序，不是一列插入排序完成后，再对列一列进行插入排序

25和13比较，59和 14比较，94和94比较，65和33比较 23和82比较得到结果

13, 14, 94, 33, 23,

25, 59, 94, 65, 82,

45, 27, 73, 25, 39,

10

到45的时候，相当于13,25,45进行插入排序，

到27的时候，对14,59,27进行插入排序，依次类推。

完成排序后，再将步长变成2，进行上述操作，直至步长变成1。

function shellsort(list) {
    var gap = list.length / 2;
 
    while (1 <= gap) {
        // 把距离为 gap 的元素编为一个组，扫描所有组
        for (var i = gap; i < list.length; i++) {
            var j = 0;
            var temp = list[i];
 
            // 对距离为 gap 的元素组进行排序
            for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
                list[j + gap] = list[j];
            }
            list[j + gap] = temp;
        }
        gap = gap / 2; // 减小增量
    }
}
var arr = [ 13, 14, 94,33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10];
shellsort(arr);
console.log(arr);//[ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]

2.计数排序：计算数字出现的次数，该方法数字的范围就是数组的长度

对数值范围0-9的数进行排序

[6, 2, 8, 5, 2, 5, 6, 7, 9, 8, 3, 1, 5, 6, 2,5,9,7,5,1]

将数字出现的次数存放到该数字对应下标的数组中，例如数字2出现了3次，arr[2]=3

'use stirct';
function countsort(arr){
	var countarr = new array(20);
	countarr.fill(0);
	var result = [];
	for(var i = 0; i
3.基数排序：
首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中
合并成一个数组[ 60, 81, 72, 123, 23, 24, 555, 36, 89, 99 ]
根据十位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中
合并成一个数组[ 123, 23, 24, 36, 555, 60, 72, 81, 89, 99 ]
根据百位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中
得到数组[ 23, 24, 36, 60, 72, 81, 89, 99, 123, 555 ]，完成排序。
'use stirct';
function getdigit(x,d){   
     var a = [1, 10, 100]; 
     return math.floor(x/a[d]) % 10;  
}  
var d = 0;
function radixsort(arrnum,d){
	if(d>2){
		return arrnum;
	}
	//创建容器
	var arr2 = new array(10).fill(0);//数组内容是空时，执行map是无效的
	arr2 = arr2.map(function(){
		return [];
	})
	var arr1 = []; 
	//往容器中放数据
	arrnum.foreach(function(x){
		arr2[getdigit(x,d)].push(x);
	})
	//将二维数组变成一维数组
	arr2.foreach(function(arr){
		arr1 = arr1.concat(arr)
	});
	d++;
	return radixsort(arr1,d);
}
var arr = [89,60,123,23,555,81,72,24,36,99];
var a = radixsort(arr,d)
console.log(a);
桶排序：
将数字放入对应的桶中，
0号桶放 0-9
1号桶放 10-19，以此类推，
将各个桶中的数字排序，将所有桶按编号顺序合并
'use stirct';  
function bucketsort(arrnum){
	//创建容器
	var arr2 = new array(10).fill(0);//数组内容是空时，执行map是无效的
	arr2 = arr2.map(function(){
		return [];
	})
	var arr1 = []; 
	//往容器中放数据
	arrnum.foreach(function(x){
		arr2[math.floor(x/10)].push(x);
	});
	//一维数组排序
	arr2.foreach(function(arr){
		arr.sort(function(a,b){
			return a-b;
		});
	})
	//将二维数组变成一维数组
	arr2.foreach(function(arr){
		arr1 = arr1.concat(arr)
	});
	return arr1;
}
var arr = [89,60,32,12,55,81,72,24,36,99];
var a = bucketsort(arr)
console.log(a);
;i++){>