乐趣区

关于前端:金九银十跳槽季七种排序算法

jiezi

关注公众号“执鸢者 ”，获取大量教学视频及 私人总结面筋（公众号原创文章）并进入 业余交换群

被前端面试中算法虐惨的小林筹备大干一场，好好筹备一下面试中的高频算法题，因为前端算法相比于后端手撕的算法较容易，所以小林筹备从最根底的七种排序算法开始。后方高能，请抓住方向盘……

一、冒泡排序

冒泡排序的思路：遍历数组，而后将最大数沉到最底部；<br/>工夫复杂度：O(N^2)；<br/>空间复杂度：O(1)

function BubbleSort(arr) {if(arr == null || arr.length <= 0){return [];
    }
    var len = arr.length;
    for(var end = len - 1; end > 0; end--){for(var i = 0; i < end; i++) {if(arr[i] > arr[i + 1]){swap(arr, i, i + 1);
            }
        }
    }
    return arr;
}
function swap(arr, i, j){// var temp = arr[i];
    // arr[i] = arr[j];
    // arr[j] = temp;
    // 替换也能够用异或运算符
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

二、抉择排序

抉择排序的实现思路：遍历数组，把最小数放在头部；<br/>工夫复杂度：O(N^2)；<br/>空间复杂度：O(1)

function SelectionSort(arr) {if(arr == null || arr.length < 0) {return [];
    }
    for(var i = 0; i < arr.length - 1; i++) {
        var minIndex = i;
        for(var j = i + 1; j < arr.length; j++) {minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr, i, minIndex);
    }
    return arr;
}

function swap(arr, i, j) {arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

三、插入排序

插入排序实现思路：将一个新的数，和后面的比拟，只有以后数小于前一个则和前一个替换地位，否则终止；<br/>工夫复杂度：O(N^2)；<br/>空间复杂度：O(1)

function insertSort(arr) {if(arr == null  || arr.length <= 0){return [];
    }
    var len = arr.length;
    for(var i = 1; i < len; i++) {for(var j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {swap(arr, j, j + 1);
        }
    }
    return arr;
}

function swap(arr, i, j){var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

四、归并排序

归并排序的思路：<br/>1. 先左侧局部排好序 <br/>2. 再右侧局部排好序 <br/>3. 再筹备一个辅助数组，用外排的形式，小的开始填，直到有个动到开端，将另一个数组残余局部拷贝到开端 <br/>4. 再将辅助数组拷贝回原数组 <br/>工夫复杂度:O(N * logN)<br/>空间复杂度:O(N)

// 递归实现

function mergeSort(arr){if(arr == null  || arr.length <= 0){return [];
    }
    sortProcess(arr, 0, arr.length - 1);
    return arr;
}

function sortProcess(arr, L, R){
    // 递归的终止条件，就是左右边界索引一样
    if(L == R){return;}
    var middle = L + ((R - L) >> 1);// 找出两头值
    sortProcess(arr, L, middle);// 对左侧局部进行递归
    sortProcess(arr, middle + 1, R);// 对右侧局部进行递归
    merge(arr, L, middle, R);// 而后利用外排形式进行联合
}

function merge(arr, L, middle, R){var help = [];
    var l = L;
    var r = middle + 1;
    var index = 0;
    // 利用外排形式进行
    while(l <= middle && r <= R){help[index++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
    }
    while(l <= middle){help.push(arr[l++]);
    }
    while(r <= R){help.push(arr[r++]);
    }

    for(var i = 0; i < help.length; i++) {arr[L + i] = help[i];
    }
    //arr.splice(L, help.length, ...help);// 这个利用了 ES6 的语法
}
// 循环实现

function mergeSort(arr){if(arr ==null || arr.length <= 0){return [];
    }
    var len = arr.length;
    // i 每次乘 2，是因为每次合并当前小组元素就变成两倍个了
    for(var i = 1; i < len; i *= 2){
        var index = 0;// 第一组的起始索引
        while(2 * i  + index <= len){
            index += 2 * i;
            merge(arr, index - 2 * i, index - i, index);
        }
        // 阐明残余两个小组，但其中一个小组数据的数量曾经有余 2 的幂次方个
        if(index + i < len){merge(arr, index, index + i, len);
        }
    }
    return arr;
}

// 利用外排的形式进行联合
function merge(arr, start, mid, end){
    // 新建一个辅助数组
    var help = [];
    var l = start, r = mid;
    var i = 0;
    while(l < mid && r < end){help[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
    }
    while(l < mid){help[i++] = arr[l++];
    }
    while(r < end){help[i++] = arr[r++];
    }
    for(var j = 0; j < help.length; j++){arr[start + j] = help[j];
    }
}

五、疾速排序

疾速排序实现思路：随机取出一个值进行划分，大于该值放左边，小于该值放右边（该算法在经典快排的根底上通过荷兰国旗思维和随机思维进行了革新）<br/>工夫复杂度：O(N*logN) <br/>空间复杂度：O(logN)

function quickSort(arr) {if(arr == null || arr.length <= 0){return [];
    }
    quick(arr, 0, arr.length - 1);
}

function quick(arr, L, R){
    // 递归完结条件是 L >= R
    if(L < R){
        // 随机找一个值，而后和最初一个值进行替换，将经典排序变为疾速排序
        swap(arr, L + Math.floor(Math.random() * (R - L + 1)), R);
        // 利用荷兰国旗问题取得划分的边界，返回的值是小于区域的最大索引和大于区域的最小索引，在这利用荷兰国旗问题将等于区域局部就不必动了
        var tempArr = partition(arr, L, R, arr[R]);
        quick(arr, L, tempArr[0]);
        quick(arr, tempArr[1], R);
    }
}
// 返回值是小于区域最初的索引和大于区域的第一个索引
function partition(arr, L, R, num){
    var less = L - 1;
    var more = R + 1;
    var cur = L;
    while(cur < more){if(arr[cur] < num){swap(arr, ++less, cur++);
        }else if(arr[cur] > num) {swap(arr, --more, cur);
        }else{cur++;}
    }
    return [less, more];
}
function swap(arr, i, j){var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

六、堆排序

堆排序思路：<br/>1. 让数组变成大根堆 <br/>2. 把最初一个地位和堆顶做替换 <br/>3. 则最大值在最初，则剩下局部做 heapify，则从新调整为大根堆，则堆顶地位和该局部最初地位做替换 <br/>4. 反复进行，直到减完，则这样最初就调整结束，整个数组排完序（为一个升序）<br/>工夫复杂度:O(N * logN)<br/>空间复杂度:O(1)

function heapSort(arr) {if(arr == null || arr.length <= 0) {return [];
    }

    // 首先是建设大顶堆的过程
    for(var i = 0; i < arr.length; i++) {heapInsert(arr, i);
    }
    var size = arr.length;// 这个值用来指定多少个数组成堆，当失去一个排序的值后这个值减一
    // 将堆顶和最初一个地位替换
    /**
     * 当大顶堆建设实现后，而后一直将最初一个地位和堆顶替换；* 这样最大值就到了最初，则剩下局部做 heapify，从新调整为大根堆，则堆顶地位和倒数第二个地位替换，反复进行，直到全副排序结束 */
    // 因为后面曾经是大顶堆，所以间接替换
    swap(arr, 0, --size);
    while(size > 0) {
        // 从新变成大顶堆
        heapify(arr, 0, size);
        // 进行替换
        swap(arr, 0, --size);
    }
}

// 加堆过程中
function heapInsert(arr, index) {
    // 比拟以后地位和其父地位，若大于其父地位，则进行替换，并将索引挪动到其父地位进行循环，否则跳过
    // 完结条件是比父地位小或者达到根节点处
    while(arr[index] > arr[parseInt((index - 1) / 2)]){
        // 进行替换
        swap(arr, index, parseInt((index - 1) / 2));
        index = parseInt((index - 1) / 2);
    }
}
// 减堆过程
/**
 * size 指的是这个数组前多少个数形成一个堆
 * 如果你想把堆顶弹出，则把堆顶和最初一个数替换，把 size 减 1，而后从 0 地位经验一次 heapify，调整一下，残余局部变成大顶堆 */
function heapify(arr, index, size) {
    var left = 2 * index + 1;
    while(left < size) {var largest = (left + 1 < size && arr[left] < arr[left + 1]) ? left + 1 : left;
        largest = arr[index] > arr[largest] ? index : largest;

        // 如果最大值索引和传进来索引一样，则该值达到指定地位，间接完结循环
        if(index == largest) {break;}

        // 进行替换，并扭转索引和其左子节点
        swap(arr, index, largest);
        index = largest;
        left = 2 * index + 1;
    }
}

function swap(arr, i, j) {var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

七、桶排序

桶排序会经验三次遍历：筹备一个数组、遍历一遍数组、重构一遍数组，是非基于比拟的排序，上面以一个问题来论述其思路。<br/>问题：<br/> 给定一个数组，求如果排序之后，相邻两个数的最大差值，要求工夫复杂度 O(N), 且要求不能用基于比拟的排序 <br/>
思路：<br/>1. 筹备桶：数组中有 N 个数就筹备 N + 1 个桶 <br/>2. 遍历一遍数组，找到最大值 max 和最小值 min
。若 min = max，则差值 =0；若 min≠max，则最小值放在 0 号桶，最大值放在 N 号桶，剩下的数属于哪个范畴就进哪个桶 <br/>3. 依据鸽笼原理，则必定有一个桶为空桶，设计该桶的目标是为了否定最大值在一个桶中，则最大差值的两个数肯定来自于两个桶，但空桶两侧并不一定是最大值 <br/>4. 所以只记录所有进入该桶的最小值 min 和最大值 max 和一个布尔值示意该桶有没有值 <br/>5. 而后遍历这个数组，如果桶是空的，则跳到下一个数，如果桶非空，则找前一个非空桶，则最大差值 = 以后桶 min – 上一个非空桶 max，用全局变量更新最大值 <br/>工夫复杂度：O(N)<br/>空间复杂度：O(N)

function maxGap(arr) {if(arr == null || arr.length <= 0) {return 0;}
    var len = arr.length;
    var max = -Infinity, min = Infinity;
    // 遍历一遍数组, 找到最大值 max 和最小值 min
    for(var i = 0; i < len; i++) {max = max > arr[i] ? max : arr[i];
        min = min > arr[i] ? arr[i] : min;
    }

    // 若 min = max, 则差值为 0;
    if(min == max) {return 0;}

    var hasNum = new Array(len + 1);
    var mins = new Array(len + 1);
    var maxs = new Array(len + 1);

    var bid = 0;// 指定桶的编号

    for(var i = 0; i < len; i++) {bid = bucket(arr[i], min, max, len);// 取得该值是在哪个桶 // 因为有 N + 1 个桶，所以距离就是 N 个，所以此处除以的是 len，而后通过这个函数失去应该放到哪个桶里
        maxs[bid] = hasNum[bid] ? Math.max(arr[i], maxs[bid]) : arr[i];
        mins[bid] = hasNum[bid] ? Math.min(arr[i], mins[bid]) : arr[i];
        hasNum[bid] = true;
    }

    var res = 0;
    var lastMax = maxs[0];

    for(var i = 0; i < len + 1; i++) {if(hasNum[i]) {res = Math.max(mins[i] - lastMax, res);
            lastMax = maxs[i];
        }
    }
    return res;
}

// 取得桶号
// 这个函数用于判断在哪个桶中，参数别离为值、最小值、最大值、桶距离
function bucket(value, min, max, len) {return parseInt((value - min) / ((max - min) / len));
}

欢送老铁们加群或者私聊

退出移动版