井井客

搜索

JS冒泡、插入、选择排序的算法像不像一家?

比较基础的冒泡排序、插入排序、选择排序算法的实现代码,感觉代码很相似呀,不知道是不是我写的有问题还是就是一家子~

JS冒泡、插入、选择排序的算法像不像一家?

1、冒泡排序

众所周知,冒泡算法就是将数列中相邻的两个数进行比较,然后将较大/小的数向同一个方向过渡。渐渐的就会形成一个由最小到最大的顺序。实现的代码:

//初始数组
var testArr = [3,5,1,9,2,8,4,15,6,11,19,2,1,7,0,5];
//冒泡排序
function bubbleSort(arr){
	var k = 0;
    var i = arr.length,
        j,temp;
    while( i > 0){
        for(j = 0; j < i-1; j++){
            temp = arr[j];
            //大于号升序,小于号降序
            if(arr[j] > arr[j+1]){
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
            //计算循环的次数
            k++;
        }
        i--;
    }
    return "共"+arr.length+"个数,冒泡算法进入循环了"+k+"次,结果为:"+String(arr);
}
console.log(bubbleSort(testArr))

里面的k是用于计算进入循环的次数,实际中并不需要。同时return正常只需返回arr,而上面这样写是为了方便读者看清(后面的代码也是一样的)。

2、插入排序

插入,我自己感觉是冒泡的一种进阶,实现的代码:

//初始数组
var testArr = [3,5,1,9,2,8,4,15,6,11,19,2,1,7,0,5];
//插入排序
function insertSort(arr){
    var k = 0;
    for(var i = 1; i < arr.length; i++){
        var temp = arr[i];
        var j = i-1;
        while(j >= 0 && temp < arr[j]){
            arr[j+1] = arr[j];
            j--;
            k++
        }
        if(j+1 !== i){
            arr[j+1] = temp;
        }
    }
    return "共"+arr.length+"个数,插入算法进入循环了"+k+"次,结果为:"+String(arr);
}
console.log(insertSort(testArr))

根据打印出的K值,这种算法进入循环的次数要比冒泡少了近一半,原因可能就在于它进于循环的条件有两个,只有当条件都满足时才会计算。

例如当数组索引为3时,正常完成j小于0的条件,需要计算三次,但如果索引2小于(根据排序规则升降)索引3值时,就会跳出循环,这样进入循环的次数就少了。

3、选择排序

正常的代码:

//初始数组
var testArr = [3,5,1,9,2,8,4,15,6,11,19,2,1,7,0,5];
//选择排序
function selectSort(arr){
    var k = 0;
    var temp;
    for(var i = 0; i < arr.length; i++){
        for(var j = i+1; j < arr.length; j++){
            if(arr[i] > arr[j]){
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            k++;
        }
    }
    return "共"+arr.length+"个数,选择排序进入循环了"+k+"次,结果为:"+String(arr);
}
console.log(selectSort(testArr))

选择跟冒泡差不多,循环次数也差不多,不过选择排序算法的过程是经过一遍比较后将最大/小值放到起始位置。下面是我自己实现的选择,循环一遍后将数列中最大/小值提取出来放在新的数组中,并且重新循环数列时不再计算这个数。

//初始数组
var testArr = [3,5,1,9,2,8,4,15,6,11,19,2,1,7,0,5];
//选择排序
function selectSort(arr){
    var k = 0;
    var index = 0 , temp = arr[index], tempArr = [];
    var i = arr.length;
    while( i > 0 ){
        for(j = 0; j < i; j++){
            if(temp > arr[j]){
                temp = arr[j];
                index = j;
            }
            k++;
        }
        i--;
        tempArr = tempArr.concat(arr.splice(index,1));
        index = 0;
        temp = arr[index]
    }
    return "共"+tempArr.length+"个数,插入算法进入循环了"+k+"次,结果为:"+String(tempArr);
}
console.log(selectSort(testArr))

总结一下可以发现这三种算法,是不是有种相似的地方?

它们都是向同一个方向传递数字,区别就在于一次传递几个位置。冒泡算法是相邻两个数一个位置一个位置传,传递的单位只有1个,并且可能会影响到最未尾的数。而插入排序的话,虽然也是一个一个传,但是在传的时候,如果条件不成立时,这种传递也会停止所以不一定会影响到未尾的数。

最后选择算法的话,则并不像常规的冒泡,它会将每次最小/大值与当前循环到的数进行对比,取最小/大值再与下一个数进行对比,同理循环下去。在一遍循环结束时获取到的最终的最小/大值放到顶端。

后面是我自己的想法,如果有什么不对的地方,欢迎拍砖~还有一个需要注意的就是列子中接收到的数组,因为是引用类型,所以很可能原始的数组值也会改变,所以在真实使用的时候还需要多多注意~

文章TAG:JS

作者:井井客原创来源:原创
本文标题:JS冒泡、插入、选择排序的算法像不像一家?
本文链接:/c/10283.html

上一篇:原生JS自制九九乘法表
下一篇:svg练习画了一个熊猫

文章分类

相关阅读

随便看看