排序 | idkhts's blog

理解排序的稳定性：
- 定义：序列[1,4\,3,6,5,4,2]排序后为[1,2,3,4,4\,5,6]则为不稳定，因为*4***与 4 的相对位置变了，*4*…4 变成了，4…***4*
- 判断要点：主要看算法是否有“间隔置换”，比如选择排序，4第一次与 2 置换后来到了 4 的后面（如果是相邻的交换就不会），最终也没能换回到 4 的前面，所以选择排序是不稳定的；希尔排序/快排也是，某一次增量/基准是可能有“间隔置换”，把原来的相对位置打乱了，所以是不稳定的；如冒泡没有间隔置换，相邻的操作可以保持相对位置不变，所以是稳定的（唯一例外，插入排序，虽然也是间隔交换，但是它保持了相对位置）

冒泡算法

两两比较，相邻两个元素比较，n 个元素需要 n 轮（每轮有 n 次）；数据都像泡泡流（冒……）向合适的地方
时间复杂度 O(n^2)，空间复杂度 O(1)，稳定

let arr = [1,5,9,7,5,6,7,4,6,57,65,48,4,65,4,987,999];
for(let i=0;i<arr.length;i++){
	for(let j=0;j<arr.length-1;j++){
    	if(arr[j]>arr[j+1]){
            arr[j] = arr[j] + arr[j+1];
            arr[j+1] = arr[j]-arr[j+1];
            arr[j] = arr[j]-arr[j+1];
        }
	}
}
console.log(arr);
//[1, 4, 4, 4, 5, 5, 6, 6, 7, 7, 9, 48, 57, 65, 65, 987, 999]

选择排序

从数组第一个位置开始，遍历剩余（未排序的，应该都在这个位置后）数组元素选择一个最合适的数放在这个位置。
时间复杂度 O(n^2)，空间复杂度 O(1)，不稳定（因为会置换）

let arr = [1,5,9,7,5,6,7,4,6,57,65,48,4,65,4,987,999];
for(let i=0;i<arr.length-1;i++){
	for(let j=i+1;j<arr.length;j++){
        if(arr[i] > arr[j]){
            arr[i] = arr[i] + arr[j];
            arr[j] = arr[i]-arr[j];
            arr[i] = arr[i]-arr[j];
        }
    }
}
console.log(arr);
//[1, 4, 4, 4, 5, 5, 6, 6, 7, 7, 9, 48, 57, 65, 65, 987, 999]

插入排序

（排升序，以下算法是）从第二个开始，认为前面的已经是有序的了，当前位置的在排好序的前面的元素比较，小于的就插入，不然继续往前；不断插入到前面，插入——代表相对位置已经确定。这里的和选择排序的区别是，插入排序排的每次排是相对位置，选择排序是每次都是排最终位置。
时间复杂度是 O(n^2)，空间复杂度为 O(1)，稳定

let arr = [1,5,9,7,5,6,7,4,6,57,65,48,4,65,4,987,999];
for(let i=1;i<arr.length;i++){
	for(let j=i;j>=0;j--){//向前寻找，找到当前元素小的，说明需要插入到这个元素后
        if(arr[i] > arr[j]){
           	let tmp = arr.splice(i,1);//从数组取出（数组长度减一）
           	arr.splice(j+1,0,tmp[0]);//插入
        }
    }
}
console.log(arr);

希尔排序

其实是升级版的插入排序，对插入排序做了优化，插入排序对有序度高的数组排序快，那么优化点就可以是序列的有序程度。希尔排序从“数组个数”和“数组有序度”去优化了插入排序。
整个数组的个数除于 2 得到一个分组数（增量一），然后在每个分组里面进行插入排序，排序后，这样一轮即完成了；然后第二轮，用第一轮（上一轮）的增量（增量一）除于 2，然后每个分组里面在进行插入排序，排序后结束本轮；重复步骤，知道增量变成<1，排序完成；
比如数组 1-8，一共 8 个元素，8/2=4，记增量为 4，所以分成四组，也即每组只有两个元素；同组元素时要分（因为分开才会整个数组都……怎么描述），所以这样分【1，5】、【2，6】、【3，7】、【4，8】，所以第i个元素的同组元素是i+增量；

编程时考虑不拆分原数组，所以为了“每个分组里排序”，那么需要利用i+增量是同组这个属性
时间复杂度是 O(n^1.3)，空间复杂度为 O(1)，不稳定（因为会置换）

