你以为只是简单的排序?(二)

上一篇文章中分享了冒泡排序、插入排序、选择排序这三种排序算法,它们的时间复杂度都是O(n^2),比较高,适合小规模数据的排序。这篇文章,分享两种时间复杂度为O(nlogn)的排序算法,归并排序快速排序。这两种排序算法适合大规模的数据排序,更加的常用一些

归并排序

归并排序思想

归并排序核心思想:将待排序的数据分成前后两个部分,然后对前后两个部分的数据分别进行排序,再将前后两部分合并,得到的结果就是排好序的数据了

语言很抽象,看图
你以为只是简单的排序?(二)_第1张图片

归并排序使用的就是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了

分治思想跟之前的一篇文章中的递归很像,但是,分治是一种解决问题的处理思想,递归是一种编程技巧。归并排序用的是分治思想,可以用递归来实现

归并排序实现

如果你看过上一篇递归的文章,上边有介绍到,解递归问题,要分析出递归公式,然后找到递归终止条件,有了这两个,基本上递归代码就出来了。有了上边的那个图,基本上可以得到下边的递推公式

递归公式
MergeSort(start, end) = merge(MergeSort(start,(start+end)/2), MergeSort((start+end)/2 + 1, end))

递归终止条件
start >= end

MergeSort(start, end)表示的是给下标start到end之间的数组中的数据进行排序,将这个这个排序分成了两个子问题,一个是MergeSort(start,(start+end)/2),另一个是MergeSort((start+end)/2 + 1), end),当把这两个子问题排好序之后,再将它们合并,就把下标start到end之间的数据排好序了

最外层的那个merge就是对两个已经有序的数组进行合并,具体过程如下:
用两个游标i和j,分别指向两个待merge数组(arr)的第一个元素(这两个数组各自是有序的),比较游标对应位置元素的大小。如果arr[i]你以为只是简单的排序?(二)_第2张图片

代码实现

func MergeSort(arr []int) []int {
    if len(arr) <= 0 {
        fmt.Println("参数不合法")
        return nil
    }

    //递归终止条件,当拆分后的数组长度少于两个元素的时候
    if len(arr) < 2 {
        return arr
    }

    midIndex := len(arr) / 2
    leftArr := MergeSort(arr[0:midIndex])
    rightArr := MergeSort(arr[midIndex:])
    result := merge(leftArr, rightArr)

    return result
}

func merge(leftArr, rightArr []int) []int {
    var mergeRes []int
    leftIndex, rightIndex := 0, 0
    leftLength, rightLength := len(leftArr), len(rightArr)

    for leftIndex < leftLength && rightIndex < rightLength {
        if leftArr[leftIndex] > rightArr[rightIndex] {
            mergeRes = append(mergeRes, rightArr[rightIndex])
            rightIndex++
        } else {
            mergeRes = append(mergeRes, leftArr[leftIndex])
            leftIndex++
        }
    }

    if leftIndex == leftLength{
        for rightIndex < rightLength {
            mergeRes = append(mergeRes, rightArr[rightIndex])
            rightIndex++
        }
    }
    if rightIndex == rightLength {
        for leftIndex < leftLength {
            mergeRes = append(mergeRes, leftArr[leftIndex])
            leftIndex++
        }
    }

    return mergeRes
}

归并排序性能分析

首先归并排序是稳定排序算法,这个主要取决于merge操作,也就是将两个有序数组合并成一个有序数组。在合并的过程中,当两个数组中有相同的元素时,先把前边那部分数组中元素放入到tmp中,这样就可以保证相同的元素,在合并前后顺序不变

归并排序的时间复杂度是O(nlogn)。假设对n个元素进行归并排序需要的时间是T(n),那分解成两个子数组排序的时间都是 T(n/2)。merge函数合并两个有序子数组的时间复杂度是O(n)。所以,套用前面的公式,归并排序的时间复杂度的计算公式就是

T(1) = C;   n=1 时,只需要常量级的执行时间,所以表示为 C。
T(n) = 2*T(n/2) + n; n>1

根据上边的公式,经过一定的数学推导可以得到T(n)=Cn+nlog2n(log以2为底的n)。所以得到归并排序的时间复杂度就是O(nlogn)

从归并排序的原理图中可以看出来,归并排序的执行效率与要排序的原始数组的有序程度无关,所以其时间复杂度是非常稳定的,不管是最好情况、最坏情况,还是平均情况,时间复杂度都是O(nlogn)

归并排序和下边的快速排序相比,虽然时间复杂度都是O(nlogn),归并排序应用却不是那么广泛,因为它不是原地排序。归并排序中合并过程需要借助额外的存储空间

递归代码的空间复杂度并不能像时间复杂度那样累加,尽管每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU 只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过n个数据的大小,所以空间复杂度是 O(n)

快速排序

快速排序思想

快速排序的实现也是分治的思想,有点像归并排序,但是他们的实现思路还是完全不一样的

快速排序核心思想:如果要排序数组中下标从start到end之间的一组数据,选择start到end之间的任意一个数据作为分区点(pivot)

然后遍历start到end之间的数据,将小于分区点(pivot)的数据放左边,大于分区点的数据放右边,将分区点位置的数据放中间。经过上边的操作之后,分区点之前的数据都小于分区点这个位置的数据,分区点右边的数据都大于分区点这个位置的数据
你以为只是简单的排序?(二)_第3张图片
可以先不用纠结为什么经过一次分区之后变成这个样子了。往下看

