排序算法

比较

对于评述算法优劣术语的说明

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;

内排序:所有排序操作都在内存中完成;
外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

时间复杂度: 一个算法执行所耗费的时间。
空间复杂度: 运行完一个程序所需内存的大小。

算法比较:

图片说明

二分查找

假设一个数组已经排好序了,现在要在数组里找一个数flag的位置。

首先先找到长度中间位置,通过与中间位置的数比较,比中间值大在右边找,比中间值小在左边找。然后再在两边各自寻找中间值,持续进行,直到找到全部位置。

//arr排好序
function binarySearch(arr,flag,Start,End){
    let end =End||arr.length-1;
    let start=Start||0;
    let m=Math.floor((start+end)/2);
    if(arr[m]==flag){
        return m;
    }
    if(flag<arr[m]){
        return binarySearch(arr,flag,0,m-1);
    }else{
        return binarySearch(arr,flag,m+1,end);
    }
    return false;
}

非递归的方法也写一个吧

function binarySearch(arr,flag){
    let r=arr.length-1,//数组下标长度减一
        l=0;
    while(l<=r){
        let m=Math.floor((h+1)/2);
        if(data[m]==flag){
            return m;
        }
        if(flag>data[m]){
            l=m+1;
        }else{
            r=m-1;
        }
    }
    return false;
}

冒泡排序

比较相邻两个元素的,如果前一个比后面的大,就交换位置,第一轮之后最后一个元素是最大的一个,按照这种方法依次比较。

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

快速排序

是利用二分查找对冒泡排序的改进,选一个元素作为基准,把数字分为两部分,一部分全部比它小,一部分全部比它大,然后递归调用,在两部分都进行快排。

