个人总结----排序算法

排序算法

时间复杂度

讨论算法时需先了解时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。
可以参考其对时间复杂度的解释简书
简单来说，就是如果将程序中程序段的运行时间用数学表达式T(n)表示时，当其中循环次数n越来越大，趋近于无穷时，则可忽略部分函数元素，比如只保留最高次项、忽略最高次项的系数，当T(n) 不等于一个常数项时，可直接将常数项省略。此时得到的函数为f(n),因此可得算法的时间复杂度为O(f(n))。
关于大O符号，可以查看百度百科：大O符号。
值得注意的是：函数运行中，各个循环之间如果是嵌套关系，则O(a x b x c x...),当顺序执行时，虽是相加，但保留最高次项。时间复杂度函数是不固定，通常取当n数值越大时，影响函数最大的因素。

空间复杂度

空间复杂度是定义了该算法在运算过程中临时占用存储空间大小的量度。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。(来自：百度百科)
一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，节省存储；而有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。(以上来自：百度百科)

具体排序算法

排序算法	时间复杂度（平均）	稳定性
冒泡排序	O(n²)	稳定
插入排序	O(n²)	稳定
选择排序	O(n²)	不稳定
快速排序	O(nlog₂n)	不稳定
归并排序	O(nlog₂n)	稳定
堆排序	O(nlog₂n)	不稳定
基数排序	O(n)	稳定
希尔排序	O(n^1.3)	不稳定

稳定性是指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
【注意】：排序算法的稳定性是由具体的算法决定，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种情况下也可以变为不稳定的算法。（来自：百度百科）

冒泡排序

