# 排序？
? 排序，即对一系列对象根据某个关键字进行排序
# 术语说明
- 稳固： 假如
a本来在b前面，且a==b，排序之后a依然在b前面 - 不稳固： 假如
a本来在b前面，且a==b，排序之后a不肯定出现在b前面 - 内排序： 所有的操作都在内存中完成
- 外排序： 因为数据太大，因而把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
- 时间复杂度： 一个算法执行所需要的时间
- 空间复杂度： 运行完一个程序所需内存的大小
?
# 排序算法总结
【说明】
- n: 数据的规模
- k: “桶”的个数
- in-place: 占用常数内存，不占用额外内存
- out-place: 占用额外内存
?
# 排序算法分类
?
# 测试用例
? 为了检验算法的正确性，算法的测试用例就显得非常重要，这里要求测试用例提供的测试数据范围必需要广，假如需要压力测试，数据量必需要大。因而，采用硬编码形式编写测试用例并不理想，最好能采用程序的方式实现数据的生成，同时也要考虑到边缘数据的测试用例。
?
# 选择排序
? 时间复杂度：O(n*n)
? 稳固性：不稳固
? 升序思路：在未排序序列中找到最小（大）元素，与未排序的第一个元素交换位置，而后，再从剩余未排序元素中继续寻觅最小（大）元素，再与未排序的第一个元素交换位置。以此类推，直到所有元素均排序完毕。
function selectionSort (arr, n) { for(var i = 0; i < n; i ++ ) { var minIndex = i for (var j = i + 1; j < n; j ++ ) { if ( arr[i] > arr[j] ) { // 查找最小数 minIndex = j //将最小数的索引保存 } } var tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; } return arr}测试用例 （此处为了方便，采用硬编码形式）
function main () { var a = ['a', 'b', 'd', 'c'] selectionSort (a, a.length); document.write(a) // 不稳固案例 var b = [6, 4, 6, 2, 8];}?
# 冒泡排序
? 时间复杂度： O(n*n)
? 稳固性：稳固
? 排序思路：从第一项开始比较相邻的两项，假如后者比前者小，则交换位置，否则不动，以此类推，此轮结束后最大的元素被交换到末尾，且将不需要再参加比较。继续下一轮比较。
function bubbleSort (arr) { var len = arr.length for (var i = 0; i < len; i++) { for (var j = 0; j < len - i; j++) { if (arr[j] < arr[j + 1]) { var tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } return arr;}?
# 插入排序
? 时间复杂度：O(n*n); 最有效的O(n*n)排序算法，在近有序的序列中，比O(nlogn)效率还要高
? 稳固性：稳固
? 排序思路： 通过从前往后构建有序序列，取后面未排序序列中的第一个，与前面已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只要用到O(1)的额外空间的排序），因此在从后向前扫描过程中，需要反复把已排序元素逐渐向后挪位，为最新元素提供插入空间。
function insertSort (arr) { var len = arr.length; for ( var i = 1; i < len; i++ ) { var curent = arr[i] for ( var j = i - 1; j == 0; j--) { if ( arr[j] > curent ) { // 循环元素比当前当前大，则当前元素往后挪 arr[j+1] = arr[j]; } else { //循环元素比当前待插小，则将tmp插入当前之后 arr[j+1] = current; } } } return arr}或者者如下写法
function insertSort2 (arr) { for ( var i = 1; i < len; i++ ) { for ( var j = i; j > 1 && arr[j] > arr[i]; j++ ) { swap(arr[j], arr[i]); } } return arr;}function swap(a, b) { var tmp = a; a = b; b = tmp;}?
# 希尔排序
? 希尔排序是插入排序的改进版，与其不同的是，优先比较的不是相邻的两个元素，而是相距较远的的元素。希尔排序又叫缩小增量排序，其核心在于如何设定间隔序列。
? 时间复杂度：平均O(nlogn)
? 稳固性： 不稳固
? 排序思路：将整个待排序序列分割成若干个序列分别进行直接插入排序
（1）选择一个增量序列，如t1,t2,…tk；其中，ti>tj; tk = 1;
（2）按增量序列个数k，对序进行k次排序，
（3）每次排序，更具对应的增量ti，将待排序列分割成若干个长度为m的子序列，分别对各子表进行插入排序，直到增量为1，排序结束。
【疑点】或者许你会疑惑，为什么希尔排序中需要经过好几轮的插入排序，并且最终在k=1情况下还要做一次完整的插入排序，也就是说做了屡次的插入排序，为什么还说是插入排序的改进版呢？
?答： 或者许你没有真正了解插入排序的强势之处。插入排序的时间复杂度在最好和最坏的情况下相差特别之大，一个是O(n); 另一个是O(n*n)；而插入排序在 （1）排序数据量小 （2）待排序列几乎有序 的时候最容易达到O(n)的时间复杂度。希尔排序正是利用了插入排序的这两个特点，在最开始的时候将长序列分割成短序列，慢慢合并起来的序列的有序化程度也会越来越高，因而尽管最后做了一个全序列排序，但其实已经是非常接近有序序列的顺序了，所以排序的速度会很快。
?
# 归并排序
? 时间复杂度： O(nlogn)
? 稳固性：稳固
? 排序思路： 分两步：分和治。分即将整个待排队列不断的分成两部分，直至每部分只剩单一元素。治的思想需要借助一个辅助队列，其长度为两个子队列长度的和。前提有两个子队列已完成排序（单个元素自身已排好序）。在其合并时，比照两个子队列第一个元素，取小的值放入辅助队列，并将该子队列下标加一继续与另一个子队列比照，仍旧取小的放入辅助队列，依次类推结束，辅助数组就是已排好序的下次递归的一个子序列。
image.png
function __merge( arr, l, mid, r ) { var aux = new Array(r - l +1); for ( var i = l; i <= r; i ++ ) { aux[i-l] = arr[i] } var i = l, j = mid + 1; for ( var k = 0; k <= r; k ++ ) { if ( i > mid ) { arr[k] = aux[j-l]; j ++; } else if ( j > r ) { arr[k] = aux[i-l]; j ++; } else if ( aux[i-l] > aux[j-l]) { arr[k] = aux[j-l]; j++; } else { arr[k] = aux[i-l] i++; } } }function __mergeSort(arr, l, r) { if ( l >= r ) { return; } var mid = parseInt((l + r)/2); __mergeSort(arr, l, mid); __mergeSort(arr, mid + 1, r); __merge(arr, l, mid, r);}function mergeSort( arr ) { var len = arr.length - 1; __mergeSort( arr, 0, len )}?
# 快速排序
? 快速排序是几种排序算法中最为重要的一种。他有几个关键元素：
（1）基准数，
（2）左哨兵，
（3）右哨兵
? 时间复杂度：O(nlogn)
? 稳固性：不稳固
? 排序思路：利用两个哨兵不断的检查队列中数据与基准数的大小关系，将其放置在队列的”前半部分“和“后半部分“。升序中，右哨兵负责检查比基准数小的元素，该元素会被丢至前半部分，左哨兵负责检查比基准数大的元素，该元素会被交换至后半部分。
（1）将数组的第一个元素当做基准数
（2）设置i和j两个哨兵，分别从排序数组的左边界和右边界开始检查数据
（3）必需右哨兵先出发检查，找到第一个比基准数小的数字，暂停检查并记录位置，左哨兵开始检查，找到第一个比基准数大的数字。而后左右哨兵的值交换位置。以此类推，直到左右哨兵相遇，此次检查结束。一次排序检查之后，就形成了大致升序的趋势。
（4）此时数组的状态是以左右哨兵相遇位置，前半部分包括哨兵位置都是比基准数小的，后半部分都是比基准数大的。此时交换哨兵与基准数，基准数便落入了最终排序应该出现的位置。
（5）以基准书将数组分成两部分去递归以上步骤，就可。
?实现代码如下
/** * @func 快速排序算法 * @param arr-待排序队列，left-排序左边界，right-排序右边界 * @method i-左哨兵，j-右哨兵, base-基准数，temp-交换变量 * @tips: * 右哨兵任务即找到比基准数小的丢到左边，左哨兵找大的丢到右边。 * 哨兵查找顺序很重要，必需右哨兵先找，这样能先定位到一个比 * 基准数小的值，便于最后与基准数交换保证逻辑正确 **/var arr = [5, 1, 7, 8, 3, 2, 9, 4, 6];quickSort(0, arr.length - 1);console.log(arr);function quickSort(left, right) { var i, j, base, temp; // 递归只剩一个元素，或者参数问题，结束排序 if (left >= right) return i = left; // 左哨兵站位左边界 j = right; // 左哨兵站位右边界 base = arr[left]; // 基准数规则取左边界值 while (i != j) { // 哨兵未碰面，本轮检查继续。 // 必需右哨兵优先开始检查，比基准数大，继续往左检查。比基准数小，暂停。 // 等号是为了让队列只有一个值的时候正常运行 while (arr[j] >= base && i < j) { j -- } // 左哨兵开始检查，比基准数小，继续往右检查 while (arr[i] <= base && i < j) { i ++ } // 左哨兵检找到比基准数大，右哨兵找到比基准数小，交换数据 if (i < j) { // i==j，不需要交换 temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } /** * while循环结束，左右哨兵碰面，本次检查结束 * 此时队列状态是哨兵及哨兵左边均比基准数小，哨兵右边均比基准数大 * 接下来，将交换基准数与哨兵位置，基准数便归位最终正确位置 **/ arr[left] = arr[i]; // 左哨兵(与右哨兵重合)， arr[i] = base; // 基准数归位 // 以基准数为分隔位置切分队列，递归调用执行子序列 quickSort(left, i-1); quickSort(i+1, right);}
