Js排序相关...

##冒泡排序(BUBBLE SORT)

数组相邻位置对比大小,左<右则交换位置,
冒泡排序遍历->
第一轮最大的将冒泡至最右边, 遍历次数:arr.length
第二轮,第二大将至最右边, 遍历次数:arr.length-1
依次…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//冒泡排序
function bubbleArr(arr){
var i = arr.length, j, temp;
while(i){
for(var j=0; j<i-1; j++){
if(arr[j] > arr[j+1]){
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
// console.log(arr, 'arrSub');
};
// console.log(arr, 'arr');
i--;
}
return arr;
}

##快速排序(QUICK SORT 来源于二分查找思想)

将数组中间下标的值取出作为参考值, 将此数据与参考值比较, 小于参考值放左边,大于放右边。然后递归快速排序左右。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//快速排序
function quickSort(arr){
if(arr.length<=1){
return arr; //递归结束条件
}
var pivotIndex = Math.floor(arr.length/2);
var pivot = arr.splice(pivotIndex,1)[0]; //标准对比值,arr为去除对比值后的数据
var left = [],right = [];
for(var i=0; i<arr.length; i++){
if(arr[i] < pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}

插入排序(INSERTION SORT)

把第一个数字单独成有序数组,然后把紧跟的后面的数字插入有序数组形成二个有序数组,
然后今次把后面的数字插入前面增量的有序数组。
如此…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function insertionSort(arr){
var key,i;
//第一个数字单独成有序数组
//从第二个开始遍历,如果小于第一个则交换,则第一二个数字成有序数组
//依次 ...
for(var j=1; j<arr.length; j++){
key = arr[j]; //2
i = j-1;
while(i>-1 && arr[i] > key){ //1>2
arr[i+1] = arr[i]; //2=1
i--;
}
arr[i+1] = key; //1=2
//console.log(arr, 'ARR');
}
return arr;
}

希尔排序(SHELL SORT)

查找遗漏

在1-range范围内随机生成n个不重复整数的数据;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//
// whole true 连续的
// num 去掉num个
function genRandom(n, range){
var rdmArr = [];
for(var i=0; i<n; i++){
var rdm = Math.ceil(Math.random() * range, 10);
if(!~rdmArr.indexOf(rdm)){
rdmArr.push(rdm);
}else{
i--;
}
}
return rdmArr;
}

生成1-n整数的数组并且在里面随机去掉m个整数,不存在m则生成完整的数组

1
2
3
4
5
6
7
8
9
10
11
12
function setArr(n, m){
var arr = [];
var rdmArr = genRandom(m, n);
for (var i = 1; i <= n; i++) {
if (!m || !rdmArr.filter(function(item,j){
return item === i;
}).length){
arr.push(i)
}
};
return arr;
}

找出【1-n整数的数组并且在里面随机去掉m个整数】,中去掉的那m个数;

1
2
3
4
5
6
7
8
9
10
11
12
13
// 1.根据位置定位
function findNumByPosition(arr, n){
var j, targetArr = [], begin=1;
for(var i=0; i<arr.length; i++){
//如果找到则某个位置少数则继续对应这个位置的数;
if(arr[i] !== begin){
targetArr.push(begin);
i--;
}
begin++;
}
return targetArr;
}


排序动画演示