JavaScript 排序算法

Posted on | In

这里列出了几种序算法（冒泡、选择、插入、归并、快速、希尔）。 排序动画

1.冒泡排序

比较任何两个相邻的项,如果第一个比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。冒泡排序的时间复杂度为O(n2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(arr) {
    let temp;
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

2.选择排序

一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位,接着找到第二小的值并将其放在第二位,以此类推。选择排序的时间复杂度为O(n2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectionSort(arr) {
    let len = arr.length;
    let min, temp;
    for (let i = 0; i < len - 1; i++) {
        min = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) { //寻找最小的数
                min = j; //将最小的数索的引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[min]; //交换最小数的位置
        arr[min] = temp;
    }
    return arr;
}

3.插入排序

将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

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

4.归并排序

采用分治法将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。时间复杂度为O(nlogn)，空间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function merge(leftArr, rightArr) {
    let result = [];
    while(leftArr.length > 0 && rightArr.length >0 ){
        if (leftArr[0] < rightArr[0]) {
            result.push(leftArr.shift()); // 把最小的最先取出，放到结果集中    
        }else{
            result.push(rightArr.shift());
        }
    }
    return result.concat(leftArr).concat(rightArr); //合并
}
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)); //递归合并与排序
}

5.快速排序

随机选取一个数组中的值作为基准值，从左至右取值与基准值对比大小。比基准值小的放数组左边，大的放右边，对比完成后将基准值和第一个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分，继续递归以上操作。该算法的复杂度和归并排序是相同的，但是额外空间复杂度比归并排序少，只需 O(logN)，并且相比归并排序来说，所需的常数时间也更少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function quickSort(arr) {
    if (arr.length <= 1) { return arr; }
    let left = [];
    let right = [];
    let pivotIndex = Math.floor(arr.length / 2); //基准位置
    let pivot = arr.splice(pivotIndex, 1)[0]; //基准数
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]); //比基准数小的放在left数组
        } else {
            right.push(arr[i]); //大于等于基准数的放在right数组
        }
    }
    return quickSort(left).concat([pivot], quickSort(right)); //递归处理，连接左数组、基准数、右数组
}

其他快速排序: https://github.com/dnxbf321/sort/blob/master/quick-sort.js

6.希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
function shellSort(arr) {
    let gaps = [5, 3, 1]; //定义间隔序列
    for (let g = 0; g < gaps.length; ++g) {
        for (let i = gaps[g]; i < arr.length; ++i) {
            let j, temp = arr[i];
            for (j = i; j >= gaps[g] && arr[j - gaps[g]] > temp; j -= gaps[g]) {
                arr[j] = arr[j - gaps[g]]; //根据间隔序列换位
            }
            arr[j] = temp;
        }
    }
    return arr;
}

系统自带排序

对于 JavaScript 系统自带排序来说，数组长度大于 10 会使用快速排序，否则使用插入排序 源码实现。选择插入排序是因为虽然时间复杂度很差，但是在数据量很小的情况下和 O(N * logN)相差无几，然而插入排序需要的常数时间很小，所以相对别的排序来说更快。