1.排序的定义

排序就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

2.冒泡排序

冒泡排序的思路是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序位置。

内层循环结束一次可以得到一个最大值或最小值。时间复杂度为O(n²)。

    function bubbleOrder(arr) {
        var temp = 0;
        for (var i = 0; i < arr.length; i++) {
            for (var j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }复制代码

3.简单选择排序

简单选择排序是将下标i作为假定的最小值,再将i+1至n的记录的关键字与i的关键字比较,选出其中的最小值,并和i的值交换。

简单选择排序与冒泡排序时间复杂度相同,但元素移动次数少。

    function selectOrder(arr) {
        var min = 0;
        var temp = 0;
        for (var i = 0; i < arr.length; i++) {
            // 假定当前最小值的下标为i
            min = i;
            for (var j = i + 1; j < arr.length; j++) {
                // 与假定的最小值比较,小的话则改变min的值
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // 如果min的值与当初假定值不等,则将最小值与当前值交换
            if (min != i) {
                temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
        return arr;
    }复制代码

4.直接插入排序

直接插入排序是将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录数加1的新的有序表。

直接插入排序与冒泡排序时间复杂度相同,但元素移动次数少。

   function insertOrder(arr) {
        // temp 用于存储当前值
        var temp = 0;
        for (var i = 1; i < arr.length; i++) {
            temp = arr[i];
            j = i - 1;
            // arr[j]相当于哨兵,表示已经排序过的序列的最大值
            while (temp < arr[j] && j >= 0) {
                // 哨兵位之后的所有已排序序列(j到i-1)向后移动一位,即arr[0]变为arr[1],arr[1]变为arr[2]
                arr[j + 1] = arr[j];
                j--;
            }
            //把j-1减掉的1加回来,(试想如果不满足while条件,即arr[i]>arr[i-1],则不需要移动,而上边j=i-1,需要再加回来)
            arr[j + 1] = temp;
        }
        return arr;
    }复制代码

5.快速排序

快速排序的思路是:通过一趟排序将待排记录分割成独立两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

选取一个值作为基准值,比基准值小的放左边,比基准值大的放右边,递归,直到左右两边都排好序,时间复杂度为O(nlogn).

   function quickOrder(arr) {
        if (arr.length > 1) {
            var mid = parseInt(arr.length / 2);
            //不可以直接让arr[i]与arr[mid]比较,当arr[mid]刚好为最小值时,无法划分为左右两部分,只有右边部分,会出现死循环
            var pivot = arr.splice(mid, 1);
            var left = [];
            var right = [];
            for (var i = 0; i < arr.length; i++) {
                if (arr[i] < pivot) {
                    left.push(arr[i]);
                } else {
                    right.push(arr[i]);
                }
            }
            return quickOrder(left).concat(pivot, quickOrder(right));
        } else {
            return arr;
        }
    }复制代码

6.希尔排序

希尔排序的原理与直接插入排序相同,步长从1变为increase。

希尔排序的时间复杂度不稳定,最差的情况是O(n²)。

    function shellOrder(arr) {
        var increase = arr.length;
        var temp;
        while (increase > 0) {
            increase = parseInt(increase / 2);
            for (var i = increase; i < arr.length; i++) {
                temp = arr[i];
                var j = i - increase;
                while (temp < arr[j] && j >= 0) {
                    arr[j + increase] = arr[j];
                    j = j - increase;
                }
                arr[j + increase] = temp;
            }
        }
        return arr;
    }复制代码

7.堆排序

堆排序利用的是二叉树中的大顶堆结构,即根节点大于左右子树 。

二叉树中存在 根节点i的两个子节点分别是2i和2i+1 ,利用数组表示二叉树时,二叉树从1开始,数组从0开始 ,故数组中存在根节点i的两个子节点分别是2i+1 和2i+1+1

    function heapOrder(arr) {
        var j = arr.length;
        var tempArr = [];
        while (j > 0) {
            // 返回arr的第一项为数组的最大值
            // 数组长度或者说二叉树长度为arr.length,则最大叶子节点为aarr.length-1项,则此叶子节点的根节点为(arr.length-1)/2
            // 故i从(arr.length-1)/2开始,一直向下遍历到0,即根节点结束
            for (var i = parseInt(arr.length / 2 - 1); i >= 0; i--) {
                maxNode(arr, i)
            }
            // 第一项为最大值,弹出后,将数组剩余项再排列为大顶堆
            tempArr.push(arr.shift());
            j--;
        }
        return tempArr;
        function maxNode(arr, i) {
            var temp = arr[i];
            for (var j = i * 2 + 1; j < arr.length; j = j * 2 + 1) {
                // 找到根的左右节点中较大的一个再与根节点比较
                if (j + 1 < arr.length && arr[j] < arr[j + 1]) {
                    // 如果右节点大,则j+1,此时arr[j]为右节点
                    j++;
                }
                // arr[j]为左右节点中较大的一个
                if (temp < arr[j]) {
                    // 如果根节点小于左右节点的较大值,则交换位置
                    arr[i] = arr[j];
                    arr[j] = temp;
                    i = j;
                } else {
                    break;
                }

            }
        }
    }复制代码

8.归并排序

归并排序是将数组先划分成2个2个一组的子数组,进行排序,再合并已经有序的子数组,平均时间复杂度为O(nlogn)

   function mergeSort(arr) {
        // 如果数组长度大于1,再进行分组,否则直接返回
        if (arr.length > 1) {
            //将数组从中间部分分为两部分
            var len = parseInt(arr.length / 2);
            // 数组的前半部分
            var arr1 = arr.slice(0, len);
            // 数组的后半部分
            var arr2 = arr.slice(len);
            // 最开始写的是:mergeSort(arr1) 没有前边的赋值操作,则虽然分组进行了排序,但并没有改变arr
            // 将arr1的子数组的排序结果赋值给arr1
            arr1 = mergeSort(arr1);
            arr2 = mergeSort(arr2);
            // 返回数组的两个子数组的排序结果
            return merge(arr1, arr2);
        } else {
            return arr;
        }
   // 对两个参数数组进行shift()操作,可使得代码更简洁
    function merge(arr1, arr2) {
        var temp = [];
        while (arr1.length && arr2.length) {
            if (arr1[0] < arr2[0]) {
                temp.push(arr1.shift());
            } else {
                temp.push(arr2.push());
            }
        }
        temp.concat(arr1, arr2);
    }
复制代码