limanting 的个人博客

排序一共分为 冒泡、插入、快排、希尔、堆排、基数、归并排序。

javaScript 里面数组的sort是归并排序加插入排序的改进版，叫TIM Sort。

冒泡

将相邻两个数比较，如果不符合意思，就交换位置。复杂度n^2。

var bubbleSort=function(arr){
    for(var i=0;i<arr.length;i++){
        for(var j=0;j<arr.length-i-1;j++){
            if(arr[j]>arr[j+1]){
                const temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
             }
         }  
    }   
    return arr;
}

优化：如果有一趟中发现没有交换，就可以直接退出。

var bubbleSort=function(arr){
    for(var i=0;i<arr.length;i++){
	bool swaped = false;
        for(var j=0;j<arr.length-i-1;j++){
            if(arr[j]>arr[j+1]){
		swaped = true;
                const temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
             }
         }
	if (!swaped) {
	   break;
	}
    }   
    return arr;
}

插入

插入的基本思想是从左到右遍历，一直保持左边的是有序的，直到最后。

var insertSort=function(arr){
    for(var i = 1; i < arr.length; i++){
        if(arr[i-1]<=arr[i]){
            continue;
        }
        let compareNum=arr[i];
        for(var j=i-1;j>=0;j--){
            if(arr[j]>compareNum){
                arr[j+1]=arr[j]
            }else{
                arr[j+1]=compareNum;
                break;
            }
        }
    }
    return arr;
}

对基本有序是友好的，虽然复杂度还是n^2，但是在大多数情况下比冒泡好很多。

快排

var quickSort = function (arr, left, right) {
    if (!left) {
        left = 0;
    }
    if (right === undefined) {
        right.arr.length - 1;
    }
    if (left >= right) {
        return;
    }
    var i = left - 1;
    var j = right + 1;
    var compareNum = arr[parseInt((i + j) / 2)];
    while (i < j) {
        while (arr[++i] < compareNum);
        while (arr[--j] > compareNum);
        if (i < j) {
            const temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    quickSort(arr, left, j);
    quickSort(arr, j + 1, right);
    return;
}

快速排序的思想是将小于基准的某个数放在左边，大于的放在右边，然后对左边和右边再继续排序。快速排序的复杂度是O（NlogN），已经是排序算法中很小的了。将数组拆分的过程当成一棵树，每一层遍历的次数都是n，但是最好的情况下，只用遍历logN次。

归并排序

归并排序的思想就是，将数组分为两半，左边和右边都是有序数组，然后将有序数组合并起来成为一个有序数组。复杂度同样是O(NlogN)。

var mergeSortB = function (arr, left, right) {
    if (left === undefined) {
        left = 0;
    }
    if (right === undefined) {
        right = arr.length - 1;
    }
    if (left === right) {
        return arr;
    }
    const mid = parseInt((left + right) / 2);
    const sortedArr = [];
    let i = left;
    let j = mid + 1;
    mergeSortB(arr, left, mid);
    mergeSortB(arr, mid + 1, right);
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            sortedArr.push(arr[i]);
            i++;
        } else {
            sortedArr.push(arr[j]);
            j++;
        }
    }
    if (i > mid && j <= right) {
        sortedArr.push.apply(sortedArr, arr.slice(j, right + 1));
    }
    if (i <= mid && j > right) {
        sortedArr.push.apply(sortedArr, arr.slice(i, mid + 1));
    }
    arr.splice(left, right - left + 1, ...sortedArr);
    return arr;
}

基数排序

仅表明原理。基数就是分桶的概念，比如一串数字，从最高位开始分类，这样很快就能定位到需要排序的。

从高位开始分桶（MSD），复杂度能到O（log（10）N），复杂度低很多，但是为什么不常用呢？因为其他的排序算法，比较大小都是一个判断，返回false或true，抽象性强，可以用函数去替代。但是基数排序是在数的大小比较上的一个精细的分类，分类是很难去列举扩展的。

从低位开始分桶（LSD） 实现简单。从低位开始分桶，再合并成一个数组，然后再逐步向高位进行上述的分桶和合并。

希尔排序

是插入排序的优化，分组的插入排序。分组的概念是距离。

s堆排序

javascript没有优先队列，所以要写优先队列的实现。

什么是优先队列？队列，先进先出，优先队列的意思是，出来的数是优先级最高的。优先队列的实现是堆（完全二叉树）。堆的根节点最大就是最大堆或大根堆，反过来就是小根堆或最小堆

堆排序就是将所有数据放大堆中，然后逐个拿出。复杂度O（NlgN）