js十大基础排序算法

十大基础算法

1.冒泡排序（Bubble Sort）

（稳定的）时间复杂O(n^2)。

升序：寻找最大数，每次选取一个最大数，排最后

function bubbleSort(arr) {
    const len = arr.length;
    // 第一个循环是选出第i+1个最大数
    for (let i = 0; i < len - 1; i++) {
        // 从头遍历，相邻比较，大数往后，得到最后一个是最大数
        for (let j = 0; j < len - 1 - i; j++) {
            // 升序
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = temp;
            }
        }
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.选择排序（Selection Sort）

（不稳定）时间复杂O(n^2)

升序：寻找最大数，从头选取一个数，比较指针往后移，交换

function selectionSort(arr) {
    const len = arr.length;
    // 第一个循环选择第i个数进行排序
    for (let i = 0; i < len - 1; i++) {
        let minIdx = i;
        // 第二个循环，相邻比较，大时往后，小时停止，进行交换
        for (let j = i + 1; j < len; j++) {
            // 寻找最小数
            if (arr[j] < arr[minIdx]) {
                // 保存最小数index
                minIdx = j;
            }
        }
        [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.插入排序（Insertion Sort）

（升序）（稳定的）时间复杂O(n^2)

从头选取第二个数，比较,其他数往后移

function insertionSort(arr) {
    const len = arr.length;
    for (let i = 1; i < len; i++) {
        let current = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.希尔排序（Shell Sort）

（插入排序进阶版）（不稳定）时间复杂O(nlogn)

function shellSort(arr) {
    const len = arr.length;
    let gap = Math.floor(len / 2);
    while (gap > 0) {
        for (let i = gap; i < len; i++) {
            let temp = arr[i];
            let j = i - gap;
            while (j >= 0 && arr[j] > temp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = temp;
        }
        gap = Math.floor(gap / 2);
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5.归并排序（Merge Sort）

（稳定的）时间复杂度O(nlogn),空间复杂度O(n)

归并排序是自下而上。快速排序是自上而下

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    const mid = Math.floor(arr.length / 2);
    const leftArr = arr.slice(0, mid);
    const rightArr = arr.slice(mid);
    return merge(mergeSort(leftArr), mergeSort(rightArr));
}
function merge(leftArr, rightArr) {
    const result = [];
    let leftIdx = 0;
    let rightIdx = 0;
    while (leftIdx < leftArr.length && rightIdx < rightArr.length) {
        // 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定
        if (leftArr[leftIdx] <= rightArr[rightIdx]) {
            result.push(leftArr[leftIdx++]);
        } else {
            result.push(rightArr[rightIdx++]);
        }
    }
    return result.concat(leftArr.slice(leftIdx)).concat(rightArr.slice(rightIdx));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

6.快速排序一（Quick Sort）

（不稳定）时间复杂度O(nlogn),空间复杂O(n)不稳定

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    const pivot = arr[arr.length - 1];
    const leftArr = [];
    const rightArr = [];
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            leftArr.push(arr[i]);
        } else {
            rightArr.push(arr[i]);
        }
    }
    return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6.快速排序二（Quick Sort）

加入分区操作之后，（不稳定）空间复杂度O(1)

function quickSort(arr) {
    // 交换
    function sort(arr, left, right) {
        if (left > right) return;
        var storeIndex = partition(arr, left, right);
        sort(arr, left, storeIndex - 1);
        sort(arr, storeIndex + 1, right);
    }
    // 分区
    function partition(arr, left, right) {      
        // 开始时不知最终pivot的存放位置，可以先将pivot交换到后面去
        // 这里直接定义最右边的元素为基准
        var pivot = arr[right];
        // 存放小于pivot的元素时，是紧挨着上一元素的，否则空隙里存放的可能是大于pivot的元素，
        // 故声明一个storeIndex变量，并初始化为left来依次紧挨着存放小于pivot的元素。
        var storeIndex = left;
        for (var i = left; i < right; i++) {
            if (arr[i] < pivot) {
                // 遍历数组，找到小于的pivot的元素，（大于pivot的元素会跳过）
                // 将循环i次时得到的元素，通过swap交换放到storeIndex处，
                // 并对storeIndex递增1，表示下一个可能要交换的位置
                swap(arr, storeIndex, i);
                storeIndex++;
            }
        }
        // 最后： 将pivot交换到storeIndex处，基准元素放置到最终正确位置上
        swap(arr, right, storeIndex);
        return storeIndex;
    }
    // 交换函数
    function swap(arr, a, b) {
        var temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    sort(arr, 0, arr.length - 1);
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

7.堆排序（Heap Sort）

（不稳定）时间复杂度O(nlogn)

function heapSort(arr) {
    let len = arr.length;
    // 构建最大堆，从最底层的右边非叶子节点i开始,
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapify(arr, len, i);
    }
    // 依次将最大元素移到末尾并进行堆调整
    for (let i = len - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        // 因为最大值已经依次被换到最后面，所以堆排序的数组长度不能再包括后面已经排好的数
        // 所以这里不能写heapify(arr, len, 0),要把len改成i
        heapify(arr, i, 0);
    }
    return arr;
}
function heapify(arr, len, i) {
    let largest = i; // 初始化当前索引节点为最大值
    let left = 2 * i + 1; // 最大值的左子节点的索引
    let right = 2 * i + 2; // 最大值的右子节点的索引
    // 如果左子节点大于当前节点，则更新最大值索引
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
    // 如果右子节点大于当前节点，则更新最大值索引
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
    // 如果最大值索引不等于当前节点，则交换
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        // 交换之后，仍然要维护其以下的堆也保持大堆顶
        heapify(arr, len, largest);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

8.计数排序（Counting Sort）

时间和空间复杂度都是O(n) = O(n+k)，k为max-min

function countingSort(arr) {
    let max = Math.max(...arr)
    let min = Math.min(...arr)
    // 创建一个新数组，arr中的值变成countArr中的索引，索引的值为该数出现的次数
    let countArr = new Array(max - min + 1).fill(0)
    // i-min，（主要是为了负数索引变为正数索引）这样就可以将负整数的情况也考虑在内
    for (let i of arr) {
        countArr[i-min]++
    }
    // 读取数据并插入原数组的索引位置
    let numindex = 0
    for (let j = 0; j < countArr.length; j++) {
        while (countArr[j] > 0) {
            // 前面减了min这里必须加回去
            arr[numindex++] = j + min
            countArr[j]--
        }
    }
    return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

9.桶排序（Bucket Sort）

（每个桶是插入排序所以是稳定的）空间复杂度取决于嵌入的排序算法

function bucketSort(arr, bucketSize = 5) {
    if (arr.length === 0) {
        return arr;
    }
    let minValue = Math.min(...arr);
    let maxValue = Math.max(...arr);
    let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    let buckets = new Array(bucketCount);
    for (let i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
    for (let num of arr) {
        let bucketIndex = Math.floor((num - minValue) / bucketSize);
        buckets[bucketIndex].push(num);
    }
    let sortedArr = [];
    for (let bucket of buckets) {
      insertionSort(bucket);
      sortedArr.push(...bucket);
    }
    return sortedArr;
} 
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let current = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

10.基数排序（Radix Sort）

function radixSort(arr) {
    let max = Math.max(...arr);
    let maxLength = String(max).length;
    for (let i = 0; i < maxLength; i++) {
        // 每次循环都会按数值的某一位上的值进行排位，从个位到最高位
        let buckets = Array.from({ length: 10 }, () => []);
        for (let num of arr) {
            // 遍历的每个数值添加到，某一位上数值所对应的桶中
            let digit = Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
            buckets[digit].push(num);
        }
        // 每比较一位，都会重新更新arr中的排序
        arr = [].concat(...buckets);
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16