JavaScript Algorithms

常用排序算法的JS实现

Posted by 犀利一下下 on 2017-03-02

作为一个新生代的前端开发工程师，不了解算法怎么行？虽然没有大块儿的时间去读《算法导论》，但是学学常见的一些基本算法还是很有必要的，一来是对自己知识面的小范围扫盲，二来也能更加知道算法的作用，为以后需要深入学习或者使用打好基础。所以，这篇文章用来记录看过的几个算法的简单实现过程还有思路。

排序算法说明

时间复杂度: 一个算法执行所耗费的时间

空间复杂度: 运行完一个程序所需内存的大小

假如存在一个data为数组[9,5,8,7,5,6,2,3,4,0]，想对其进行排序，最方便的可以使用js自身的sort方法，比如：

1
2
3
var data =[9,5,8,7,5,6,2,3,4,0]
// 想对该数组进行排序，可以使用js自带的sort方法:
data.sort((x,y)=>x-y)

但是为了学习其他排序算法的思路，下面分别用其他方法进行对比

1.冒泡排序

思路解析：
(1)重复比较相邻两个元素之间的大小，小的放左边，大的放右边;

(2)第一轮比较之后，最大的数值肯定会被放到最右边;

(3)接下来第二轮，只需要把第二轮中最大的放在第二靠右的位置就行了，所以j的限定范围是j<len-1-i;
以此类推：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Array.prototype.bubbleSort = function(){
    var len = this.length
    var arr = this
    //外层循环遍历元素，脚标从0到len-1,i是为了表征选出第几（i+1）个最大值放到了右侧
    for(var i=0; i<len-1;i++){
        //内层循环遍历元素，脚标从0到len-1-i，随着i增加，循环j的范围减小，
        //是因为右侧已经排过的最大值不需要重新排了
        for(var j=0; j<len-1-i; j++){
            if(arr[j]>arr[j+1]){
                var temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1]=temp
            }
        }
    }
    return arr
}
console.log(data.bubbleSort())  //[0,2,3,4,5,5,6,7,8,9]

2.快速排序

思路解析：快速排序是对冒泡排序的一种改进，第一轮排序将数据分为两部分，一部分比另一部分的所有数据都小。
接着再对两个部分递归调用快排方法，直到最小的部分只剩两个元素。

(1)选择一个基准元素，将数据分为两个子序列;

(2)对数据重新排序，将所有小于基准值的元素放在基准值的前面，所有大于基准值的数据放在后面;

(3)分别对较小元素的子序列和较大元素的子序列重复（1）（2）两个步骤;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Array.prototype.quickSort = function(){
    var arr = this,len = arr.length
    if(len<=1){
        return arr
    }
    //设定一个基准值的位置
    var pivotIndex = Math.floor(len/2)
    var pivot = arr.splice(pivotIndex,1)[0] //基准值
    var left=[],right=[]
    for(var i=0; i<len-1; i++){
        if(arr[i]<pivot){
            //比基准值小的放左边
            left.push(arr[i])
        }else{
             //比基准值大的放右边
            right.push(arr[i])
        }
    }
    //递归调用，把多个碎片有序小数组拼成一个新数组
    return left.quickSort().concat([pivot],right.quickSort())
}
console.log(data.quickSort())  //[0,2,3,4,5,5,6,7,8,9]

3.选择排序

思路解析：
（1）从数组的开头开始，将第一个元素和其他元素进行比较，检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续;

（2）选择排序会用到嵌套循环，外循环从数组的第一个元素移动到数组的倒数第二个元素，内循环从第二个数组元素移动到最后一个元素，查找比当前外循环所指向的元素小的元素;

（3）每次内循环迭代后，数组中最小的值都会被赋值到合适的位置;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Array.prototype.selectionSort = function(){
    var arr = this,len=arr.length,minIndex,temp
    for(var i=0; i<len-1; i++){
        //从数组的开头开始，将第一个元素和其他元素进行比较
        minIndex = i
        //从i的下一个开始，遍历剩下的，找出最小的往左放，最终依次都是从最小-->最大，实现排序
        for(var j=i+1;j<len;j++){
            if(arr[j]<arr[minIndex]){
                minIndex = j
            }
            temp = arr[i]
            arr[i]=arr[minIndex]
            arr[minIndex]=temp
        }
    }
    return arr
}
console.log(data.selectionSort())  //[0,2,3,4,5,5,6,7,8,9]

4.插入排序

思路解析：

（1） 从第一个元素开始，该元素可以认为已经被排序

（2） 取出下一个元素，在已经排序的元素序列中从后向前扫描

（3） 如果该元素（已排序）大于新元素，将该元素移到下一位置

（4） 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

（5）将新元素插入到下一位置中

（6） 重复步骤2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Array.prototype.insertionSort = function(){
    var arr = this,len=arr.length
    //假设第0个元素为有序的数列，第一个以后是无序的，所以for循环i从1开始
    for(var i=1; i<len; i++){
        if(arr[i]<arr[i-1]){
            //取出无序数列中的第i个作为待插入元素
               var guard = arr[i]
               var j = i-1
               //把刚刚取出元素的前一位挪到取出元素的原位置上
               arr[i] = arr[j]
        }
           //把取出元素插入到之前的有序数列中，并判断这个插入元素比有序数列中移动的数小，
           //直到guard==arr[j]时，不再拨动有序数列，就在arr[j+1]的位置上插入guard。
           //（可以想象在一排并排的小立方体调整顺序，先拿出一个小块，然后依次拨动之前的，为小块腾出位置插入）
        while(j>=0 && guard < arr[j]){
            arr[j+1]=arr[j]
            j--
        }
        //插入guard
        arr[j+1] = guard
    }
    return arr
}
 console.log(data.insertionSort())  //[0,2,3,4,5,5,6,7,8,9]

归并排序

思路解析：

（1）.把长度为n的输入序列分成两个长度为n/2的子序列；

（2）.对这两个子序列分别采用归并排序；

（3）.将两个排序好的子序列合并成一个最终的排序序列；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function mergeSort(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));
}
 
function merge(left, right)
{
    var result = [];
    console.time('归并排序耗时');
    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());
    console.timeEnd('归并排序耗时');
    return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));

制造随机数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
        function fn(n){
    if(typeof n !== "number"){
        console.log("参数类型错误")
        return 
    }
    var arrSet = new Set();
    while(arrSet.size<n){
        var num = Math.floor(100*Math.random())
        if( num <= 32 && num>=2){
            arrSet.add(num)
        }
    }
    return [...arrSet]

}
fn(20)

FEATURED TAGS
JavaScript Algorithms