经典算法(归并排序丶快速排序)

249 阅读5分钟

相对于上一节介绍的三种排序算法,本节的排序算法在实际中应用更加广泛,赶快学习起来吧。

归并排序

分治是归并排序算法的主要思想。在算法中的直接体现就是先将数组通过多次切割划分成极短的数据,当数据长度被划分成一时,不用排序对于一个数据本身来说就是有序的,这个划分的过程被称为归。 当数据长度被划分成一时,我们就要通过并操作来一边将之前划分的数据合并到一起一边排序。因为之前划分的每一个数组片段都是有序的,因此归操作逻辑就很简单了。

function seprate(array,start,end){
    let l = end-start + 1
    let mid
    if(l>1){
        if(l%2===0){//偶数个
            mid = (start+end-1)/2
        } else {//奇数个
            mid = (start+end)/2
        }
        seprate(array, start,mid)
        seprate(array, mid+1,end)
    }
}

这是归操作的代码,当seprate调用栈到底的时候,start,end就会指向同一个元素,并且mid是undefined,最后再递归调用并函数。

function seprate(array,start,end){
    let l = end-start + 1
    let mid
    if(l>1){
        if(l%2===0){//偶数个
            mid = (start+end-1)/2
        } else {//奇数个
            mid = (start+end)/2
        }
        seprate(array, start,mid)
        seprate(array, mid+1,end)
    }
    mix(array, start, end, mid)
}
function mix (array, start, end, mid){
    let length = end - start +1
    if(mid){
        let arrayA = []
        let arrayB = []
        //将左右两边的内容分别复制到两个数组里
        for(let i = 0,l = mid-start+1;i<l;i++){
            arrayA[i] = array[start+i]
        }
        for(let i = 0,l = end-mid;i<l;i++){
            arrayB[i] = array[mid+i+1]
        }
        let arrayAindex = 0
        let arrayBindex = 0
        let arrayindex = start
        //对比两个数组开头的内容,因为两个数组本身是有序的,去替换原数组的内容,
        //直到两个数组的内容都被遍历完毕
        while(arrayAindex + arrayBindex <length){
            let arrayAItem = arrayA[arrayAindex]
            let arrayBItem = arrayB[arrayBindex]
            if(arrayAItem && arrayBItem){
                if(arrayAItem<=arrayBItem){
                    array[arrayindex] = arrayAItem
                    arrayindex ++
                    arrayAindex++
                }else {
                    array[arrayindex] = arrayBItem
                    arrayindex ++
                    arrayBindex++
                }
            } else if(arrayAItem) {
                array[arrayindex] = arrayAItem
                arrayindex ++
                arrayAindex++
            } else if(arrayBItem){
                array[arrayindex] = arrayBItem
                arrayindex ++
                arrayBindex++
            }
        }
    } else {
        return          //没有mid说明只剩下了一个元素
    }
}

并操作每次是将两个有序的数组片段合并成一个有序的数组,因为两个数组片段本身就有序了。因此我们可以将两个数组片段复制下来,然后每次取两个数组中最小的,放到元素组的开头,以此类推,直到两个数组片段的数据被遍历完毕

算法分析

1.空间复杂度分析

在归的过程中,我们并没有使用线性的内存空间,而在并的过程中,我们每次都要复制一次原数组,因此空间复杂度为O(n)

2.时间复杂度分析

归并排序的时间复杂度分析很复杂,就不证明了,直接说出答案吧O(nlogn),可以看出来这个时间复杂度还是很优秀的,关键是归并排序的时间复杂度极其稳定,跟要排列的数据的有序度没有关系。

3.是否是稳定排序算法

当在并的过程中,如果两个数组的开头相同了,我们可以把位于前侧的数组内的数据优先放入目标数组中,这样就不会破坏原有数据的顺序了,因此是稳定排序算法。

快速排序

快速排序跟归并排序有相似之处,也是依靠分治的思想,但是在对数组片段的排序方式上又跟归并排序不太相同。如果说归并是从下往上排序的话,那么快排就是从上往下排序。归并排序在对数组片段进行排序时,会先从数组片段中随机找出一个元素,这个元素暂且称之为基数,然后再在数组片段的两头各布置一个哨兵,如果左侧的哨兵发现有大于基数的元素,那么把左侧的元素移到右侧,右边的哨兵也是一样。最后两个哨兵相遇,将基数的位置与哨兵相遇的位置互换,数组片段排序完成,再将数组片段分成两段,分别再操作左右两边两个数组片段,直到数组片段是1,结束递归。

function quicksort(array, left, right){
    let i,j,target
    if(left > right){       //说明已经没有数据可以再分了
        return ;
    }
    //将左右两侧哨兵记录
    i = left;
    j = right;
    //记录基数
    target = array[right]
    //左右哨兵相遇为终止条件
    while(i!=j){
        //左侧找到比基数大的节点停下
        while(array[i]<=target && i<j){
            i++
        }
        //右侧找到比基数小的节点停下
        while(array[j]>=target && i<j){
            j--
        }
        //哨兵没有相遇说明左侧找到了比基数大的,右侧找到了比基数小的,交换
        if(i<j){
            let item = array[i]
            array[i] = array[j]
            array[j] = item
        }
    }
    //哨兵相遇,相遇的点就是基数应该位于的中间,与基数交换
    array[right] = array[i]
    array[i] = target 
    //继续排序左右两侧
    quicksort(array, left, i-1)
    quicksort(array, i+1, right)
}

注释已经把思路写的很清楚了,就不赘述了,直接算法分析

算法分析

1.空间复杂度分析

我们在算法过程中只使用了常数级的额外内存空间,因此空间复杂度是O(1),是一个原地排序算法。

2.时间复杂度分析

绝大多数情况下的时间复杂度为O(nlogn),在极端情况下会退化为O(n²)

3.是否是原地排序算法

由于我们在最后将基数和哨兵所指向的位置交换时,可能会破坏数组原有数据的顺序,因此不是一个原地排序算法