冒泡排序思想：从第0个元素到第n-1个元素遍历，若前面一个元素大于后面一个元素，则交换两个元素，这样可将整个序列中最大的元素冒泡到最后，然后再从第0个到第n-2遍历，如此往复，直到只剩一个元素。

    function bubbleSort() {
    for (var i = 0; i < arr.length - 1; i++) {
        for (var j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {  //比较相邻数值大小，若前面的大于后面的，则互相替换
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}
var arr = [1, 2, 5, 2, 5, 1, 7, 4, 1, 19, 33, 2];
console.log(bubbleSort(arr)); //[1, 1, 1, 2, 2, 2, 4, 5, 5, 7, 19, 33]

冒泡循环是稳定的，但如果将arr[j] > arr[j + 1]改为arr[j] >= arr[j + 1],则相同的两个元素也会发生交换，相同元素相对位置发生变化，因此变成了不稳定算法。

插入排序

插入排序思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

function insertionSort(arr) {
    for (var i = 1; i < arr.length; i++) {
        var temp = arr[i]; //存储用于比较的初值
        for (var j = i - 1; j >= 0; j--) {
            if (arr[j] > temp) {
                arr[j + 1] = arr[j]; //插入，替换
            } else {
                break;
            }
        }
        arr[j + 1] = temp; //若arr[j + 1]已被替换，则arr[(j - 1) + 1]此时为空，此时赋值
    }
    return arr;
}
var arr = [1, 2, 5, 2, 5, 1, 7, 4, 1, 19, 33, 2];
console.log(insertionSort(arr)); //[1, 1, 1, 2, 2, 2, 4, 5, 5, 7, 19, 33]

选择排序

选择排序思想：从原始数据中找到最小元素，并放在数组的最前面。然后再从下面的元素中找到最小元素，放在之前最小元素的后面，直到排序完成。

function selectionSort() {
    for (var i = 0; i < arr.length - 1; i++) {
        var min = arr[i];
        var minIndex = i; //变量初始化
        for (var j = i + 1; j < arr.length; j++) { //将i与i之后的数进行比较
            if (min > arr[j]) {
                min = arr[j];
                minIndex = j; //找到此次循环最小的数值，及其下标
            }
        }
        arr[minIndex] = arr[i];
        arr[i] = min; //将此时的最小值与比较值替换
    }
    return arr;
}
var arr = [5, 99, 2, 9, 1, 5, 67, 7, 10, 23];
console.log(selectionSort(arr)); //[1, 2, 5, 5, 7, 9, 10, 23, 67, 99]

快速排序

快速排序思想：选取第一个数为基准，通过一次遍历将小于它的元素放到它的左侧，将大于它的元素放到它的右侧，然后对它的左右两个子序列分别再执行同样的操作。

function quickSort(arr) { //利用递归实现
    if (arr.length <= 1) {
        return arr;
    } //用于递归使用，也是判断当数组中元素唯一时的判断条件。
    var pivotIndex = Math.floor(arr.length / 2);
    // console.log(pivotIndex);
    var pivot = arr.splice(pivotIndex, 1)[0]; //从原数组中取其中间值，成为一个只含有一个数的数组，取出这个数，并以此为基准 
    // console.log(pivot);
    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 quickSort(left).concat([pivot], quickSort(right)); //这里使用concat操作符，将左区间，基准，右区间拼接为一个新数组
}
    var arr = [5, 99, 2, 9, 1, 5, 67, 7, 10, 23];
    console.log(quickSort(arr)); //[1, 2, 5, 5, 7, 9, 10, 23, 67, 99]

递归有一定的局限性，因此还有以下方式实现快速排序。↓↓↓↓↓

 function quickSort(arr, i, j) { //常规 
            if (i < j) {
                let left = i; //left当前区间内左极限
                let right = j; //right为当前区间内右极限
                let pivot = arr[left]; //令当前区间左极限为基数 
                while (i < j) {
                    while (arr[j] >= pivot && i < j) { // 从后往前找比基准小的数
                        j--;
                    }
                    arr[i] = arr[j]; //找到后，赋值
                    while (arr[i] <= pivot && i < j) { // 从前往后找比基准大的数
                        i++;
                    }
                    arr[j] = arr[i]; //找到后，赋值
                }
                arr[i] = pivot; //此时 i=j将基数放置中间位置
                quickSort(arr, left, i - 1); //左边重复上述操作
                quickSort(arr, i + 1, right); //右边重复上述操作
                return arr;
            }
        }
        let arr = [5, 99, 2, 9, 1, 5, 67, 7, 10, 23];
        console.log(quickSort(arr, 0, arr.length - 1)); //[1, 2, 5, 5, 7, 9, 10, 23, 67, 99]

归并排序

归并排序思想：利用二分的特性，将序列分成两个子序列进行排序，将排序后的两个子序列归并（合并），当序列的长度为2时，它的两个子序列长度为1，即视为有序，可直接合并，即达到归并排序的最小子状态。

function　 merge(left, right) { //此函数递归方法
    var　 result = []; //建立一个新数组
    while (left.length > 0 && right.length > 0) { //循环，用于保证当数组中存在可比较的值
        if (left[0] < right[0]) { //两组数组第一个元素相互比较，小的排在前面。(left数组与right数组本身已经完成从小到大的排序，所以其本身的第一个元素一定是当前数组中的最小值)
            /*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    return　 result.concat(left).concat(right); //合并数组为一个数组
}
function　 mergeSort(items) {
    if (items.length == 1) { //判断原数组长度，为1时，直接输出结果。
        return　 items;
    }
    var　 middle = Math.floor(items.length / 2), //将原数组分为左右两段，(递归思想，无限分两段，直到每段只有一个数，然后反推比较大小排序)
        left = items.slice(0, middle),
        right = items.slice(middle);
    return　 merge(mergeSort(left), mergeSort(right)); //输出最终结果
}
var arr = [1, 3, 5, 2, 7, 32, 8, 4, 6, 33];
console.log(mergeSort(arr)); //[1, 2, 3, 4, 5, 6, 7, 8, 32, 33]

堆排序

归并排序思想：利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
大堆顶：每个结点的值都大于或等于其左右孩子结点的值。
小堆顶：每个结点的值都小于或等于其左右孩子结点的值。
这里需要知道二叉树基本的性质：
·若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个结点(i>=0)。
·高度为k的二叉树最多有2^(k) - 1个结点(k>=1)。 (设空树的高度为0)
·对任何一棵二叉树，如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。
完美二叉树：一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
完全二叉树：完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
完满二叉树：所有非叶子结点的度都是2。（只要你有孩子，你就必然是有两个孩子。）

由完全二叉树性质可知：左边子节点位置 = 当前父节点的两倍==>left = 2 * i +1；右边子节点位置 = 当前父节点的两倍 + 2 ==> right = 2 * ( i + 1 )
注意：i = 0 时是根节点
所以：Floor( (子– 1 ) /2)= 父节点的下标

var len;      // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
    function buildMaxHeap(arr) {     // 建立大顶堆
        len = arr.length;   //取数组长度
        for (var i = Math.floor(len/2-1); i >= 0; i--) {    //此时的 i 是当前最大子节点的父节点的下标，必须自底向上，不能自顶向下
            heapify(arr, i);
        }
    }
    function heapify(arr, i) {     // 堆调整
        var left = 2 * i + 1,     
            right = 2 * (i + 1),    //取当前最大子节点，左右兄弟节点
            largest = i;    //此时的最大子节点的父节点下标
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < len && arr[right] > arr[largest]) {  //若子节点超过范围 ，则为false
            largest = right;
        }                                 //保证右边大于左边
        if (largest != i) {             
            swap(arr, i, largest);    //两个数互换
            heapify(arr, largest);    //直到最大值为父节点
        }
    }
    function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    function heapSort(arr) {
        buildMaxHeap(arr);
        for (var i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);                          //此时 根节点为最大值，将最大值放在最后一个子节点
            len--;                                    //数组长度减一，成为新数组，再进行堆调整
            heapify(arr, 0);    //再进行堆调整
        }
        return arr;
    }
    var arr = [100, 99, 2, 9, 1, 6, 67, 7, 10, 23,3];
    console.log(heapSort(arr));//[1, 2, 3, 6, 7, 9, 10, 23, 67, 99, 100]

未完待续。。。

水平有限，若有错误，烦请指出

参考地址：
1.https://www.cnblogs.com/angelye/p/7508292.html
2.https://www.jianshu.com/p/916b15eae350
3.各个排序算法的百度百科
4.https://www.jianshu.com/p/33cffa1ce613
5.https://segmentfault.com/a/1190000015488549?utm_source=tag-newest