let testArr = [1, 5, 9, 7, 5, 6, 7, 4, 6, 57, 65, 48, 4, 65, 4, 987, 999];
//首先划分增量
for (let n = Math.floor(testArr.length / 2); n >= 1; n = Math.floor(n / 2)) {
    //然后按增量间隔对这些元素进行插入排序
    for (let i = n; i < testArr.length; i++) {
        //“j-=n”注意是跳增量n个，而不是1个，为1就是直接插入排序了；
        for (let j = i; j >= 0; j-=n) {
            if (testArr[i] > testArr[j]) {
                let tmp = testArr.splice(i, 1);
                testArr.splice(j + n, 0, tmp[0]);//前一位也是跳增量的
                break;
            }
        }
    }

}
console.log(testArr);

归并排序

分而治之思想，大序列划分为小序列，小序列再划分为更小的序列，直到最后只有一个的时候就很简单两个比较；这样的比较对排序
时间复杂度 O(n ㏒2 n),空间复杂度为 O(n)，稳定

let testArr = [1, 5, 9, 7, 5, 6, 7, 4, 6, 57, 65, 48, 4, 65, 4, 987, 999];
//归并排序
function MergeSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
    let mid = Math.floor(arr.length / 2);
    return merge(MergeSort(arr.slice(0, mid)), MergeSort(arr.slice(mid)))
}
function merge(arr1, arr2) {
    let result = [];
    //比较两个数组，小的先进结果集，大的和小的所在数组后一个元素进行再一轮比较，直到某个数组为空
    while (arr1.length > 0 && arr2.length > 0) {
        if (arr1[0] > arr2[0]) {
            result.push(arr2.shift());
        } else {
            result.push(arr1.shift());
        }
    }

    //可能某个数组为空了，则另一个数组可以直接加到结果集后
    if (arr2.length != 0) {
        result = result.concat(arr2)
    }
    if (arr1.length != 0) {
        result = result.concat(arr1)
    }
    return result;
}
testArr = MergeSort(testArr)
console.log(testArr);

快速排序

