几个概念
- 时间复杂度：执行算法所需要的计算工作量。
- 空间复杂度：算法在运行过程中临时占用存储空间大小的度量。
- 稳定性：如果存在多个具有相同的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定的。
in-place算法，指的是不需要额外空间的算法。
算法的时间复杂度和空间复杂度是可以相互转化的。比如谷歌浏览器相比于其他的浏览器，运行速度要快。是因为它占用了更多的内存空间，以空间换取了时间。
如何选择
- 若n较小(如 n≤ 50)，可采用 直接插入或直接选择排序。
- 若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、或归并排序。
- 快速排序是目前内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
- 若要求排序稳定，则可选用归并排序。先利用直接插入排序获的有序子序列，然后再两两归并。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。
Array.sort()使用的是直接插入排序和快速排序结合的排序算法。数组长度不超过10时，使用直接插入排序。长度超过10使用快速排序。
冒泡排序
- 思想：相邻两个数比较大小，较大的数下沉，较小的数冒起来。
- 时间复杂度
O(n2)，一般不推荐使用。
function BubbleSort(arr){
let temp; //临时变量
for(var i = 0; i < arr.length-1; i++){
let flag = false
for(var j = arr.length-1; j > i; j--){
if(arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = true
}
}
if(!flag) break; // 如果第N次遍历没有发生交换，说明已经排序完成，无需后续的遍历，提升了排序稳定性。
}
return arr
}直接选择排序
- 思想：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 时间复杂度
O(n2),数据量较小时推荐。 - 不稳定排序。比如序列：
{ 5, 8, 5, 2, 9 }，首次选择以后，最小元素2和第一个5进行交换，从而改变了两个元素5的相对次序。
function SelectionSort(arr)
{
for (let i = 0; i < arr.length - 1; i++){
let min = i, temp;
for (let j = i + 1; j < arr.length; j++){
if (arr[j] < arr[min])
{
min = j;
}
}
if (min != i)
{
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
return arr;
}
直接插入排序
- 思想：和抓扑克牌类似，首个元素为初始已排序队列，第二个元素从后往前扫描已排序队列，找到合适的位置插入，后面的元素依此类推。
- 特点：时间复杂度
O(n2), 通常在数据量级较小时使用。Array.sort()内部，在数组长度不超过10时，就使用插入排序。是稳定排序算法。
function insertSort(arr){
let temp, lenth = arr.length;
for(let i =0 ; i < lenth-1 ; i++){
for(let j = i + 1 ; j > 0 ; j--){
if(arr[j] < arr[j-1]){
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}else{ //不需要交换
break;
}
}
}
return arr;
}快速排序
- 思想：分而治之。先从数列中取出一个数作为基数（一般是第一个或者最后一个）；将比这个数小的全部放在它的左边，大于或等于它的全部放在它的右边；对左右两个小数列重复第二步，直至各区间只有1个数。
- 特点：平均时间复杂度：
O(N*logN)O(N*logN), 通常明显比其他O(nlogn)算法更快。快速排序是不稳定的排序算法。
function quickSort(arr) {
if (arr.length <= 1)
return arr;
// 首个元素作为基数
const pivot = arr[0];
//左右区间，用于存放排序后的数
let left = [], right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
//递归left/right; 使用concat操作符，将左区间，基准，右区间拼接为一个新数组
return quickSort(left).concat([pivot], quickSort(right));
}归并排序
- 思想：归并排序主要依赖归并(Merge)操作。指的是将两个已经排序的序列合并成一个序列的操作。
- 特点：平均时间复杂度 O(NlogN)。是稳定排序算法。
下面，我们应用归并排序思想，合并一个二维有序数组成一维有序数组：
/**
* 基本思路：双指针 从头到尾比较两个数组的第一个值，根据值的大小依次插入到新的数组中
* @param {Array} arr1
* @param {Array} arr2
*/
function merge(arr1, arr2){
let result=[];
while(arr1.length>0 && arr2.length>0){
if(arr1[0]<arr2[0]){
/*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/
result.push(arr1.shift());
}else{
result.push(arr2.shift());
}
}
return result.concat(arr1).concat(arr2);
}
function mergeSort(arr){
let lengthArr = arr.length;
if(lengthArr === 0){
return [];
}
while(arr.length > 1){
let arrayItem1 = arr.shift();
let arrayItem2 = arr.shift();
let mergeArr = merge(arrayItem1, arrayItem2);
arr.push(mergeArr);
}
return arr[0];
}
let arr = [[1,2,3],[4,5,6],[7,8,9],[1,2,3],[4,5,6]];
mergeSort(arr);