常见排序算法(JS篇)

冒泡排序

原理

通过比较相邻的两个数，如果后一个数比前一个数小，则交换它们的位置。重复这个过程，直到所有的数都按照从小到大的顺序排列。

代码中使用了两层嵌套的循环。外层循环控制比较的轮数，内层循环用于比较相邻的两个数并交换位置。

下面代码添加了一个标志位来判断是否发生了交换，如果某一轮比较中没有发生交换，说明数组已经有序，可以提前结束循环。

时间复杂度 O(n ^ 2) n为数组长度

空间复杂度 O(1)

算法稳定性 稳定

let array = [3, 1, 4, 6, 5, 7, 2];

function bubbleSort(arr) {
    const len = arr.length;
    for(let i = 0; i < len - 1; i++) {
        let swapped = false; // 标志位，判断是否发生交换
        for(let j = 0; j < len - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true; // 发生交换
            }
        }
        if(!swapped) {
            break;
        }
    }
    return arr;
}

console.log(bubbleSort(array)); // [1, 2, 3, 4, 5, 6, 7]

选择排序

原理

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。依次类推完成整个数组的排序。

时间复杂度 O(n ^ 2) n为数组长度

空间复杂度 O(1)

算法稳定性 不稳定

let array = [3, 1, 4, 6, 5, 7, 2];

function selectionSort(arr) {
    const len = arr.length;
    for(let i = 0; i < len - 1; i++) {
        let minIndex = i;
        for(let j = i; j < len; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if(i !== minIndex) {
            let temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
            // [ arr[i], arr[minIndex] ] = [ arr[minIndex], arr[i] ]; //交换位置
        }
    }
    
    return arr;
}

console.log(selectionSort(array)); // [1, 2, 3, 4, 5, 6, 7]

插入排序

原理

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的过程，就如同打扑克牌时，不断整理放入手中的牌一样，即每次拿到一张牌，按大小顺序（从大到小或从小到大，一般都是这样吧）将其插入到合适的位置。

为了方便理解，这里大致模拟一下摸牌过程（从小到大）：

第一次摸到一张 9。
第二次摸到一张 6，它比 9 小，要放在 9 的前面。
第三次摸到一张 10，它比 9 大，要放到 9 的后面。

以此类推（仅为便于理解，所以过程不是很严谨），直到所有的牌摸完。

所以，我们可以将插入排序理解为: 每次将一个新数据插入到有序队列中的合适位置里。

时间复杂度 最坏O(n^2) 最好O(n)

空间复杂度 O(1)

算法稳定性 稳定

let array = [3, 1, 4, 6, 5, 7, 2];

function insertSort(arr) {
    const len = arr.length;
    for(let i = 1; i < len; i++) {
        let temp = arr[i];
        let j = i;
        for(; j > 0; j--) {
            if (temp > arr[j - 1]) {
                break; // 当前考察的数大于前一个数，证明有序，退出循环
            } 
            arr[j] = arr[j - 1]; // 将前一个数复制到后一个数上
        }
        arr[j] = temp; // 找到考察的数应处于的位置
    }
    
    return arr;
}

console.log(insertSort(array)); // [1, 2, 3, 4, 5, 6, 7]

归并排序

原理

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

时间复杂度 O(nlogn)

空间复杂度 O(n)

算法稳定性 稳定

let array = [3, 1, 4, 6, 5, 7, 2];

function merge(left, right) {
    let result = [];
    while(left.length > 0 && right.length > 0) {
        if(left[0] < right[0]) {
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    
    return result.concat(left).concat(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(array)); // [1, 2, 3, 4, 5, 6, 7]

快速排序

原理

采用二分法，取出中间数，数组每次和中间数比较，小的放到左边，大的放到右边。

在数据集之中，找一个基准点
建立两个数组，分别存储左边和右边的数组
利用递归进行下次比较
快速排序的时间复杂度为 O(nlogn)，是一种高效的排序算法

时间复杂度 平均O(nlogn)，最坏O(n2)，实际上大多数情况下小于O(nlogn)

空间复杂度 O(logn)

算法稳定性 不稳定

let array = [3, 1, 4, 6, 5, 7, 2];

function quickSort(arr) {
    if(arr.length === 0) {
        return [];
    }
    const middleIndex = Math.floor(arr.length / 2);
    let c = arr.splice(middleIndex, 1);
    let left = [];
    let right = [];
    
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < c) {
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    
    return quickSort(left).concat(c, quickSort(right));
    
}

console.log(quickSort(array)); // // [1, 2, 3, 4, 5, 6, 7]