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

写在前面

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

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)

1. 加一个标志位，如果没有进行交换，将标志位设置为false，表示排序完成。
2. 记录最后一次交换的位置，因为最后一次交换的数，是在这一次排序当中最大的数，之后的数都比它大。在最佳状态下，时间复杂度也会缩到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() {
    for(let i = 0 ; i < arr.length ; i++){
        let index = i;
        for(let j = i+1 ; j < arr.length ; j++){
            if(arr[index] > arr[j]){
                index = j;
            }
        }
        swap(arr,index,i);
    }
    return arr;
}
//将目前数组中最小的元素放到第i个位置
function swap(arr,index,i) {
    let temp = arr[index];
    arr[index] = arr[i];
    arr[i] = temp;
}
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 = 0 ; i < arr.length ; i++){
        let temp = arr[i];
        for(let j = 0 ; j < i ; j++){
            if(temp < arr[j] && j === 0){
                arr.splice(i,1);    //从索引为i的位置删除一项。
                arr.unshift(temp);  //将元素temp增加到数组的开头
                break;
            }else if(temp > arr[j] && temp < arr[j+1] && j < (i-1)){
                arr.splice(i,1);
                arr.splice(j+1,0,temp); //在索引为j+1的位置插入temp
                break;
            }
        }
    }
    return arr;
}

console.log(insertSort(arr));

复杂度

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

推荐大家去看这个人的mianjing。里面还讲到了基数排序和归并排序，有时间再补上。