一、排序算法说明

• 排序的定义：对一序列对象根据某个关键字进行排序。
  输入：n个数：a1,a2,a3,...,an 输出：n个数的排列:a1',a2',a3',...,an'，使得a1'<=a2'<=a3'<=...<=an'
• 对于评述算法优劣术语的说明
• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
• 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
• 内排序：所有排序操作都在内存中完成；
• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
• 时间复杂度: 一个算法执行所耗费的时间。
• 空间复杂度: 运行完一个程序所需内存的大小。
• 总结

• 对比

  
  
  

  In-place: 占用常数内存，不占用额外内存 Out-place: 占用额外内存。

• 分类

  
  

二、详解

1.冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

• 算法描述
  <1>.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  <2>.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  <3>.针对所有的元素重复以上的步骤，除了最后一个；
  <4>.重复步骤1~3，直到排序完成。
• 算法实现

function bubbleSort(arr) {
    let length = arr.length;
    for(let i = 0;i < length-1;i++) {
        for(let j = 0;j < length-1-i;j++) {
            if(arr[j] > arr[j + 1]) { // 相邻元素对比
                let temp = arr[j + 1]; // 交换位置
                arr[j + 1] = arr[j]; 
                arr[j] =temp; 
            }
        }
    }
    return arr;
}
let arr = [2, 1, 19, 30, 27];
console.log(bubbleSort(arr))

• 算法分析
• 最佳情况
  T(n) = O(n)（数据正序）
• 最差情况
  T(n) = O(n2)（数据反序）
• 平均
  T(n) = O(n2)

2.选择排序（Selection Sort）
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 算法描述
• <1>.初始状态：无序区为R[1..n]，有序区为空；
• <2>.第i趟排序(i=1,2,3...n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。排序开始时从无序区的第一个开始，对比后面的，如果遇到比这个小的，就记录下位置。该趟排序从当前无序区中选出最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• <3>.n-1趟结束，数组有序化了。
• 算法实现

function selectionSort(arr) {
    let len = arr.length;
    let minIndex, temp;
    for(let i = 0;i < len;i++) {
        minIndex = i;
        for(let j = i + 1;j < len; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    console.timeEnd('选择排序耗时');
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));

• 算法分析
• 最佳情况：T(n) = O(n2)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)

3.插入排序（Insertion-Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 算法描述

• <1>.从第一个元素开始，该元素可以认为已经被排序；

• <2>.取出下一个元素，在已经排序的元素序列中从后向前扫描；

• <3>.如果该元素（已排序）大于新元素，将该元素移到下一位置；

• <4>.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

• <5>.将新元素插入到该位置后；

• <6>.重复步骤2~5。

• 算法实现

function insertionSort (array) {
    if(Object.prototype.toString.call(array).slice(8, -1) == 'Array') {
        console.time('插入排序耗时');
        for (let i = 1;i < array.length; i++) {
            let key = array[i];
            let j = i - 1;
            while(j >= 0 && array[j] > key) {
                array[j + 1] = array[j]; //与前面排好序的对比
                j--;
            }
            array[j + 1] = key; // 插入到最后对比的那个数后面
        }
        console.timeEnd('插入排序耗时：');
        return array;
    } else {
        return 'array is not an Array!';
    }
}

• 算法分析
• 最佳情况：输入数组按升序排列。T(n) = O(n)
• 最坏情况：输入数组按降序排列。T(n) = O(n2)
• 平均情况：T(n) = O(n2)

4.归并排序（Merge Sort）
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

• 算法描述
• <1>.把长度为n的输入序列分成两个长度为n/2的子序列；
• <2>.对这两个子序列分别采用归并排序；
• <3>.将两个排序好的子序列合并成一个最终的排序序列。
• 算法实现

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 = [];
    console.time('归并排序耗时');
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length)
        result.push(left.shift());
    while (right.length)
        result.push(right.shift());
    console.timeEnd('归并排序耗时');
    return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));

• 算法分析
• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(nlogn)
• 平均情况：T(n) = O(nlogn)

5.快速排序（Quick Sort）
快速排序快，而且效率高！它是处理大数据最快的排序算法之一。
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

• 算法描述
• <1>.从数列中挑出一个元素，称为 "基准"（pivot）；
• <2>.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• <3>.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
• 算法实现

let quickSort = function (arr) {
    console.time('快速排序耗时');
    if(arr.length <= 1) {return arr;}
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1) [0];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if(arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    console.timeEnd('快速排序耗时');
　　return quickSort(left).concat([pivot], quickSort(right));
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr));

• 算法分析
• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(nlogn)

6.计数排序
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

• 算法描述
• <1>. 找出待排序的数组中最大和最小的元素；
• <2>. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• <3>. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• <4>. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
• 算法实现

function countingSort(array) {
    var len = array.length,
        B = [],
        C = [],
        min = max = array[0];
    console.time('计数排序耗时');
    for (var i = 0; i < len; i++) {
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
        C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
    }
    for (var j = min; j < max; j++) {
        C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
    }
    for (var k = len - 1; k >= 0; k--) {
        B[C[array[k]] - 1] = array[k];
        C[array[k]]--;
    }
    console.timeEnd('计数排序耗时');
    return B;
}
var arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(countingSort(arr)); 

• 算法分析
• 最佳情况：T(n) = O(n+k)
• 最差情况：T(n) = O(n+k)
• 平均情况：T(n) = O(n+k)