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

书旅 · · 428 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

一直在犹豫要不要写排序的文章,因为真的烂大街了。可是一旦细看,还真是很多值的思考的地方,所以还是选择记录一下

以下完整代码,均可从这里获取

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) 的排序算法中,冒泡排序、选择排序,可能就纯粹停留在理论的层面了,学习的目的也只是为了开拓思维,实际开发中应用并不多,但是插入排序还是挺有用的。有些编程语言中的排序函数的实现原理会用到插入排序算法

image.png


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:书旅

查看原文:你以为只是简单的排序?(一)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

428 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传