也是分而治之思想，与归并排序的区别是，划分问题的方法：归并排序的划分子问题一般方法是从数组中间划分两端，然后递归划分直到一个；快速排序的划分是以一个元素作为一个基准，大于它和小于它分两半，然后递归划分直到一个。同时快排的主要操作是交换数组元素，使用的空间相对归并排序更少
实现：选择第一个元素作为基准，先从数组尾往回遍历，找到比基准小的与基准互换，互换后再数组头+1开始(第一个已经确定比基准小了，应该放基准左变)，找到比基准大的与基准互换，互换后又从右边刚刚基准所在-1找小于的，互换位置，从左边找大于再刚刚基准所在+1`。。。不断重复左右跳，直到没有元素可找，一轮结束；然后分别在基准两侧再进行刚刚的操作（更小粒度）。【比较乱，直接看代码吧】
平均时间复杂为 O(nlog₂n)，最差可以达到 O(n^2)，n 表示元素个数；空间复杂度为 O(1)，一个空间记录基准+双指针用了 2 个空间 = 3 =》O(1)；若用了递归可能性能还差点；不稳定（因为会置换）

//测试数组
let testArr = [1, 55, 68, 21, 598, 66, 221, 1554, 3879, 5216, 100, 8, 9, 5, 7, 6, 22, 21]
  function quickSort(arr) {
        if (arr.length <= 1) return arr;
        let low = 0;
        let hight = arr.length - 1;
        let pivot = arr[0]; //基准
        let isRight = true;

        //按基准划分
        while (low < hight) {
            if (isRight) {//先寻找比基准小的
                if (arr[hight] > pivot) {
                    hight--;
                } else {
                    arr[low] = arr[hight];
                    low++;
                    isRight = !isRight;
                }
            } else {//再寻比基准大的
                if (arr[low] > pivot) {
                    arr[hight] = arr[low];
                    hight--;
                    isRight = !isRight;
                } else {
                    low++;
                }
            }
        }
        arr[low] = pivot;
        let arr1 = quickSort(arr.slice(0, low)); //再在分块里面排序
        let arr2 = quickSort(arr.slice(low + 1)); //再在分块里面排序
        return arr1.concat([arr[low]], arr2) //返回连接起来的数组
    }
    console.log('原数组', testArr)
    console.log('排后数组', quickSort(testArr))

堆排序

前置知识：
- 完全二叉树：所有节点都先有左子树再有右子树的二叉树
- 堆，用数组来存储一颗有序的完全二叉树，分大根堆和小根堆
  - 大根堆：根比左右子节点都大，但左右节点谁大没有规定
  - 小根堆：根比左右子节点都小，但左右节点谁小没有规定
  - 怎么用数组存储一个完全二叉树？
    
    完全二叉树有个性质，如果按先序遍历给每个节点一个从 0 开始的序号，那么第 i 号节点的左右子节点分别是 2i+1、2i+2；所以数组构造堆，就是遍历数组，让当前元素 i 和 2i+1、2i+2 比较大小，最大的/最小的换到当前位即可
思想大概是利用堆这种结构排序，以大根堆为例，把数组构造成一个大根堆，取根节点，也即最大值，剩下的 n-1 个再构造一个大根堆，再取根节点，不断循环这样的操作就可以得到一个大到小的排序/小到大的排序
构造大根堆：
- 找 arr.length/2-1 的节点，即非叶子节点的从左到右的第一个节点，构造左右子节点都小于当前的节点，若是由子节点大于当前节点则交换，若交换后破坏了子节点的大根堆构造那么也要进行替换，直到最后
- 然后找第二个非叶子节点 arr.length/2-2，重复上面操作，直到多有非叶子节点都完成
堆排序是一种选择排序，堆其实就是帮助选择的数据结构而已
时间复杂度：O(nlog₂n)
空间复杂度：O(1)

是否稳定：不稳定

//测试数组
let testArr = [1, 55, 68, 21, 598, 66, 221, 1554, 3879, 5216, 100, 8, 9, 5, 7, 6, 22, 21]

function heapSort(arr){
    // 数组arr交换i,j的值
    const swap = (arr,i,j)=> {
        // if(i === j) return
        arr[i] = arr[i] + arr[j]
        arr[j] = arr[i] - arr[j]
        arr[i] = arr[i] - arr[j]
    }

    // 堆调整
    const heapify = (arr,i,len) => {
        let left = i*2+1 //左节点
        let right = i*2+2 //右节点
        let largest = i //最大值序号

        if(left < len && arr[left] > arr[largest]){
            largest = left
        }
        if(right < len && arr[right] > arr[largest]){
            largest = right
        }
        if(largest !== i){
            swap(arr,i,largest)
            heapify(arr,largest,len)
        }
    }

    // 构造大根堆
    for(let i = Math.floor(arr.length/2);i>=0;i--){
        heapify(arr,i,arr.length)
    }

    // 取最大值
    for(let i = arr.length-1;i>0;i--){
        swap(arr,i,0)
        heapify(arr,0,i)
    }

    return arr
}

console.log(heapSort(testArr))

桶排序

主要就是利用数组下标排序，把原数组放到另一个按下对应值的下标的数组（称桶数组）中，在按序取得这个桶数组的非空元素即可。为了节约空间，原数组的值可以经过一个“提炼”（一定的换算）得到一个下标，压缩桶数组的长度，这样有可能多个元素命中一个桶，那么在放进桶里排下序即可；思想有点类似 hash 表
时间复杂度 O(n),空间 O(n)，稳定，是线性排序，没有 O（nlogn)限制，大数据很快，但是空间消耗也大
实现：
- 计划桶数组长度和原数组一样，可以取出原数组最大值和最小值（O(n))，求出它们的间隔，再除于原数组长度求每个桶的值间隔
- 遍历原数组，按照换算取得下标：下标 = 取整[ (元素 - 最小值) / 桶间隔 ] ；看这个下标的桶是否有元素，有元素插入时稍微做个排序即可 O(m)，没有的直接作为第一个元素
- 遍历桶数组，从下标小到大获取，桶内元素也同样获取即可

//测试数组
let testArr = [1, 55, 68, 21, 598, 66, 221, 1554, 3879, 5216, 100, 8, 9, 5, 7, 6, 22, 21]

function BucketSort(arr) {
    const buckets = Array(arr.length)
    const max = Math.max(...arr) //最大值
    const min = Math.min(...arr) //最小值
    const BkLength = Math.floor((max + min) / arr.length) + 1 //桶间隔

    //构造桶数组
    for (let i = 0; i < arr.length; i++) {
        const index = Math.floor((arr[i] - min) / BkLength) //数组从0开始，这里可以不用+1

        // 桶为空，可以直接作为第一个
        if (!buckets[index]) {
            buckets[index] = [arr[i]]
            continue
        }

        // 桶不为空，插入到桶里面对应的位置
        let isInsert = false
        for (let j = 0; j < buckets[index].length; j++) {
            if (buckets[index][j] > arr[i]) {
                buckets[index].splice(j, 0, arr[i])
                isInsert = true
                break
            }
        }
        !isInsert && (buckets[index].push(arr[i]))

    }

    //取出元素
    arr = []
    for (let i = 0; i < buckets.length; i++) {
        if (!buckets[i]) {
            continue
        }
        arr.push(...buckets[i])
    }
  return arr
}
console.log(BucketSort(testArr))