应届生必须掌握的十大排序算法

冒泡排序

思路/原理：比较相邻的两个元素，如果前一个比后一个大，则交换位置，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。就好像一串气泡一样，最终从小到大或从大到小依次排下来。

function bubbleSort(arr) {            
    var len = arr.length;            
    // i表示第几趟排序            
    for(var i = 0; i < len - 1; 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;                        
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];                    
            }                                        
        }            
    }            
    return arr;        
}        
console.log(bubbleSort([3, 1, 8, 10, 5]));复制代码

时间复杂度: 平均情况O(n²)  最坏情况O(n²)  最好情况O(n)

空间复杂度: O(1)

稳定性: 稳定

由于冒泡 排序 只在相邻元素大小不符合要求时才调换他们的位置，它并不改变相同元素之间的相对顺序，因此它是稳定的排序算法。

复杂性: 简单

选择排序

思路/原理: 每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。

function selectSort(arr) {            
    var len = arr.length;            
    // 控制位置            
    for(var i = 0; i < len - 1; i++) {                            
        // 假如这个是最小的                
        var min = i;                
        // 与后面的数字进行比较 寻找最小值的索引                
        for(var j = i + 1; j < len; j++) {                    
            if(arr[j] < arr[min]) {                        
                min = j;                    
            }                
        }                
        // 如果当前的值的索引和最小值的索引不相等 交换位置                
        if(i !== min) {                    
            [arr[i], arr[min]] = [arr[min], arr[i]];                
        }                        
    }            
    return arr;        
}复制代码

思路/原理: 将排序分为排序与未排序，将未排序的数依次向排序数进行比较。

function insertSort(arr) {            
    var len = arr.length;            
    for (var i = 1; i < len; i++) {                
        var temp = arr[i]; // 要插入的元素                
        // 与前面的排序好的数组进行比较                 
        var j = i - 1;                
        while(j >= 0 && temp < arr[j]) {                    
            // 如果当前元素小于他们 则他们往后运动 并交换当前元素和他们的位置 否则不动                    
            arr[j + 1] = arr[j];                       
            j --;                
        }                 
        arr[j + 1] = temp;            
    }            
    return arr        
}        
console.log(insertSort([2, 1, 4, 8, 3]));                        复制代码

时间复杂度: 平均情况O(n²) 最坏情况O(n²) 最好情况O(n)

空间复杂度: O(1)

稳定性: 稳定

// 采用分而治之的思想 把数组以递归的方式分为左右相等的两个数组        
function mergeSort(arr) {            
    var len = arr.length;            
    // 递归出口            
    if(len < 2) {            
        return arr;            
    }            
    var mid = parseInt(len / 2),                
    left = arr.slice(0, mid),                
    right = arr.slice(mid);            
    return merge(mergeSort(left), mergeSort(right));            
}        
// 把两个数组进行排序        
function merge(left, right) {            
    var res = [];            
    while(left.length && right.length) {                
        if(left[0] < right[0]) {                    
            res.push(left.shift());                
        }else {                    
            res.push(right.shift());                
        }              
    }                        
    // 把剩余的数组连接                
    while(left.length) {                
        res.push(left.shift());            
    }            
    while(right.length) {                
        res.push(right.shift());            
    }            
    return res;        
}复制代码