一直在犹豫要不要写排序的文章,因为真的烂大街了。可是一旦细看,还真是很多值的思考的地方,所以还是选择记录一下
以下完整代码,均可从这里获取
https://github.com/Rain-Life/data-struct-by-go/tree/master/sort
排序算法效率分析
了解如何分析一个排序算法,可以帮助我们在实际工作场景中选择合适的排序算法,比如,如果排序的数据比较少,可以选择冒泡或插入排序,如果排序的数据量较大,选择归并或快速排序,虽然它们两两的时间复杂度是相同的,但是还是有很大的区别的,下边会对它们做对比
排序算法执行效率
一般分析一个排序算法的复杂度,我们都是去分析它的时间复杂度,时间复杂度反应的是数据规模n很大的时候的一个增长趋势。所以,通常在分析时间复杂度的时候会忽略到系数、常数、低阶。但是,在实际开发场景中,可能我们排序的数据并不多,因此,在对排序算法进行分析的时候,还是需要将系数、常数、低阶也考虑进来
分析一个排序算法的时间复杂度的时候,通常会分析它的最好情况、最坏情况以及平均情况下的时间复杂度。因为对于要排序的数据,它的有序度,对排序算法的执行时间是有影响的,所以,要想选择最合适的排序算法,这些情况的时间复杂度都应该考虑到(其实不光是排序,在实现任何一个算法的时候,当有多种方式可供选择的时候,都应该分析多重情况下的时间复杂度)
下边要分享的三个排序算法都是基于比较的排序算法,基于比较的排序算法的在执行过程中,一般涉及两种操作,一个是比较大小,一个是数据交换。因此,在对比这几种排序算法的时候,比较次数和移动次数也应该考虑进去。这也是为什么基于比较排序的算法,我们通常不会选择冒泡排序,而选择插入排序
排序算法内存消耗
算法的内存消耗可以通过空间复杂度来衡量。针对排序算法的空间复杂度,有一个新的概念是原地排序。原地排序算法,就是特指空间复杂度是O(1)的排序算法。下边要分享的三种排序算法,都是原地排序算法
排序算法稳定性
只靠执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法,还有一个重要的度量指标,稳定性。意思是,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变
如:1、8、6、5、5、7、2、3,按照大小排序之后是:1、2、3、5、5、6、7、8
这组数据里有两个5。经过某种排序算法排序之后,如果两个5的前后顺序没有改变,那我们就把这种排序算法叫作稳定的排序算法;如果前后顺序发生变化,那对应的排序算法就叫作不稳定的排序算法
冒泡排序
冒泡排序优化
冒泡排序的实现思想,相信大家都非常的熟悉了
每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作
实际上,冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时,说明已经达到完全有序,不用再继续执行后续的冒泡操作。如图
下边是优化后的代码:
func BubbleSort(arr []int) {
flag := false
n := len(arr)
for i := 0; i < n; i++ {
flag = false//如果某一次冒泡,没有出现数据交换,说明已经有序,不用再继续冒泡了
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
tmp := arr[j]
arr[j] = arr[j+1]
arr[j+1] = tmp
flag = true
}
}
if !flag {
break
}
}
for _, v := range arr {
fmt.Printf("%v\t", v)
}
}
冒泡排序算法分析
首先冒泡排序是一个原地排序算法,因为冒泡排序只涉及相邻数据的交换,需要常量级的临时空间,所以空间复杂度是O(1)
在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法
在最好的情况下,也就是待排数据是完全有序的,那只需要进行一次冒泡操作即可,所以最好情况下的时间复杂度是O(n)
最坏情况下是待排数据是完全无序的,这个时候就需要n次冒泡,所以最坏情况下的时间复杂度是O(n^2)
平均情况下的时间复杂度的分析涉及比较复杂的推导,不是这里的重点(我也不会,手动狗头。如果你想了解,可以看这里),冒泡排序算法的平均时间复杂度是O(n^2)
插入排序
插入排序思想
插入排序是如何来的?假设现在有一个有序的数组,让你往里边插入一个数据之后,保持数组是有序的。我们都会想到通过遍历来找到待插入数据的位置,然后进行数据的移动。通过这种方式就可以保证这个数组有序。借鉴上边这种插入方法,于是就有了插入排序
插入排序的思想是:将待排序的数组分成两个区间,有序区和无序区。刚开始的时候,有序区只有第一个元素。插入排序的过程就是每次从无序区中取出一个元素,放入到有序区中对应的位置,保证插入到有序区中之后,有序区依然是有序的。不断的重复这个过程,直到无序区为空
文字描述比较抽象,见下图(从小到大排序)
插入排序也是包含两种操作,一种是比较,一种是移动。下边是代码实现
func InsertSort(arr []int) {
if len(arr) <= 0 {
fmt.Println("待排数据不合法")
}
n := len(arr)
for i := 1; i < n; i++ {//i是待排区的元素
value := arr[i]
j := i-1
for ; j >= 0; j-- { //j遍历的是已排区的每一个元素
if arr[j] > value {
arr[j+1] = arr[j] //如果满足条件,将前一个值赋给后边这个
} else {
break
}
}
arr[j+1] = value
}
for _, v := range arr {
fmt.Printf("%v\t", v)
}
}
插入排序算法分析
插入排序也不需要额外的存储空间,空间复杂度是O(1),所以它是原地排序算法
在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法
如果待排序的数据是完全有序的,并不需要搬移任何数据。如果从尾到头在有序数据组里面查找插入位置,每次只需要比较一个数据就能确定插入的位置。所以这种情况下,最好是时间复杂度为O(n)。注意,这里是从尾到头遍历已经有序的数据
如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,所以最坏情况时间复杂度为O(n^2)。平均时间复杂度也是O(n^2)
选择排序
选择排序思想
选择排序的思想和插入排序的思想有些类似,选择排序是每次从无序区中选择一个最小的元素放入到有序区中,具体如图:
代码实现如下
func SelectionSort(arr []int) {
n := len(arr)
if n <= 0 {
fmt.Println("待排数据不合法")
}
for i := 0; i < n - 1; i++ {
for j := i+1; j < n ; j++ {
if arr[i] > arr[j] {
arr[i],arr[j] = arr[j], arr[i]
}
}
}
for _, v := range arr {
fmt.Printf("%v\t", v)
}
}
选择排序算法分析
选择排序的空间复杂度也是O(1),是原地排序算法。选择排序的最好情况和最坏情况的时间复杂度都是O(n^2),这个很简单,看一下它的执行过程就知道了
选择排序不是一个稳定排序,选择排序每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性
比如7,3,5,7,1,9 这样一组数据,使用选择排序算法来排序的话,第一次找到最小元素1,与第一个7交换位置,那第一个7和中间的7顺序就变了,所以就不稳定了
这样一看,选择排序和前边两个排序算法相比就差一些了
三种排序算法对比
这里就先不提选择排序了,因为和前两种相比,它明显逊色一些
冒泡排序不管怎么优化,元素交换的次数是一个固定值。插入排序是同样的,不管怎么优化,元素移动的次数也是一个固定值。但是,从冒泡和插入排序的代码上看,冒泡排序的数据交换次数比插入排序要复杂,冒泡排序需要3个赋值操作,而插入排序只需要1个
冒泡排序的交换操作
if arr[j] > arr[j+1] {
tmp := arr[j]
arr[j] = arr[j+1]
arr[j+1] = tmp
flag = true
}
选择排序的交换操作
if arr[j] > value {
arr[j+1] = arr[j]
}
假设把一次赋值操作的时间算作一个单位时间,那冒泡排序的交换操作需要3个单位时间,而插入排序只需要1个单位时间
如果需要排序的数据比较少,可能这样的差别可以忽略不计,但是数据多起来之后,插入排序节省的时间还是比较明显的
是否是原地排序 | 是否是稳定排序 | 最好情况 | 最坏情况 | 平均情况 | |
---|---|---|---|---|---|
冒泡排序 | 是 | 是 | O(n) | O(n^2) | O(n^2) |
插入排序 | 是 | 是 | O(n) | O(n^2) | O(n^2) |
选择排序 | 是 | 否 | O(n^2) | O(n^2) | O(n^2) |
这三种时间复杂度为 O(n2) 的排序算法中,冒泡排序、选择排序,可能就纯粹停留在理论的层面了,学习的目的也只是为了开拓思维,实际开发中应用并不多,但是插入排序还是挺有用的。有些编程语言中的排序函数的实现原理会用到插入排序算法
有疑问加站长微信联系(非本文作者)