排序

选择排序

思路： 找到数组内最小的值 与当前 已经有序的下一位做替换

时间复杂度：

// 选择排序
const arr = ['S','H','E','L','L','S','O','R','T','E','X','A','M','P','L','E'];
const selectSort = (arr) => {
    const length = arr.length;
    for(let i = 0; i < length; i++ ) {
        let minIndex = i;
        for(let j = i + 1; j < length; j++) {
            minIndex = arr[j] >  arr[minIndex] ? minIndex : j;
        }
        const temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
console.log(selectSort(arr))

冒泡方法

思路：循环数组，将前一个比后一个大的数组位置互换（这样保证第一次循环之后最后一个值都是最大的，以后再次循环数组就可以不用循环最后一个）

时间复杂度：

/**
 * @param {number[]} nums
 * @return {number[]}
 * 冒泡排序写法
 */
var sortArray = function(nums) {
    let len = nums.length;
    for(let j = len-1;j>-1;j--){  
        for(let i = 0;i<j;i++){
            if(nums[i]>nums[i+1]){
                let tempNum = nums[i];
                nums[i]= nums[i+1];
                nums[i+1] = tempNum;
            }
        }
    }
    return nums;
};

插入排序

思路： 类似摸牌一样，会一个个来，把新增的数 插入已有的有序的牌的适当位置

时间复杂度：

与选择排序的区别：在对原先有序多的情况下，插入排序会快很多， 选择排序的速度则是和处理 随机的数组一样 （下图 左边插入排序，右边选择排序）

// 选择排序
const arr = ['S','H','E','L','L','S','O','R','T','E','X','A','M','P','L','E'];
const insertSort = (arr) => {
    const length = arr.length;
    for(let i = 1; i < length; i++ ) {
        const temp = arr[i];
        for (var j = i;j >= 0 ;j--){
            // 遍历到第一位 或者中间有某个值小于arr[i] 将其插入
            if(j === 0 || temp >= arr[j-1]) {
                arr[j] = temp;
                break;
            }
            // 当前值和之前的每个值进行比较，发现有比当前值小的值就进行重新赋值
            arr[j] = arr[j-1];
        }
    }
    return arr;
}
console.log(insertSort(arr))

希尔排序

思路： 插入排序的优化效率的方法，插入排序拿到新的值 需要和相邻的数一个个交换直到插入到正确的位置， 希尔排序就是把 一个乱序拆分成 一个个独立的子序列， 使其可以跨多个位子进行交换，利用插入排序 对有序的序列 速度较快的特点 最后将多个有序的子序列进行插入排序

时间复杂度：

function shellSort(arr) {
    const len = arr.length;
    let n = 1;
    while(n < len) {
        n = 3 * n + 1
    }
    while(n >= 1) {
        for(let i = n; i < len; i++) {
            for(let j = i - n; j >= 0; j-=n) {
                if(arr[j+n] < arr[j]) {
                    let temp = arr[j];
                    arr[j] = arr[j+n];
                    arr[j+n] = temp;
                }else {
                    break;
                }
            }
        }
        console.log(arr,n)
        n = (n-1)/3;
    }
    return arr;
}
var arr = ['S','H','E','L','L','S','O','R','T','E','X','A','M','P','L','E'];
console.log(shellSort(arr))

归并排序

思路： 利用巧妙的递归 先将数组拆成 单个 并且 分leftArr 和 rightArr, 然后 通过mergeSortArr 一层层合并 ，mergeSortArr方法相当于合并两个有序的数组

时间复杂度：

function mergeSort(arr) {
    if(arr.length <= 1) {
        return arr
    }
    const length = arr.length;
    const middleIndex = Math.floor(length/2);
    const leftArr = mergeSort(arr.slice(0, middleIndex));
    const rightArr = mergeSort(arr.slice(middleIndex, length));

    return mergeSortArr(leftArr,rightArr);
}

function mergeSortArr(leftArr,rightArr) {
    console.log(JSON.stringify(leftArr), JSON.stringify(rightArr))
    let sortArr = [];
    while(leftArr.length && rightArr.length) {
        if(leftArr[0] < rightArr[0]) {
            sortArr.push(leftArr.shift())
        }else {
            sortArr.push(rightArr.shift())
        }
    }
    //排序完 可能leftArr 或者rightArr  上还有数组没有shift出去
    sortArr = [...sortArr, ...leftArr, ...rightArr]
    return sortArr
}

console.log(mergeSort(['S','H','E','L','L','S','O','R','T','E','X','A','M','P','L','E']));

二分法排序(快速排序)

思路： 定一个基准值,每次都从原有数组删掉这个基准值,将大于的值放在left数组 小于的值放在right数组,通过递归的方法把左边和右边的连在一起 如果最后这个数组length=1停止递归放回数组

时间复杂度：

/**
 * 二分法排序写法
 */
var sortArray = function(nums) {
    let len = nums.length;
    if(len<=1){
        return nums
    }
    let middleNum = ~~(len/2);
    let leftArr = [];
    let rightArr = [];
    for(let i=0;i<len;i++){
        if(i!==middleNum){
            nums[i]<nums[middleNum]?leftArr.push(nums[i]):rightArr.push(nums[i])
        }
    }
    return [...sortArray(leftArr),nums[middleNum],...sortArray(rightArr)]
}

堆排序

思路：详情看算法207

时间复杂度：

与其它排序的区别： 堆排序用于优先队列让出队和入队复杂度都降低，面对数量量大的情况无法排序，有了优先队列就可以从优先队列中取出并处理一部分 再根据结果决定是否先优先队列添加更多的数据

// 交换两个节点
function swap(A, i, j) {
  let temp = A[i];
  A[i] = A[j];
  A[j] = temp; 
}

// 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
// 假设 结点 i 以下的子堆已经是一个大顶堆，shiftDown函数实现的
// 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。后面
// 将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
// 都执行 shiftDown操作，所以就满足了结点 i 以下的子堆已经是一大
//顶堆
function shiftDown(A, i, length) {
  let temp = A[i]; // 当前父节点
// j<length 的目的是对结点 i 以下的结点全部做顺序调整
  for(let j = 2*i+1; j<length; j = 2*j+1) {
    temp = A[i];  // 将 A[i] 取出，整个过程相当于找到 A[i] 应处于的位置
    if(j+1 < length && A[j] < A[j+1]) { 
      j++;   // 找到两个孩子中较大的一个，再与父节点比较
    }
    if(temp < A[j]) {
      swap(A, i, j) // 如果父节点小于子节点:交换；否则跳出
      i = j;  // 交换后，temp 的下标变为 j
    } else {
      break;
    }
  }
}

// 堆排序
function heapSort(A) {
  // 初始化大顶堆，从第一个非叶子结点开始
  for(let i = Math.floor(A.length/2-1); i>=0; i--) {
    shiftDown(A, i, A.length);
  }
  // 排序，每一次for循环找出一个当前最大值，数组长度减一
  for(let i = Math.floor(A.length-1); i>0; i--) {
    swap(A, 0, i); // 根节点与最后一个节点交换
    shiftDown(A, 0, i); // 从根节点开始调整，并且最后一个结点已经为当
                         // 前最大值，不需要再参与比较，所以第三个参数
                         // 为 i，即比较到最后一个结点前一个即可
  }
}

let Arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
heapSort(Arr);
alert(Arr);

时间复杂度：

通俗来说可以理解成循环了几次

稳定性：

一般来说判断元素时候长距离 交换（希尔，快速排序）
元素相对位置改变， 例如给一群女生本来是安漂亮程度排序，漂漂的在前面，丑的在后面，现在按年龄再排序，排序之后如果丑的跑到漂亮的前面去了，就不稳定了。