排序算法稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
Array.prototype.sort
js标准库中的排序方法，可传入一个函数自定义比较规则。流行的浏览器实现都是稳定的排序算法。（例如chrome之前使用的是快排，在7.0版本之后换成了Timsort
）
关于Array.prototype.sort()详细介绍见 MDN。
冒泡排序
最蠢的排序。遍历数组，依次对比相邻的两个数，如果两个数的顺序错误则交换位置。平均时间复杂度为 O（n²），稳定排序。
function Bubble (arr){
if (!arr || !arr.length ) return arr;
for (let i = arr.length; i > 0; i--) {
for (let j = 1; j < i; j++) {
if (arr[j] < arr[j - 1]) {
const tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}
}
}
return arr;
}
鸡尾酒排序
冒泡排序改良版，又称双向冒泡排序。在每一轮遍历中，进行两次冒泡。一次将最大值置于一端，一次将最小值置于另一端。性能略为优化，平均时间复杂度仍然是 O（n²）。稳定排序。
function Cocktail(arr) {
if (!arr || !arr.length ) return arr;
for (let i = arr.length; i > 0; i--) {
for (let j = i - 1; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
const tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}
}
for (let j = arr.length - i + 1; j < i; j++) {
if (arr[j] < arr[j - 1]) {
const tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}
}
}
return arr;
}
插入排序
类似打扑克将牌排序的手法，外层循环从第一个元素开始遍历，内层循环将下一个元素与左侧元素依次比较，插入到应处的位置。因为进行内层循环时，元素位置对的情况下无需继续进行遍历，所以效率比冒泡高很多。特别是在数组大部分元素有序情况下效率很高。但在极端情况下依然需要进行完全遍历，所以平均时间复杂度也还是O（n²）。稳定排序。
function Insertion (arr){
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
const tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}else{
break;
}
}
}
return arr;
}
选择排序
外层循环依次遍历数组，内层循环遍历未排序部分找出最小/大的元素与前面的元素交换。与插入排序比较，选择排序无需进行频繁的元素交换动作，内层循环只是标记最小元素，遍历完成后进行一次交换。减少了交换的开销。但选择排序无论如何都需要完全遍历数组，在大部分有序情况下效率低于插入排序。平均时间复杂度也还是O（n²）。不稳定排序。
class Selection(arr){
for (let i = 0; i < arr.length; i++) {
let min = arr[i];
let minIndex = i;
for (let j = i; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
}
if (minIndex != i) {
let tem = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tem;
}
}
return arr;
}
希尔排序
to be continued
归并排序
归并排序一种基于分治法思路的排序。通过将数组两两划分，排序后再合并。平均时间复杂度为O(nlogn)，需要申请空间进行合并操作，空间复杂度为T(n)。是一种稳定的排序算法。稳定排序。
function Merge(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return sort(Merge(left), Merge(right));
}
function sort(arrA, arrB) {
let i = 0;
let j = 0;
const arr = [];
while (arrA.length > 0 && arrB.length > 0) {
if (arrA[0] < arrB[0]) {
arr.push(arrA.shift());
} else {
arr.push(arrB.shift());
}
if (arrA.length == 0) {
arr = arr.concat(arrB);
} else if (arrB.length == 0) {
arr = arr.concat(arrA);
}
}
return arr;
}
快速排序
最快的排序算法。思路是先取一个基准值，然后双指针遍历数组。右指针负责找到比基准值小的值，左指针负责找到比基准值大的值，两值交换。使得数组一边是比基准值小的，一边是比基准值大的。然后再分别对这两边进行排序。平均时间复杂度为O(nlogn)，不稳定排序。快的原理是通过双指针，使得每一轮循环可以使多个元素大致归位。
快排递归版本
function QuickSortRecursion(arr) {
partition(arr, 0, arr.length - 1);
return arr;
}
function partition(arr, start, end) {
if (arr.length <= 1 || start === end) {
return;
}
let left = start, right = end;
let key = arr[start];
while(left < right){
while(left < right && key <= arr[right]){//右指针往左走，寻找比基准值小的值
right--;
}
while(left < right && key >= arr[left]){//左指针向右走，寻找比基准值大的值
left++;
}
//交换元素
const tem = arr[right];
arr[right] = arr[left];
arr[left] = tem;
}
if(left == right && key > arr[right]){//如果指针所指比基准值小
arr[start] = arr[right];
arr[right] = key;
}
if(left - 1 > start){
partition(arr, start, left - 1);
}
if(right + 1 < end){
partition(arr, right + 1, end);
}
}
非递归版本
似乎递归的算法变不递归都是利用栈来解决的。其实递归也就是函数调用栈，原理是完全一样的。但函数调用栈里保存了每一个函数的执行上下文，占用内存会比循环+栈的方式大得多，当多重嵌套时会导致爆栈。改为循环+栈的形式可以处理更大的数组。
function QuickSort(arr){
const stack = [];
let start = 0, end = arr.length - 1;
do {
let indexData = null;
if (stack.length != 0) {
let data = stack.pop();
start = data.start;
end = data.end;
}
indexData = this.partition(arr, start, end);
if (indexData != null) {
if (indexData - 1 > start) {
stack.push({ start: start, end: indexData - 1 });
}
if (indexData + 1 < end) {
stack.push({ start: indexData + 1, end: end });
}
}
} while (stack.length != 0);
return arr;
}
function partition(arr, start, end) {
if (arr.length <= 1 || start === end) {
return null;
}
let left = start, right = end;
let key = arr[start];
while(left < right){
while(left < right && key <= arr[right]){//右指针往左走，寻找比基准值小的值
right--;
}
while(left < right && key >= arr[left]){//左指针向右走，寻找比基准值大的值
left++;
}
const tem = arr[right];
arr[right] = arr[left];
arr[left] = tem;//交换元素
}
if(left == right && key > arr[right]){//如果指针所指比基准值小
arr[start] = arr[right];
arr[right] = key;
}
return left;
}