根据递归的思想,如果我们用递归排序下标从start到pivot-1之间的数据和下标从pivot+1到end之间的数据,直到区间缩小为 1,就说明所有的数据都有序了

所以,按照上边的思想,可以得到下边这个递归公式

公式:
QuickSort(start...end) = QuickSort(start...pivot-1) + QuickSort(pivot+1...end)

终止条件:
start >= end

根据递归的公式,写出来的代码是这个样子

func QuickSort(arr []int, start int, end int) {
    if start >= end {
        return
    }

    pivot := partition(arr, start, end)
    QuickSort(arr, start, pivot-1)
    QuickSort(arr, pivot+1, end)
}

还记得上边的归并排序不,在归并排序里边有一个merge()方法,是将两个有序的数组合并成一个有序的数组。而这里用到了一个partition()函数,就是上边说到的,随机选择一个元素作为分区点(pivot)(一般情况下,可以选择start到end区间的最后一个元素),然后对A[start…end]分区,函数返回分区点(pivot)的下标

知道这个partition()函数是做什么的,下边就是各显神通的去实现它了。如果不考虑空间复杂度的话,就有一个非常简单的方法。申请两个临时数组A和B,然后遍历待分区的数组arr,将小于pivot分区点对应下标值的放到A数组,大于的放到B数组,然后将A数组和B数组中的数据分别顺序的放入到arr中即可。看图:
你以为只是简单的排序?(二)_第4张图片

如果按照这种思路实现的话,partition()函数就需要很多额外的内存空间,所以快排就不是原地排序算法了。如果希望快排是原地排序算法,那它的空间复杂度得是O(1),那partition()分区函数就不能占用太多额外的内存空间,我们就需要在arr的原地完成分区操作

下边的这个就非常巧妙的实现了空间复杂度为O(1)的情况下,完成了分区的操作(反正我是不知道别人是怎么想出来的,没别的法子,理解它,文字描述可能比较难理解,不慌,看图)

func partition(arr []int, start int, end int) int {
    pivotValue := arr[end]
    i := start
    for j:=start;j < end;j++ {
        if arr[j] < pivot {
            arr[i], arr[j] = arr[j],arr[i]
            i++
        }
    }
    arr[i], arr[end] = arr[end], arr[i]

    return i
}

上边是通过游标i,将arr[start...end]分成两个部分,arr[start...i-1]的元素都是小于pivot的,可以叫它“已处理区间”,arr[i...end]是“未处理区间”。每次都从未处理的区间arr[i...end]中取一个元素arr[j],与pivotValue对比,如果小于pivotValue,则将其加入到已处理区间的尾部,也就是arr[i]的位置。文字描述不好理解,看图
你以为只是简单的排序?(二)_第5张图片

快速排序实现

原理上边都介绍了,下边是完整的代码实现

package quickSort

func QuickSort(arr []int, start int, end int) {
    if start >= end {
        return
    }

    pivot := partition(arr, start, end)
    QuickSort(arr, start, pivot-1)
    QuickSort(arr, pivot+1, end)
}


func partition(arr []int, start int, end int) int {
    pivotValue := arr[end]
    i := start
    for j:=start;j < end;j++ {
        if arr[j] < pivotValue {
            arr[i], arr[j] = arr[j],arr[i]
            i++
        }
    }
    arr[i], arr[end] = arr[end], arr[i]

    return i
}

快速排序性能分析

上边使用了一种巧妙的方法,在空间复杂度为O(1)的情况下,实现了快速排序,所以快排是一个稳定的排序算法

因为分区的过程涉及交换操作,如果数组中有两个相同的元素,比如序列 6,8,7,6,3,5,9,4,在经过第一次分区操作之后,两个6的相对先后顺序就会改变(跟着上边的分区算法图,很容易可以推出来)。所以,快速排序并不是一个稳定的排序算法

快排也是用递归来实现的。对于递归代码的时间复杂度,归并排序中分析出来的公式,这里也还是适用的。如果每次分区操作,都能正好把数组分成大小接近相等的两个小区间,那快排的时间复杂度递推求解公式跟归并是相同的。所以,快排的时间复杂度也是O(nlogn)

T(1) = C;   n=1 时,只需要常量级的执行时间,所以表示为 C。
T(n) = 2*T(n/2) + n; n>1

但是,公式成立的前提是每次分区操作,我们选择的pivot都很合适,正好能将大区间对等地一分为二。但实际上这种情况是很难实现的

如果数组中的数据原来已经是有序的了,比如 1,3,5,6,8。如果每次选择最后一个元素作为pivot,那每次分区得到的两个区间都是不均等的。我们需要进行大约n次分区操作,才能完成快排的整个过程。每次分区我们平均要扫描大约n/2个元素,这种情况下,快排的时间复杂度就从O(nlogn)退化成了O(n^2)

快排在大部分情况下的时间复杂度都可以做到O(nlogn),只有在极端情况下,才会退化到O(n^2)

归并排序和快速排序对比

两种排序思想的区别

快排和归并用的都是分治思想,递推公式和递归代码也非常相似,那它们的区别在哪里呢?
你以为只是简单的排序?(二)_第6张图片

可以发现,归并排序的处理过程是由下到上的,先处理子问题,然后再合并。而快排正好相反,它的处理过程是由上到下的,先分区,然后再处理子问题

性能上的差异

归并排序虽然是稳定的、时间复杂度为O(nlogn)的排序算法,但是它是非原地排序算法。归并之所以是非原地排序算法,主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数,可以实现原地排序,解决了归并排序占用太多内存的问题

你可能感兴趣的