比较排序算法一般有三个指标
- 时间复杂度， 算法执行完成所需要的时间
- 空间复杂度， 算法执行完成所需要的空间
- 稳定性，当二个元素的值相同的时候，排序之后二个元素的前后位置是否发生改变
以下的排序都为升序
冒泡排序
冒泡排序是面试官最喜欢问新手程序员的.冒泡排序就像名字一样，冒泡排序第一次冒出最大的，第二次冒出第二大的，第三次冒出第三大的.....直到冒出倒数第二大的.
const array = [12, 2, 3, 10, 8, 8, 9, 21]function BubbleSort(array){ let len = array.length; if (len == 0 || len == 1) { return array; } for (let i = 0; i < len-1; i++) { for (let j = 0; j < len-1-i; j++) { // 减i是因为第0到第i大已经冒出来了 不需要再比较了 if (array[j] > array[j+1]) { [array[j], array[j+1]] = [array[j+1], array[j]]; } } } return array}BubbleSort(array) //[2, 3, 8, 8, 9, 10, 12, 21]复制代码 时间复杂度为O(n^2)，空间复杂度为O(1)，稳定
仅仅面试考察，实际运用是不会用到的，因为冒泡排序是非常没效率的，因为不仅时间复杂度高而且有O(n^2)的交换，交换所耗的性能远大于比较
选择排序
选择排序是第一位找到最小的，第二位找到第二小的，第三位找到第三小的.....
const array = [12, 2, 3, 10, 8, 8, 9, 21]function SelectionSort(array){ let len = array.length; if (len == 0 || len == 1) { return array; } for (let i = 0; i < len-1; i++) { let min = i; for (let j = i+1; j < len-1-i; j++) { if (array[j] < array[min]) { min = j } } [array[i], array[min]] = [array[min], array[i]]; } return array }SelectionSort(array) //[2, 3, 8, 8, 9, 10, 12, 21]复制代码 时间复杂度为O(n^2)，空间复杂度为O(1)，稳定
仅仅面试考察，实际运用跟冒泡一样，也不会用到，因为效率也非常低. 但是比冒泡好点，因为元素如果再正确的位置上不会交换。
插入排序
就是，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
const array = [12, 2, 3, 10, 8, 8, 9, 21]function InsertionSort(array){ let len = array.length; if (len == 0 || len == 1) { return array; } for (let i = 1; i < len; i++) { for (let j = 0; j < i; j++) { // 查找的部分可以使用二分查找 if (array[j] > array[i]) { this.splice(j, 0, array[i]); // 插入进来 this.splice(i+1, 1); // 删除已插入的元素 break; } } } return array; }InsertionSort(array) //[2, 3, 8, 8, 9, 10, 12, 21]复制代码 时间复杂度为O(n^2)，空间复杂度为O(1)，不稳定
效率也不高，通常也不会使用，但是如果数据接近线性排列.那么使用二分查找插入排序是一个非常好的选择
快速排序
这个也是经常被问到，是递归算法的经典使用场景
const array = [12, 2, 3, 10, 8, 8, 9, 21]function quickSort(array){ let len = array.length; if (len == 0 || len == 1) { return array; } let mid = array[0], left =[], right = []; for (let i = 1; i < len; i++) { if (array[i] < mid) { left.push(array[i]) } else { right.push(array[i]) } } return quickSort(left).concat(mid, quickSort(right))}quickSort(array) //[2, 3, 8, 8, 9, 10, 12, 21]复制代码 时间复杂度为O(nlogn)，空间复杂度为O(n)，不稳定
平均时间复杂度低 ，占用空间小，快速排序是使用得最多得排序算法
归并排序
归并排序是分治算法得经典应用，归并算法得核心是将两个已经排序的序列合并成一个序列.
const array = [12, 2, 3, 10, 8, 8, 9, 21]function mergeSort(array){ let len = array.length; if (len == 0 || len == 1) { return array; } function merge(left, right) { let final = []; while (left.length && right.length) { final.push(left[0] <= right[0] ? left.shift() : right.shift()); } return final.concat(left.concat(right)); } let mid = Math.floor(len-1/2); let left = array.slice(0, mid) let right = array.slice(mid); return merge(mergeSort(left), mergeSort(right))}mergeSort(array) //[2, 3, 8, 8, 9, 10, 12, 21]复制代码 时间复杂度为O(nlogn)，空间复杂度为O(n)，不稳定
时间复杂度和空间复杂度与快速排序是一样的，其实二个性能是相当的,毕竟二种排序都出现在浏览器内核中。为什么要快速排序使用较大，可能快速排序在各种数据量下表现得更为稳定吧. 但是如果数据呈分段有序时，使用归并排序效率更高
堆排序
具体如何实现，在这一章已经讲过，我直接贴上代码了
// 最大堆调整 function maxHeapfiy(array, i, heapSize){ let left = 2*i+1, right = 2*i+2, mid = i; if (left < heapSize && array[left] > array[mid]) { mid = left; } if (right < heapSize && array[right] > array[mid]) { mid = right; } if (mid != i) { [array[i], array[mid]] = [array[mid], array[i]] maxHeapfiy(array, mid, heapSize) } } // 构建最大堆 const buildMaxHeapfiy = (array, heapSize) => { let parent = Math.floor(heapSize/2) for (parent; parent >= 0; parent--) { maxHeapfiy(array, parent, heapSize) } } // 堆排序 const array = [12, 2, 3, 10, 8, 8, 9, 21]; let heapSize = array.length; buildMaxHeapfiy(array, heapSize) for (let i = heapSize-1; i >=0; i--) { [array[0], array[i]] = [array[i], array[0]]; this.maxHeapfiy(array, 0, i); } // [2, 3, 8, 8, 9, 10, 12, 21]复制代码 时间复杂度为O(nlogn)，空间复杂度为O(n)，不稳定
堆排序虽然，时间复杂度和空间复杂度都较低，但是堆排序的有个缺点在于当堆中的一个数据发生改变，都需要进行堆调整来维护最大堆（最小堆），需要额外的维护开销，由于在实际运用中，数据变动是很频繁的，所以实际上堆排序不是很适合实际的运用。