排序算法是数据结构和算法之中的基本功，无论是在笔试还是面试，还是实际运用中都有着很基础的地位。这不正直七月，每年校招的备战期，所以想把常见的排序算法记录下来。在本篇文章中的排序算法使用 JavaScript 实现。
一、 冒泡排序冒泡排序是排序算法中最简单的一个算法，其优点是易理解，易实现。在一些对性能要求不高且数据量不大的需求中，冒泡排序是一个很好的选择。
原理：假设排序顺序为增序，数组长度为 N。数组每相邻两个元素进行比较，大数后移，小数前移，第一轮排序下来就能找到最大的数。也就是比较 A[i] 和 A[i+1] ，将大数后移，随后增加 i 的值，再进行比较。第二轮再对剩余的 N-1 个数进行排序，找出第二大的数，以此类推。同时也可以记录交换次数来进行优化，如果在一层循环之中交换次数为 0，则排序结束。
下面这张图展示了冒泡排序的全过程：
下面这张图展示冒泡排序在宏观层面的全过程：
O(n^2) O(n) O(n^2) O(1)
1 function bubbleSort (arr) { 2 var swapTime = 0; 3 for(var i = 0, length1 = arr.length; i < length1; i ++){ 4 for(var j = 0, length2 = length1 - i; j < length2 - 1; j ++){ 5 if(arr[j] > arr[j+1]){ 6 swapTime++; 7 var temp = arr[j]; 8 arr[j] = arr[j+1]; 9 arr[j+1] = temp; 10 } 11 } 12 //检查交换次数，如果为0，则当前数组为有序数组；如不为0，则重置 13 if(swapTime === 0){ 14 break; 15 }else { 16 swapTime = 0; 17 } 18 } 19 } 二、选择排序
选择排序算法与冒泡排序算法类似，即每一轮找出一个最大值。但和冒泡排序不同的一点是，冒泡排序是采用不停的交换将最大值（最小值）筛选出来，而选择排序是记录下最大值（最小值）的索引。
原理：假设排序方式为增序，数组长度为 N。设置最大值索引初始值 index = 0，然后遍历数组，记录下最大值的索引，即比较 A[i] 与 A[index] 的值，若 A[i] > A[index] 则更新 index = i。在每一轮遍历结束后，交换 index 位置和末尾位置的值，即交换 A[index] 和 A[i]，这样便保证了末尾值是最大值。随后对剩余的 N-1 个数进行同样的方式排序，以此类推。
下面这张图展示了选择排序的全过程：
下面这张图展示了在宏观层面上选择排序的全过程：
O(n^2) O(n^2) O(n^2) O(1)
1 function selectSort (arr) { 2 for(var i = 0, length1 = arr.length; i < length1; i ++){ 3 var index = 0 4 for(var j = 0, length2 = length1 - i; j < length2; j ++){ 5 if(arr[j] > arr[index]){ 6 index = j; 7 } 8 } 9 var temp = arr[index]; 10 arr[index] = arr[length1 - i - 1]; 11 arr[length1 - i - 1] = temp; 12 } 13 } 三、插入排序