与其临渊羡鱼，不如退而结网。

前端一定要会的算法--排序

发表于 2018-02-09 | 分类于 algorithm | 阅读次数:

写在前面

最近也看了一些面经一些总结，排序是出现的频率最高的。今天就来总结一下最常出现的几个排序算法。包括Array对象自带的sort()方法，冒泡排序(BubbleSort)，快速排序(QuickSort)，选择排序(SeletionSort)，插入排序(InsertSort)。本文主要是直接丢代码，不做过多解释，毕竟基本都是数据结构的知识。

算法复杂度

排序方式	平均	最坏	最好	空间	稳定性
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(logn)	不稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定

Array.sort()

代码：

const arr = [22,12,4,45,3,87,77,43,55,42];

//默认是根据字符串unicode码进行排序
console.log(arr.sort());        //[ 12, 22, 3, 4, 42, 43, 45, 55, 77, 87 ]

//若想指定排序方式，则需要使用Array.sort(CompareFunction)
function compareFunc(a,b) {
    return a-b;
}
console.log(arr.sort(compareFunc));  //[ 3, 4, 12, 22, 42, 43, 45, 55, 77, 87 ]

//ES6中更优雅的写法
console.log(arr.sort((a,b)=>a-b));//[ 3, 4, 12, 22, 42, 43, 45, 55, 77, 87 ]

//从V8引擎源码来看，sort是js实现的，且算法是快速排序，实现方式更为复杂，主要是做了性能上的优化。

冒泡排序(BubbleSort)

代码

const arr = [22,12,4,45,3,87,77,43,55,42];
function bubbleSort(arr) {
    for(let i = 0 ; i < arr.length-1 ; i++){
        for(let j = 0 ; j < arr.length-1-i ; j++){
            if(arr[j]>arr[j+1]){
                swap(arr,j);
            }
        }
    }
    return arr;
}
function swap(arr,j) {
    let temp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = temp;
}
console.log(bubbleSort(arr));

复杂度

时间复杂度O(n²)。
空间复杂度O(1)。
是稳定排序。

改进，时间复杂度为O(n)

加一个标志位，如果没有进行交换，将标志位设置为false，表示排序完成。
记录最后一次交换的位置，因为最后一次交换的数，是在这一次排序当中最大的数，之后的数都比它大。在最佳状态下，时间复杂度也会缩到O(n)。

快速排序(QuickSort)

代码

//思路：找到一个基数，然后将比基数小的数放在基数的左边，将比基数大的放在基数的右边。
//之后进行递归那两组已经归类好的数组
const arr = [22,12,4,45,3,87,77,43,55,42];

function quickSort(arr) {
    if(arr.length <= 1){
        return arr;
    }
    let temp = arr[0];
    let right = [];
    let left = [];
    for(let i = 1 ; i < arr.length ; i++){
        if(arr[i]>temp){
            right.push(arr[i]);
        }else{
            left.push(arr[i]);
        }
    }
    return quickSort(left).concat([temp],quickSort(right));
}
console.log(quickSort(arr));

复杂度

时间复杂度：O(nlogn)。
空间复杂度：O(logn)。
是不稳定排序。

选择排序(SelectionSort)

代码

