JavaScript 实现3种排序算法

淡淡的烟草味﹌ 2022-05-30 02:37 188阅读 0赞

本文讲述了冒泡，插入，快速三大排序算法，个人感觉写的比较清晰，欢迎留言讨论。

/** * Created by Administrator on 2017/5/26. */
    /* 冒泡排序：外层循环控制比较次数， 内层循环控制arr[i]和arr[i+1]的大小，并判断arr[i]和arr[i+1]是否需要交换 */
    var arr=[2,4,3,1,5,7,6];
    
    function bubbleSort(arr){ 
        var len=arr.length
        for(var r=1;r<len;r++){
            for(var i=0;i<len-r;i++){
                if(arr[i]>arr[i+1]){
                    arr[i]=[arr[i+1],arr[i+1]=arr[i]][0];
                }
            }
        }
        return arr
    }
    console.log('这是冒泡排序算法'+bubbleSort(arr))
    /* 插入排序：原理：arr[p]和t比较之前，0~i-1的元素已经排好序了，只需要把t插入合适的位置即可。 step1:取出arr[i]的值，保存在t中，并把t放在擂台上； step2:定义p=i-1,通过循环比较变量arr[p]和定值t的大小，来判断arr[p]和arr[p+1]是否需要交换位置。 step3:如果arr[p]>t,则需要arr[p]要和arr[p+1]交换位置，然后p--;继续比较arr[p]和t的大小 如果arr[p]<t,或者p减到-1了，则说明arr[p]以前的都比t小，那么就设置arr[p+1]=t;并结束循环 (arr[p]的值已经被arr[p+1]拿走了) */
    function insertSort(arr){ 
        for(var i=1;i<arr.length;i++){
            var t=arr[i];
            var p=i-1;
            while(true){
                if(arr[p]<t||p<0){
                    arr[p+1]=t;
                    break;
                }
                if(arr[p]>t){
                    arr[p+1]=arr[p];
                    p--;
                }
            }
        }
        return arr;
    }
    console.log('这是插入排序算法'+insertSort(arr))
    /* 快速排序：把数组分为两份和中间值c，比较数组中的元素和中间值c的大小，依次迭代拼接 当分组的length小于1时，则没有必要排序。 */
    function quickSort(arr){ 
        if(arr.length<1){
            return arr;
        }else{
            var i=parseInt((arr.length-1)/2);
            var c=arr.splice(i,1)[0];
            var left=[];
            var right=[];
            for(var i=0;i<arr.length;i++){
                if(arr[i]<c){
                    left.push(arr[i]);
                }else{
                    right.push(arr[i]);
                }
            }
        }
        return quickSort(left).concat(c,quickSort(right));
    }
    console.log('这是快速排序算法'+quickSort(arr));