常见的排序算法

纪录下常见的几种排序

冒泡排序

原理：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法复杂度：

O(N2)

function bubblingSort(arr) {
    if(arr.length <= 1) return arr;

    for(let i=0; i<arr.length-1; i++) {
        for(let j=0; j<arr.length-1-i; j++) {
            if(arr[j] > arr[j+1]) {
                let s = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = s;
            }
        }
    }

    return arr;
}

const array = [44, 56, 34, 2, 4, 1, 3];

console.log(bubblingSort(array));

// [1, 2, 3, 4, 34, 44, 56]

选择排序

原理：

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3. 重复第二步，直到所有元素均排序完毕。

算法复杂度

O(n²)

    function selSort(arr) {
        if(arr.length <= 1) return arr;

        let minIndex;
        let len = arr.length;

        for(let i=0; i<len-1; i++) {
            minIndex = i;
            for(let j=i+1; j<len; j++) {
                if(arr[minIndex] > arr[j]) {
                    minIndex = j
                }
            }
            let temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }

        return arr;
    }

    console.log(selSort(array))

    // [1, 2, 3, 4, 34, 44, 56]

快速排序

原理：

取数组中间位置的一个数作为基准，通过跟基准数进行比较将数组分割成两部分，然后再进行前面两部分的操作，这一步可以用递归实现，从而实现排序。

算法复杂度

快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。

function fastSort(arr) {
    if(arr.length <= 1) return arr;

    let middle = arr.splice(Math.floor(arr.length/2), 1)[0];
    let left = [];
    let right = [];

    for(let i=0; i<arr.length; i++) {
        let item = arr[i];
        if(item <= middle) left.push(item);
        else right.push(item);
    }

    return fastSort(left).concat(middle, fastSort(right));
}

const array = [44, 56, 34, 2, 4, 1, 3];

console.log(fastSort(array));

// [1, 2, 3, 4, 34, 44, 56]