js排序算法

一、 冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。

平均复杂度：o(n^2) 空间复杂度：o(1) 稳定性：稳定

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

代码：

    // 冒泡排序 每次将最大的数值冒泡到最右面，并且执行下次外部循环时将右部最大数剔除，
    // 外部循环执行次数为: 数组长度-1（即假设最坏情况每个数都需要位移需要位移数组长度-1个数）
    // 内部循环次数为: 数组长度 - 当前已经选出右部最大数个数(i) - 1 （位移数比数组长度少一）
let a = [1, 3, 6, 2, 7];

for (let i = 0; i < a.length - 1; i++) {
        for (let j = 0; j < a.length - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                let c = a[j];
                a[j] = a[j + 1];
                a[j + 1] = c;
                // [a[j], a[j + 1]] = [a[j + 1], a[j]]
            }
        }
    }

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

二、选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
平均复杂度：o(n^2) 空间复杂度：o(1) 稳定性：不稳定

步骤：

1、每一次循环，找到最小的那个数，并用变量记住它的索引
2、然后将最小值放在它该在的位置上
3、持续对越来越少的元素重复上面的步骤

代码：

// 第一次循环找到数组中最小的数，并将其放在左面
// 之后的循环在数组剩余数中找到第二小的以此类推
for (let i = 0; i < a.length - 1; i++) {
        for (let j = i + 1; j < a.length; j++) {
            if (a[i] > a[j]) {
                let c = a[j];
                a[j] = a[i];
                a[i] = c;
                // [a[j], a[i]] = [a[i], a[j]]
            }
        }
    }

待确认(两种循环执行次数相同，但比选择排序交换次数要多)

// 其实就是先选取前两个数对比，大数放后面。第二次加入第三个数逐项对比，如果第三个数大于第一个数就和第一个数交换，之后第二个数和交换后的第三个数对比交换。即一个逐渐增加的数组进行排序，2个数据排序，3个数据排序，新加入的数据每个对比，符合条件交换（这步比插入排序多了，因为将已经排好的数组又便利一遍排序）
// 首先外部循环确定当前要比对的值a[i]
// 然后内部循环逐项对比数组a[i]之前的数a[j]与a[i]做比对,前一项大于后一项时交换位置。
for (let i = 1; i < a.length; i++) {
        for (let j = 0; j < i; j++) {
            if (a[i] < a[j]) {
                [a[j], a[i]] = [a[i], a[j]]
            }
        }
    }

三、插入排序

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

// 先确定第一个基准数据，由于需要对比所以第一个基准数据为a[1], i为1。 (这里基准数据为currentValue)
// 拿到基准数据后再确定基准数据的前一项(这里为a[flag])进行对比如果前一项大于基准数据则前一项向后移一位（a[flag + 1] = a[flag]）
// 移动完毕因为前面还有其他更多的数（前一项的前一项的前一项...）都需要和基准数比如果比基准数大则向后移一位
// 直到基准数大于（该前一项）将基准数插入到（该前一项的后面）（ a[flag + 1] = currentValue;）
// while循环停止的判断标准是执行到基准数大于等于（前一项）（a[flag] <= currentValue）
// 或者（前一项）不存在即数组的-1项时跳出循环 （flag < 0）
// 由于数组的-1项为undefined undefined和数字对比一定为false所以一定跳出while循环所以flag >= 0判断条件可以不写
for (let i = 1; i < a.length; i++) {
        flag = i - 1;
        currentValue = a[i];
        // flag >= 0  可以不写因为a[flag]为undefined undefined和任何数对比都为false可以终止while循环
        while (flag >= 0 && a[flag] > currentValue) {
            a[flag + 1] = a[flag]
            flag--;
        }
        a[flag + 1] = currentValue;
    }

四、快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

// 先选取一个基准数据（例如a[0]），定义为flag用来和这个基准数据做对比，并且从数组中删除该基准数。
// 然后定义空数组left和right, 将数组每项和基准数做对比，如果小于基准数放在left数组中，大于的话放在right数组中
// 分别递归调用处理left和right数组，将处理好的left数组、中间选取的基准数据和right数组合并
// 因为每次递归调用都要删除一个基准数据所以到最后这个数组长度为1时就直接返回数组
var a = [2, 8, 7, 5, 1, 9]

    function quickSort(arr) {
        if (arr.length <= 1) {
            return arr
        }
        let flag = arr[0];
        let left = [];
        let right = [];
        arr.splice(0, 1);
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] < flag) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }
        return quickSort(left).concat(flag, quickSort(right))
    }

    console.log(quickSort(a))

五、归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
(1） 把长度为n的输入序列分成两个长度为n/2的子序列；
（2）对这两个子序列分别采用归并排序；
（3） 将两个排序好的子序列合并成一个最终的排序序列。

download.png

// 将数组从中间分开为两个数组left和right，递归调用将分开的两个数组再次分别分为两个数组，直到该数组长度为1时
// 递归调用的同时将left和right第一项做对比小的放入到空数组中并删除最小项，并且将剩余的数组left和right数组合并（因为不能确定到底最后剩余的数组中left和right哪个大），其实每次对比的时候左右数组都是已经排序好的数组所以只需每次循环取出两数组中最小项即可排序，剩余的最大数还留在left或者right数组中需要通过concat合并过来
function mergeSort(arr) { //采用自上而下的递归方法
        var len = arr.length;
        if (len < 2) {
            return arr;
        }
        var middle = Math.floor(len / 2),
            left = arr.slice(0, middle),
            right = arr.slice(middle);
        return merge(mergeSort(left), mergeSort(right));
    }

    function merge(left, right) {
        var result = [];
        while (left.length && right.length) {
            // 不断比较left和right数组的第一项，小的取出存入res
            left[0] < right[0] ? result.push(left.shift()) : result.push(right.shift());
        }
        return result.concat(left, right);
    }

    console.log(mergeSort(a))

六、希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

function shellSort(arr) {
        for (let i = Math.floor(arr.length); i > 0; i = Math.floor(i / 2)) {
            for (let j = i; j < arr.length; j++) {
                let k = j;
                let currentValue = arr[j];
                while (k - i >= 0 && arr[k - i] > currentValue) {
                    arr[k] = arr[k - i];
                    k = k - i;
                }
                arr[k] = currentValue
            }
        }
    }

    var arr = [3, 5, 7, 1, 4, 56, 12, 78, 25, 0, 9, 8, 42, 37];
    shellSort(arr)
    console.log(arr)