你以为只是简单的排序？（一）

关注
发布于: 2020 年 11 月 14 日
一直在犹豫要不要写排序的文章，因为真的烂大街了。可是一旦细看，还真是很多值的思考的地方，所以还是选择记录一下
﻿
以下完整代码，均可从这里获取
排序算法效率分析了解如何分析一个排序算法，可以帮助我们在实际工作场景中选择合适的排序算法，比如，如果排序的数据比较少，可以选择冒泡或插入排序，如果排序的数据量较大，选择归并或快速排序，虽然它们两两的时间复杂度是相同的，但是还是有很大的区别的，下边会对它们做对比
﻿
排序算法执行效率一般分析一个排序算法的复杂度，我们都是去分析它的时间复杂度，时间复杂度反应的是数据规模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(n2) 的排序算法中，冒泡排序、选择排序，可能就纯粹停留在理论的层面了，学习的目的也只是为了开拓思维，实际开发中应用并不多，但是插入排序还是挺有用的。有些编程语言中的排序函数的实现原理会用到插入排序算法
﻿
﻿