function quickSort(arr){
    if(arr.length<=1){
        return arr;
    }
    //中间位置
    let middle=Math.floor(arr.length/2);
    let flag=arr.splice(middle,1)[0];//取出中间元素
    let left=[],right=[];
    for(let i=0;i<arr.length;i++){
        if(arr[i]<flag){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    return quickSort(left).cocat([flag],quickSort(right));
}

插入排序

从第一个元素开始,该元素认为已经被排序了,取出下一个元素。在已经排序的元素序列中从后向前扫描,如果大于新元素,那么就把这个元素移动到下一个位置。直到找到已排序的元素小于或者等于新元素的位置,将新元素插入下一个位置。依次进行。(其实就是最开头的元素当作是有序数列,后面的元素是无序的,然后从第一个开始往前面插入)

function insertSort(arr){
    //从第一个开始(遍历无序数列)
    for(let i=1;i<arr.length;i++){
        if(arr[i]<arr[i-1]){
            let guard=arr[i];//无序数列中的第i个元素
            let j=i-1;//有序数列的最后一个位置
            arr[i]=arr[j];
            while(j>=0&&guard<arr[j]){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=guard;
        }     
    }
}

选择排序

首先在未排序的队里找到最小的元素,存放到排序序列中的起始位置,然后从剩下没有排序的元素中找最小的元素,放到已排序的队尾

function selectionSort(arr){
    let len=arr.lengrh;
    let index,temp;
    for(let i=0;i<len-1;i++){
        index=i;
        for(let j=i+1;j<len;j++){
            if(arr[j]<arr[index]){
                index=j;//存最小索引
            }
        }
        tmp=arr[j];
        arr[i]=arr[index];
        arr[index]=temp;
    }
    return arr;
}

希尔排序

用于较大规模无序数据。

先将整个待排序的数据集分割为若干组,然后对每一个组分别进行直接插入排序。此时每个组内插入排序所作用的数据量小,效率比较高。

排序完后基本上数组,小元素大体在前,大元素大体在后,然后缩小增量,继续分组,此时虽然每个分组元素个数变多了,但是数组变有序了,效率也是比较高的。

用的比较少,篇幅稍微长一些。

这个算法的图解可以看这篇博客,用一问一答的方式把它描述得非常有趣了。专业一点的描述可以看这篇博客,动图把过程说的非常清楚。

也可以直接看下面的动图(摘自上面的博客)

shellSort

function shellSort(arr){
    var len=arr.length;
    var tmp,gap=1;

    while(gap<len/5){
        gap=gap*5+1;
    }
    for(gap;gap>0;gap=Math.floor(gap/5)){
        for(var i=gap;i<len;i++){
            tmp=arr[i];
            for(var j=i-gap;j>=0&&arr[j]>tmp;j-=gap){
                arr[j+gap]=arr[j];
            }
            arr[j+gap]=tmp;
        }
    }
    return arr;
}

归并排序

一种稳定排序方法,将已有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,再使序列段间有序。

其实也是二分的思想,只不过是在二分的基础上,先分段,段内再排,然后把每一段拼接起来。

这篇博客里有非常仔细的图片分析。这个需要新申请一个数组来做,所以自然是O(n)的空间复杂度啦!

从上面这篇博客偷了个动图帮助理解:

mergeSort

function mergeSort(arr){
    //自上而下递归
    var len =arr.length;
    if(len<2){return arr}
    var middle=Math.floor(len/2),
        left=arr.slice(0,middle),
        right=arr.slice(middle);
    return merge(mergeSort(left),mergeSort(right));
}

function merge(left,right){
    var result=[];
    while(left.length&&right.length){
        if(left[0]<=right[0]){
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    while(left.length){
        result.push(left.shift());
    }
    while(right.length){
        result.push(right.shift());
    }
    return result;
}

堆排序

堆排序利用堆的数据结果设计的排序算法。堆是一个近似完全二叉树的结构,同时满足:子节点的键值或索引总是小于/大于父节点。

heapSort

function heapSort(arr){
    if(Object.prototype.toString.call(arr).slice(8,-1)==='Array'){
        var heapSize=arr.length,temp;//建堆
        for(var i=Math.floor(heapSize/2)-1;i>=0;i--){
            heapify(arr,i,heapSize);
        }
        for(var j=heapSize-1;j>=1;j--){
            //堆排序
            temp=arr[0];
            arr[0]=arr[j];
            arr[j]=temp;
            heapify(arr,0,--heapSize);
        }
        return arr;
    }else{
        throw TypeError('Input not Array');
    }
}

function heapify(arr,x,len){
    if(Object.prototype.toString.call(arr).slice(8,-1)==='Array'&&typeof x==='number'){
        var l=x*2+1,
            r=x*2+2,
            largest=x,
            temp;
        if(l<len&&arr[l]>arr[largest]){
            largest=l;
        }
        if(r<len&&arr[r]>arr[largest]){
            largest=r;
        }
        if(largest!=x){
            temp=arr[x];
            arr[x]=arr[largest];
            arr[largest]=temp;
            heapify(arr,largest,len);
        }
    }else{
        throw TypeError('Input Illegal');
    }
}

计数排序

使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数,然后根据数组C来将A中的元素排到正确位置。(只能对整数排序)

function countingSort(arr){
    var len=arr.length,B=[],C=[],min=max=arr[0];
    for(var i=0;i<len;i++){
        min=min<arr[i]? min:arr[i];
        max=max>arr[i]? max:arr[i];
        C[arr[i]]=C[arr[i]]?C[arr[i]]+1:1;
    }
    for(var j=min;j<max;j++){
        C[j+1]=(C[j+1]||0)+(C[j]||0);
    }
    for(var k=len-1;k>=0;k--){
        B[C[arr[k]]-1]=arr[k];
        C[arr[k]]--;
    }
    return B;
}

桶排序

假设输入的数据服从均匀分布,将数据分到有限数量的桶里。每个桶再分别排序。(可以再使用别的排序算法,或者递归继续用桶排序)

function bucketSort(arr,num){
    if(arr.length<=1) return arr;
    let len=arr.length;
    let buckets=[],result=[],space,n=0;
    min=max=arr[0];
    let regex='/^[1-9]+[0-9]*$/';

    for(let i=1;i<len;i++){
        min=min<=arr[i]?min:arr[i];
        max=max>=arr[i]?max:arr[i];
    }
    space=(max-min+1)/num;//索引减法+1
    for(let j=0;j<len;j++){
        let index=Math.floor((arr[j]-min)/space);
        if(buckets[index]){
            //不是空桶的话,就插入排序
            var k=buckets[index].length-1;
            while(k>=0&&buckets[index][k]>arr[j]){
                buckets[index][k+1]=buckets[index][k];
                k--;
            }
            buckets[index][k+1]=arr[j];
        }else{
            //空桶,初始化
            buckets[index]=[]
            buckets[index].push(arr[j]);
        }
    }
    while(n<num){
        result=result.concat(buckets[n]);
        n++;
    }
    return result;
}

基数排序

基数排序是按照地位先排序,然后收集;再按照高位排序,然后收集;以此类推,直到最高位。有时候有些属性有优先级顺序,先按低优先级排序,在按高优先级排序。

最后次序就是高优先级在前,高优先级相同的低优先级高的在前。

大意就是说:比如[53 3 542 748 14]

先按个位排序就是[542 053 003 014 748]

然后按照十位排序,[003 014 542 748 053]

然后按照百位排序,[003 014 053 542 748]

因为它是分别排序分别收集的,所以是稳定的。

function radixSort(arr,maxDigit){
    let mod=10,dev=1,counter=[];
    for(let i=0;i<maxDigit;i++,dev*=10,mod *=10){
        for(let j=0;j<arr.length;j++){
            let bucket=parseInt((arr[j]%mod)/dev);
            if(counter[bucket]==null){
                counter[bucket]=[];
            }
            counter[bucket].push(arr[j]);
        }
        var pos=0;
        for(let j=0;j<counter.length;j++){
            let value=null;
            if(counter[j]!=null){
                while((value=counter[j].shift())!=null){
                    arr[pos++]=value;
                }
            }
        }
    }
    return arr;
}

注:这三种算法用到的比较少,但上面这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

  • 基数排序:根据键值的每位数字来分配桶
  • 计数排序:每个桶只存储单一键值
  • 桶排序:每个桶存储一定范围的数值