Javascript 排序算法总结

1.冒泡排序

像水里的冒泡一样，水底的小气泡升到顶部，变成大气泡。冒泡排序就是每次循环都将最大的数值放到右边

function BubbleSort(array) {
            for (let i = 0; i < array.length - 1; i++) { //循环了多少次
                for (j = 0; j < array.length - i - 1; j++) { //每次循环比较多少次
                    if (array[j] > array[j + 1]) {
                        [array[j], array[j + 1]] = [array[j + 1], array[j]]
                    }
                }
            }
            return array;
        }
 

比较次数：(N-1) + (N-2) + · · · + 3 + 2 + 1 = (N * N-1)/2

比较次数时间复杂度：O(N^2)

每次比较都要交换，效率一般，但概念容易理解

2.选择排序

每次排序都选择最小的一个放在左边

function selectionSort(array) {
            for (let i = 0; i < array.length - 1; i++) { //循环了多少次 比较至倒数第二个即可
                let min = i
                for (let j = i + 1; j < array.length; j++) { //每次循环比较多少次
                    if (array[min] > array[j]) {
                        min = j
                    }
                }
                [array[min], array[i]] = [array[i], array[min]]
            }
            return array
        }
 

比较次数：(N-1) + (N-2) + · · · + 3 + 2 + 1 = (N * N-1)/2

比较次数时间复杂度：O(N^2)

交换次数：N-1

交换次数时间复杂度：O(N)

交换次数少，执行效率上高于冒泡排序

3.插入排序

原理是局部有序，从第二个位置开始，每次循环与左边的数字比较，插入到合适的位置

function insertSort(array) {
            for (let i = 1; i < array.length; i++) {
                let temp = array[i] //temp是要比较的数据
                let j = i
                while (temp < array[j - 1] && j > 0) { //因为左边局部有序，先与左边一位的数字比较，小于才向左继续比较
                    array[j] = array[j - 1]
                    j--
                }
                array[j] = temp //j已经--了，此时替换的是j的位置
            }
            return array
        }
 

最多比较次数：1 + 2 + 3 + · · · + (N-2) + (N-1) = (N * N-1)/2

平均比较次数：(N * N-1)/4

则平均复制次数：(N * N-1)/4

比较次数时间复杂度：O(N^2)

4.快速排序

快速排序的思想是分而治之，选择一个数据作为枢纽，将小于该枢纽的数字移到左边，将大于该枢纽的数字移到右边，左右两块区域继续相同的操作，从而实现排序

function quiceSort(arr) {
            if (arr.length <= 1) {
                return arr
            };
            let pivotIndex = Math.floor(arr.length / 2) //基准位置
            let pivot = arr.splice(pivotIndex, 1)[0] //基准数
            let left = []
            let right = []
            for (var i = 0; i < arr.length; i++) {
                if (arr[i] < pivot) {
                    left.push(arr[i])
                } else {
                    right.push(arr[i])
                }
            }
            return quiceSort(left).concat([pivot], quiceSort(right))
        }
 

比较次数时间复杂度：O(N*logN)