关于数据结构:你以为只是简单的排序二

47次阅读

共计 5243 个字符,预计需要花费 14 分钟才能阅读完成。

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

归并排序

归并排序思维

归并排序核心思想:将待排序的数据分成前后两个局部,而后对前后两个局部的数据别离进行排序,再将前后两局部合并,失去的后果就是排好序的数据了

语言很形象,看图

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

分治思维跟之前的一篇文章中的递归很像,然而,分治是一种解决问题的解决思维,递归是一种编程技巧。归并排序用的是分治思维,能够用递归来实现

归并排序实现

如果你看过上一篇递归的文章,上边有介绍到,解递归问题,要剖析出递归公式,而后找到递归终止条件,有了这两个,基本上递归代码就进去了。有了上边的那个图,基本上能够失去下边的递推公式

递归公式
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]<arr[j],则将 arr[i]放入到一个新的数组中 tmp,而后 i 向后挪动一位,否则,将 a[j]放入 tmp 中,j 向后一位。反复以上过程,直到有一个子数组空了,而后把另一个子数组中的数据追加到 tmp 的尾部,以上过程,即可将两个别离有序的数组合并成一个有序数组。具体过程如图:

代码实现

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) 的数据放右边,大于分区点的数据放左边,将分区点地位的数据放两头。通过上边的操作之后,分区点之前的数据都小于分区点这个地位的数据,分区点左边的数据都大于分区点这个地位的数据

能够先不必纠结为什么通过一次分区之后变成这个样子了。往下看

依据递归的思维,如果咱们用递归排序下标从 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 中即可。看图:

如果依照这种思路实现的话,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]的地位。文字描述不好了解,看图

疾速排序实现

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

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)

归并排序和疾速排序比照

两种排序思维的区别

快排和归并用的都是分治思维,递推公式和递归代码也十分类似,那它们的区别在哪里呢?

能够发现,归并排序的处理过程是由下到上的,先解决子问题,而后再合并。而快排正好相同,它的处理过程是由上到下的,先分区,而后再解决子问题

性能上的差别

归并排序尽管是稳固的、工夫复杂度为 O(nlogn)的排序算法,然而它是 非原地排序算法。归并之所以是非原地排序算法,次要起因是合并函数无奈在原地执行。疾速排序通过设计奇妙的原地分区函数,能够实现原地排序,解决了归并排序占用太多内存的问题

正文完
 0