电脑和手机都能浏览的网站开发,wordpress域名修改,wordpress什么是分页,音频文件放到网站空间里生成链接怎么做一直在犹豫要不要写排序的文章#xff0c;因为真的烂大街了。可是一旦细看#xff0c;还真是很多值的思考的地方#xff0c;所以还是选择记录一下以下完整代码#xff0c;均可从这里获取https://github.com/Rain-Life/data-struct-by-go/tree/master/sort排序算法效率分析了…一直在犹豫要不要写排序的文章因为真的烂大街了。可是一旦细看还真是很多值的思考的地方所以还是选择记录一下以下完整代码均可从这里获取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 : falsen : len(arr)for i : 0; i n; i {flag false//如果某一次冒泡没有出现数据交换说明已经有序不用再继续冒泡了for j : 0; j n-i-1; j {if arr[j] arr[j1] {tmp : arr[j]arr[j] arr[j1]arr[j1] tmpflag true}}if !flag {break}}for _, v : range arr {fmt.Printf(%vt, 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-1for ; j 0; j-- { //j遍历的是已排区的每一个元素if arr[j] value {arr[j1] arr[j] //如果满足条件将前一个值赋给后边这个} else {break}}arr[j1] value}for _, v : range arr {fmt.Printf(%vt, 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 : i1; j n ; j {if arr[i] arr[j] {arr[i],arr[j] arr[j], arr[i]}}}for _, v : range arr {fmt.Printf(%vt, v)}
}
选择排序算法分析选择排序的空间复杂度也是O(1)是原地排序算法。选择排序的最好情况和最坏情况的时间复杂度都是O(n^2)这个很简单看一下它的执行过程就知道了「选择排序不是一个稳定排序」选择排序每次都要找剩余未排序元素中的最小值并和前面的元素交换位置这样破坏了稳定性比如735719 这样一组数据使用选择排序算法来排序的话第一次找到最小元素1与第一个7交换位置那第一个7和中间的7顺序就变了所以就不稳定了这样一看选择排序和前边两个排序算法相比就差一些了三种排序算法对比这里就先不提选择排序了因为和前两种相比它明显逊色一些冒泡排序不管怎么优化元素交换的次数是一个固定值。插入排序是同样的不管怎么优化元素移动的次数也是一个固定值。但是从冒泡和插入排序的代码上看冒泡排序的数据交换次数比插入排序要复杂冒泡排序需要3个赋值操作而插入排序只需要1个冒泡排序的交换操作
if arr[j] arr[j1] {tmp : arr[j]arr[j] arr[j1]arr[j1] tmpflag true
}选择排序的交换操作
if arr[j] value {arr[j1] arr[j]
}假设把一次赋值操作的时间算作一个单位时间那冒泡排序的交换操作需要3个单位时间而插入排序只需要1个单位时间如果需要排序的数据比较少可能这样的差别可以忽略不计但是数据多起来之后插入排序节省的时间还是比较明显的这三种时间复杂度为 O(n2) 的排序算法中冒泡排序、选择排序可能就纯粹停留在理论的层面了学习的目的也只是为了开拓思维实际开发中应用并不多但是插入排序还是挺有用的。有些编程语言中的排序函数的实现原理会用到插入排序算法