//思路：第一遍，从数组中选出最小的，与第一个元素进行交换；
//第二遍，从第二个元素开始，找出最小的，与第二个元素进行交换，以此循环，完成排序。
const arr = [22,12,4,45,3,87,77,43,55,42];
function SelectionSort(arr) {
    for(let i = 0 ; i < arr.length ; i++){
        for(let j = i+1 ; j < arr.length ; j ++){
            if(arr[i]>arr[j]){
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr;
}
console.log(selectionSort(arr));

复杂度

时间复杂度O(n²)。
空间复杂度O(1)。
该排序是不稳定排序。

插入排序(InsertSort)

代码

//思路：首先，循环原数组，然后将当前位置的元素，插入到之前已排好的数组中，依次操作。
const arr = [22,12,4,45,3,87,77,43,55,42];

function InsertSort(arr) {
    for(let i = 1 ; i < arr.length ; i ++){
        for(let j = i; j > 0 ; j--){
            if(arr[j-1]>arr[j]){
                [arr[j-1],arr[j]] = [arr[j],arr[j-1]];
            }else{
                break;
            }
        }
    }
    return arr;
}

console.log(insertSort(arr));

复杂度

时间复杂度O(n²)。
空间复杂度O(1)。
该排序是稳定排序。

堆排序

//构造大顶堆
function shiftDown(A, i, length) {
    let temp = A[i];                        // 当前父节点
    // j<length 的目的是对结点 i 以下的结点全部做顺序调整
    for(let j = 2*i+1; j<length; j = 2*j+1) {
        //temp = A[i];                        // 将 A[i] 取出，整个过程相当于找到 A[i] 应处于的位置
        if(j+1 < length && A[j] < A[j+1]) {
            j++;                            // 找到两个孩子中较大的一个，再与父节点比较
        }
        if(temp < A[j]) {
            [A[i],A[j]] = [A[j],A[i]];      // 如果父节点小于子节点:交换；否则跳出
            i = j;                          // 交换后，temp 的下标变为 j
        } else {
            break;
        }
    }
}
// 堆排序
function heapSort(A) {
    // 初始化大顶堆，从第一个非叶子结点开始
    for(let i = Math.floor(A.length/2-1); i>=0; i--) {
        shiftDown(A, i, A.length);
    }
    // 调整堆：排序，每一次for循环找出一个当前最大值，数组长度减一
    for(let i = Math.floor(A.length-1); i>0; i--) {
        [A[0],A[i]] = [A[i],A[0]];          // 根节点与最后一个节点交换
        shiftDown(A, 0, i);                 // 从根节点开始调整，并且最后一个结点已经为当前最大值，不需要再参与比较，所以第三个参数为 i，即比较到最后一个结点前一个即可
    }
    return A;
}

let Arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
console.log(heapSort(Arr));

归并排序

归并排序的算法思路是，将两个有序的数组合并为一个有序数组往往比直接处理一个无序数组容易。为此，归并排序要创建n个只有一个元素的列表，其中n为要排序的列表的长度，然后再将这些列表合并为单个有序列表。

let arr = [22,23,34,12,123,5,67,44,32];
function merge(left,right) {
    let result = [];
    while(left.length && right.length){
        if(left[0] < right[0]){
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    return result.concat(left,right);
}
function mergeSort(arr){
    if(arr.length <= 1) return arr;
    let middle = Math.floor(arr.length/2);
    let left = arr.slice(0,middle);
    let right = arr.slice(middle);
    return merge(mergeSort(left),mergeSort(right));
}
console.log(mergeSort(arr));	//[ 5, 12, 22, 23, 32, 34, 44, 67, 123 ]

复杂度

时间复杂度O(nlogn)。
空间复杂度O(n)。
该排序是稳定排序。

常见代码题

ajax

//ajax请求
function sendAjax(){
    let xhr = new XMLHttpRequest();
    xhr.onreadystatechange = function(){
        if(xhr.readyState === 0){
            //todo loading
        }
        if(xhr.readyState === 4){
            if(xhr.status >= 200 && xhr.status < 300 || xhr.status === 304){
                alert(xhr.responseText)
            }else{
                alert("fail:",xhr.status);
            }
        }
    }
    xhr.open("method","url","true");
    xhr.send();
}

字符串翻转

//字符串翻转
function reverse(str){
    return str.split("").reverse().join("");
}
console.log(reverse("123456"));

二分查找

//二分查找
function middleSearch(arr,target,startIndex,endIndex){
    if(!target || !(arr instanceof Array)) return;
    var len = arr.length,
    startIndex = typeof startIndex === 'number'?startIndex:0,
    endIndex = typeof endIndex === 'number'?endIndex:len-1,
    midIndex = Math.floor((startIndex+endIndex)/2),
    midVal = arr[midIndex];
    if(startIndex>endIndex){
        return;
    }
    if(midVal === target){
        return midIndex;
    }else if(midVal > target){
        return middleSearch(arr,target,startIndex,midIndex-1);
    }else{
        return middleSearch(arr,target,midIndex+1,endIndex);
    }
}
console.log(middleSearch([1,2,3,4,5,6,7,7,8],4))

大数相加

//大数相加
function bigAdd(str1,str2){
    let result = '',
    carry = 0;
    str1 = str1.split('');
    str2 = str2.split('');
    while(str1.lenhth || str2.length || carry){
        let temp = parseInt(str1.pop()||0) + parseInt(str2.pop()||0) + carry;
        result = temp % 10 + result;
        carry = Math.floor(temp/10);
    }
    return result;
}
console.log(bigAdd("123","345"));

实现bind

//实现bind
function LikeBind(context){
    let [self,args] = [this,[]];
    args = Array.prototype.slice.call(arguments);
    return function(){
        args = args.concat(Array.prototype.slice.call(arguments));
        return self.apply(context,args);
    }
}

继承

//继承
//原型继承
//对象会被多个实例共享
function Parent1(){
    this.name = "原型继承：wzb";
}
Parent1.prototype.getName = function(){
    console.log(this.name);
}

function Child1(){

}
Child1.prototype = new Parent1();
var child1 = new Child1();
child1.getName();

//借用构造函数继承
//方法需全部在构造函数中定义
function Parent2(name){
    this.name = name;
}
function Child2(name){
    Parent2.call(this,name);
}
let child2 = new Child2("借用构造函数继承：wzb");
console.log(child2.name);

//组合继承
function Parent3(name){
    this.name = name;
    this.colors = ["red","black"];
}
Parent3.prototype.getName = function(){
    console.log("组合继承：",this.name);
}
function Child3(name,age){
    Parent3.call(this,name);
    this.age = age;
}
Child3.prototype = new Parent3();
Child3.prototype.constructor = Child3;
let child3 = new Child3("wzb","123");
console.log(child3.getName());

二叉排序树

/**
 * * 创建排序二叉树的构造函数
 * * @param valArr 排序二叉树中节点的值
 * * @constructor
 * */
function BinaryTree(valArr) {
    function Node(val) {
        this.value = val;
        this.left = null;
        this.right = null;
    }
    var root = null;
    valArr.forEach(function (val) {
        var newNode = new Node(val);
        if(root === null){
            root = newNode;
        } else {
            this.insetNode(root,newNode);
        }
    },this);
    this.root = root;
}
// 向二叉树中插入节点
BinaryTree.prototype.insetNode = function (node, newNode) {
    if(newNode.value > node.value){
        if(node.right === null){
            node.right = newNode;
        } else {
            this.insetNode(node.right,newNode);
        }
    } else {
        if(node.left === null){
            node.left = newNode;
        } else {
            this.insetNode(node.left,newNode);
        }
    }
};
// 中序遍历
BinaryTree.prototype.LFR = function () {
    const result = [];
    function computed(node) {
        if(node !== null ){
            computed(node.left);
            result.push(node.value);
            computed(node.right);
        }
    }
    computed(this.root);
    return result;
};
// 前序遍历
BinaryTree.prototype.FLR = function () {
    const result = [];
    function computed(node) {
        if(node !== null ){
            result.push(node.value);
            computed(node.left);
            computed(node.right);
        }
    }
    computed(this.root);
    return result
};
// 后序遍历
BinaryTree.prototype.RFL = function () {
    const result = [];
    function computed(node) {
        if(node !== null ){
            computed(node.right);
            result.push(node.value);
            computed(node.left);
        }
    }
    computed(this.root);
    return result
};
// 获取二叉树中的最小值
BinaryTree.prototype.getMin = function (node) {
    var min = null;
    function computed(node) {
        if(node){
            if(node.left){
                computed(node.left);
            } else {
                min = node.value;
            }
        }
    }
    computed(node || this.root);
    return min;
};
// 获取二叉树中的最大值
BinaryTree.prototype.getMax = function (node) {
    var Max = null;
    function computed(node) {
        if(node){
            if(node.right){
                computed(node.right);
            } else {
                Max = node.value;
            }
        }
    }
    computed(node || this.root);
    return Max;
};
// 查找给定值
BinaryTree.prototype.findVal = function (val,node) {
    function find(node) {
        if(node){
            if(node.value === val) return true;
            else if(val > node.value) return find(node.right);
            else {
                return find(node.left);
            }
        } else {
            return false;
        }

    }
    return find(node || this.root);
};
// 删除节点
BinaryTree.prototype.removeNode = function (val,node) {
    function remove(val,node) {
        if(!node) return null;
        if(val > node.value) {
            node.right =  remove.call(this,val,node.right);
        } else if(val < node.value){
            node.left =  remove.call(this,val,node.left);
        } else {
            // 要删除的节点没有左孩子也没有右孩子
            if(node.right === null && node.left === null){
                return null;
            }
            // 只有右孩子没有左孩子
            else if(node.right && node.left === null){
                return node.right;
            }
            // 只有左孩子没有右孩子
            else if (node.left && node.right === null) {
                return node.left;
            }
            // 有左孩子也有右孩子
            else {
                var min = this.getMin(node.right);
                node.value = min;
                node.right =  remove.call(this,min, node.right);
                return node;
            }
        }
        return node;
    }
    remove.call(this,val,node || this.root);
};
var binaryTree = new BinaryTree([10,4,2,14,3,15,13,12,6,9]);
console.log('中序遍历',binaryTree.LFR());
console.log('前序遍历',binaryTree.FLR());
console.log('后序遍历',binaryTree.RFL());
console.log('最小值',binaryTree.getMin());
console.log('最大值',binaryTree.getMax());
console.log(binaryTree.findVal(4));
binaryTree.removeNode(3);

排序

//sort
let arr = [1,2,3,4,5,6,7,8,9,0];

//乱序
function disorder(arr){
    arr = arr.sort(()=>{
        return Math.random() - 0.5;
    })
    console.log("disorder:",arr);
    return arr;
}

//冒泡
function BubbleSort(arr){
    for(let i = 0 ; i < arr.length-1 ; i++){
        for(let j = 0 ; j < arr.length-i-1 ; j++){
            if(arr[j] > arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]];
            }
        }
    }
    return arr;
}
console.log("BubbleSort(O(n²)，稳定):",BubbleSort(disorder(arr)));

//快速排序
function QuickSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    let [temp,left,right] = [arr[0],[],[]];
    for(let i = 1 ; i < arr.length ; i++){
        if(arr[i] > temp){
            right.push(arr[i]);
        }else{
            left.push(arr[i]);
        }
    }
    return QuickSort(left).concat([temp],QuickSort(right));
}
console.log("QuickSort(O(nlogn),不稳定):",QuickSort(disorder(arr)));

//选择排序
function SelectionSort(arr){
    for(let i = 0 ; i < arr.length ; i ++){
        for(let j = i+1 ; j < arr.length ; j++){
            if(arr[i]>arr[j]){
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr;
}
console.log("SelectionSort:(O(n²)，不稳定)：",SelectionSort(disorder(arr)));

//插入排序
function InsetSort(arr){
    for(let i = 1 ; i < arr.length ; i++){
        for(let j = 0 ; j < i ; j++){
            if(arr[i] < arr[j]){
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr;
}
console.log("InsetSort(O(n²)，稳定):",InsetSort(disorder(arr)));

//归并排序
function merge(left,right){
    let result = [];
    while(left.length && right.length){
        if(left[0] < right[0]){
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    return result.concat(left,right);
}
function mergeSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    let middle = Math.floor(arr.length/2);
    let left = arr.slice(0,middle);
    let right = arr.slice(middle);
    return merge(mergeSort(left),mergeSort(right));
}
console.log("mergeSort(O(nlogn)，稳定):",mergeSort(disorder(arr)));