JavaScript常见排序算法

排序对比

冒泡排序

• 设置两个变量i,j，i从0~length-1，j从0~length-i-1，进行遍历，外部循环i执行一次，内部循环j执行多次，每次都是从0开始比较当前元素和后一个元素，如果当前元素较大，则交换
• 结果：每次都是找到当前序列的最大一个元素放在末尾的固定位置，所以内部循环的length=length-i-1，因为后面的元素已经不需要在遍历，i共执行length-1次

function bubblesort(array) {
    let len = array.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    return array
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 4];
console.log(bubblesort(array));

选择排序

• 设置三个变量i,j,minIndex,i从0~length-1,j从i+1~length，minIndex每次循环开始都指向当前的i,内部循环比较j指向的元素与minIdex指向的元素的大小，然后将minIndex指向找到的最小元素，如果minIndex!=i说明找到，则交minIndex与i所指的元素
• 结果是每次都会在未排序列中找到最小元素，然后放到未排序列的首部

function selectSort(array) {
    let len = array.length;
    let minIndex,temp;
    for(let i = 0;i<len-1;i++){
        minIndex = i;
        for(let j = i+1;j<len;j++){
            if(array[j]<array[minIndex]){
                minIndex=j;
            }
        }
        if(minIndex!=i){
            temp=array[i];
            array[i]=array[minIndex];
            array[minIndex]=temp;
        }
    }
    return array;
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 4];
console.log(selectSort(array));

直接插入排序

• 设置三个变量i,j,key，默认第一个有序，所以i从1~length，每次循环都将j = i - 1，key = arr[i]，key保存当前的值，j指向前一个值，在j>=0的时候，比较前一个值和当前值的大小，如果前一个值大，则往后挪，同时j--，直到j<0或者前一个值小，说明当前元素已经找到了正确位置，就把key赋值给当前有序序列的末尾也就是j+1
• 结果是每次循环都是将当前元素从后往前插入到前面的有序序列中，每次循环有序序列个数+1

function insertSort(array) {
    let len = array.length;
    let key;
    for (let i = 1; i < len; i++) {
        key = array[i];
        let j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
    return array;
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 4];
console.log(insertSort(array));

快速排序

• 首先判断，如何数组中只有一个元素，则返回，否则，就找到中间元素为基准，比基准小的放left数组，比基准大的放right数组，然后递归调用

function quicksort(array) {
    if(array.length<=1){
        return array;
    }
    let index = Math.floor(array.length/2);
    let num = array.splice(index,1);
    let left=[],right=[];
    for(let i = 0;i<array.length;i++){
        if(array[i]<num){
            left.push(array[i]);
        }
        else {
            right.push(array[i]);
        }
    }
    return quicksort(left).concat(num,quicksort(right));
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 4];
console.log(quicksort(array));

归并排序（自上而下）

• 采用分治法，把长度为n的序列分成两个长度为n/2的子序列，然后对这两个子序列分别采用归并排序，最终再进行合并

function mergeSort(array) {
    if (array.length < 2) {
        return array;
    }
    let middle = parseInt(array.length / 2);
    let left = array.slice(0, middle);
    let right = array.slice(middle);
    return merge(mergeSort(left), mergeSort(right))
}
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());
        }
    }
    while (left.length){
        result.push(left.shift());
    }
    while (right.length){
        result.push(right.shift());
    }
    return result;
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 4];
console.log(mergeSort(array));

参考文章推荐
十大经典排序算法的 JS 版