详解JavaScript如何实现四种常用排序

目录

一、插入排序直接插入排序二、交换排序（1）冒泡排序（2）快速排序三、选择排序（1）简单选择排序（2）堆排序四、归并排序

一、插入排序

插入排序有直接插入排序，折半插入排序，希尔排序，这里只实现常用的直接插入排序

直接插入排序

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。

插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

function insertSort(array) {//第一个默认已经排好      for (let i = 1; i < array.length; i++) {        let target = i;        for (let j = i - 1; j >= 0; j--) {          if (array[target] < array[j]) {            [array[target], array[j]] = [array[j], array[target]]            target = j;          } else {            break;          }        }      }      return array;    }

(front.length) { temp.push(front.shift()); } while (end.length) { temp.push(end.shift()); } return temp; }

做题时，上面多了删除过程，特别大的例子，时间也可能会超，用下面的方法

function merge(left, right){    let leftLen = left.length, rightLen = right.length;    let i = 0, j = 0;    let temp = new Array(leftLen + rightLen);    for(let cur = 0; cur < leftLen + rightLen; cur++){        // 检查i, j有没有超界        if(i >= leftLen) temp[cur]= right[j++];        else if(j >= rightLen) temp[cur] = left[i++];        else if(left[i] <= right[j]){            temp[cur] = left[i++];        }else{            temp[cur] = right[j++];        }    }    return temp;}

复杂度

时间复杂度：O(nlogn)

空间复杂度:O(n)

稳定性

稳定