排序算法的执行效率
对于排序算法执行效率的分析，我们一般会从这个几个方面衡量：
- 最好情况、最坏情况、平均情况时间复杂度
- 时间复杂度的系数、常数、低阶
- 比较次数和交换（或移动）次数
排序算法的稳定性
比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。
冒泡排序(Bubble Sort)
func BubbleSort(nums []int) []int {
size := len(nums)
if size <= 1 {
return []int{}
}
for i := 0; i < size; i++ {
// 提前退出冒泡循环的标志位
flag := false
for j := 0; j < size-i-1; j++ {
if nums[j] > nums[j+1] {
// 交换
tmp := nums[j]
nums[j] = nums[j+1]
nums[j+1] = tmp
flag = true // 表示数据有交换
}
}
if !flag {
break
}
}
return nums
}
冒泡排序的时间复杂度是多少？
要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。
如果用概率论方法定量分析平均时间复杂度，涉及的数学推理和计算就会很复杂。我这里还有一种思路，通过“有序度”和“逆序度”这两个概念来进行分析。
有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样：
有序元素对：a[i] <= a[j], 如果i < j。
同理，对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n*(n-1)/2，也就是 15。我们把这种完全有序的数组的有序度叫作满有序度。
逆序元素对：a[i] > a[j], 如果i < j。
我们还可以得到一个公式：逆序度 = 满有序度 - 有序度。我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。
我还是拿前面举的那个冒泡排序的例子来说明。要排序的数组的初始状态是 4，5，6，3，2，1 ，其中，有序元素对有 (4，5) (4，6)(5，6)，所以有序度是 3。n=6，所以排序完成之后终态的满有序度为 n*(n-1)/2=15。
冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是n*(n-1)/2–初始有序度。此例中就是 15–3=12，要进行 12 次交换操作。
对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是 0，所以要进行 n*(n-1)/2 次交换。最好情况下，初始状态的有序度是 n*(n-1)/2，就不需要进行交换。我们可以取个中间值 n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。*
换句话说，平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n2)，所以平均情况下的时间复杂度就是 O(n2)。
插入排序(Insertion Sort)
首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。
初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
func InsertionSort(nums []int) []int {
n := len(nums)
if n <= 1 {
return []int{}
}
for i := 1; i < n; i++ {
value := nums[i]
j := i - 1
// 查找插入的位置
for ; j >= 0; j-- {
if nums[j] > value {
nums[j+1] = nums[j] // 数据移动
} else {
break
}
}
nums[j+1] = value // 插入数据
}
return nums
}
过程如图所示：
选择排序(Selection Sort)
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
总结
冒泡排序和插入排序的时间复杂度都是 O(n2)，都是原地排序算法。
为什么插入排序要比冒泡排序更受欢迎呢？
冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。
冒泡排序中数据的交换操作:
if a[j] > a[j+1] {
// 交换
tmp := a[j]
a[j] = a[j+1]
a[j+1] = tmp
flag = true
}
插入排序中数据的移动操作:
if a[j] > value {
a[j+1] = a[j] // 数据移动
} else {
break
}