Morse's Site
3913 字
20 分钟
6 排序总结
2020-05-10
algo

6 排序#

如何评价一个排序算法?#

  • 排序算法的执行效率

    • 最好, 最坏, 平均情况时间复杂度

    除了最好, 最坏, 平均情况时间复杂度外, 还需要知道三种情况对应的原始数据是什么样子.

    为什么要区分三种时间复杂度?

      * 为了更好的对比不同的排序算法.
  * 数据的有序度不同, 对算法的执行效率是有影响的.
    • 时间复杂度的常数, 系数和低阶

    时间复杂度是反映数据规模 n 很大时增长的一个趋势, 所以在表示的时候会忽略常数, 系数, 低阶. 所以对同一时间复杂度的算法分析时, 就需要把常数, 系数和低阶也考虑进来.

    • 数据的比较和移动(或交换)次数

    比较的排序算法会涉及两种操作:

      * 元素比较大小
  * 元素交换或移动

    所以分析时需要考虑比较何移动次数

  • 排序算法的内存消耗

原地排序(Sort in place): 指空间复杂度为 O(1) 的排序算法.

  • 排序算法的稳定性

稳定性: 当待排序的元素中存在值相同元素, 经过排序后, 相等元素之间原有的先后顺序保持不变.

如果排序算法不稳定则叫不稳定的排序算法, 反之叫稳定的排序算法.

示例: 10 万单的电商订单, 需要按金额从小到大排序, 金额相同的订单按下单时间从早到晚排序. 使用稳定的排序算法, 先按时间从早到晚排序, 然后在按金额排序. 稳定排序算法可以保持金额相同的订单, 在排序后前后顺序保持不变.

冒泡排序(Bubble Sort)#

// 未优化
func BubbleSort(n []int) {
	for i := 0; i < len(n); i++ {
		for j := 0; j < len(n)-i-1; j++ {
			if n[j] > n[j+1] {
				n[j], n[j+1] = n[j+1], n[j]
			}
		}
	}
}
// 已优化
func BubbleOptimizeSort(n []int) {
	for i, l := 0, len(n); i < l; i++ {
		isBreak := false
		for j := 0; j < l-i-1; j++ {
			if n[j] > n[j+1] {
				n[j], n[j+1] = n[j+1], n[j]
				isBreak = true
			}
		}
		if !isBreak {
			break
		}
	}
}

算法实现要点:

  1. 双重 for 循环

  2. 内层 for 循环从 0 开始, 结束条件: 数组长度 - i - 1, 重点是减 1

    • 为什么减 i: 因为冒泡排序最内层的 for 每循环一次, 都会把本次循环的数组最高位放置一个最大数, 下次内层 for 在开始的时候就不需要在比较了, 所以你会发现最内层的 for 循环次数会越来越小.
    • 为什么减 1: 因为最内层 if 判断时, 获取的两个值的下标是j和j+1, 所以内层 for 循环结束条件必须在减 1

  3. 优化 当内层某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

比较未优化和已优化的代码. 未优化的代码无论入参n是怎样的数列, for 循环次数都为: 6(外层 for 循环次数)+5!(内层 for 循环次数)=21 次, 比如: n = [1, 2, 3, 4, 5, 6]这样的排列也是 21 次. 已优化的代码会在内层 for 循环没有发生过数据交换时, 即if条件每一次都不满足时, 外层 for 直接退出, 也就是说, 极端入参[1, 2, 3, 4, 5, 6], 在优化后循环次数为: 1(外层) + 5(内层: 6 - 0 - 1) = 6 次.

问题#

  • 冒泡排序是原地排序算法么?

是的. 冒泡排序空间复杂度为 O(1)

  • 冒泡排序是稳定排序算法么?

冒泡排序只比较两个数字的大小, 当相等时不做交换, 所以可以满足稳定排序算法的条件.

  • 冒泡排序算法的时间复杂度是什么?

    • 最好情况: [1, 2, 3, 4, 5, 6], 时间复杂度为: O(n)
    • 最坏情况: [6, 5, 4, 3, 2, 1], 时间复杂度为: O(n²)
    • 平均情况:

    有序度: 指数组中具有 有序关系 的 元素对 的个数.

    它的数学表达式: a[i] < a[j], 如果 i < j

    逆序度: 与有序度相反.

    数学表达式: a[i] > a[j], 如果 i < j

    满有序度: 完全有序的数组的有序度叫做 满有序度.

    eg: [1, 2, 3, 4, 5, 6] 就是一个完全有序的数组, 它的有序度为: n*(n-1)/2

    公式: 逆有序度 = 满有序度 - 有序度

    可以发现排序的实质: 增加有序度, 减少逆序度的过程.

    冒泡排序有两个操作: 比较和交换. 每交换一次, 有序度加 1. 不管算法如何改进, 交换次数总是不变的. 即为逆序度. 也就是: 满有序度 - 初始有序度

    eg: [4, 5, 6, 3, 2, 1], 满有序度: 6*(6-1)/2=15, 初始有序度: (4, 5), (5, 6), (4, 6) = 3, 所以逆序度为: 15 - 3 = 12, 所以要交换 12 次.

    对于冒泡排序来说, 最好情况下, 即数组为满有序度下, 交换次数为 0, 不需要交换. 最坏情况下, 即数组的有序度为 0, 需要交换: n*(n-1)/2 次. 所以平均交换为: n*(n-1)/4 次.

    所以平均时间复杂度为: O(n²)

注意: 默认从小到大为有序

插入排序(Insertion Sort)#

插入排序的特点是: 将元素分为两个区间, 已排序区间和未排序区间. 初始的已排序区间只有一个元素, 即数组的第一个元素.

插入排序算法的核心思想是: 每次取未排序区间中的一个元素, 在已排序区间中找到合适的位置将其插入, 并把已排序区间这个位置之后的元素向后移位. 这个过程中已排序区间的数据始终是有序的. 重复这个过程, 直到未排序区间的元素为空.

插入排序也有两个操作: 元素比较, 元素移动. 一般找到插入点(就是比较大小条件满足后), 先将元素向后移位, 在将元素插入.

func InsertionSort(n []int) {
	for i, l := 1, len(n); i < l; i++ {
		value, j := n[i], i-1
		for ; j >= 0; j-- {
			if n[j] > value {
				n[j+1] = n[j]
			} else {
				break
			}
		}
		n[j+1] = value
	}
}

算法注意要点:

  1. 初始已排序区间只有一个元素, 所以外层 for 从数字 1 开始. 即未排序区间从数组下标 1 开始.

  2. 内层 for 是拿已排序区间的元素循环, 因为存在元素移位, 所以必须从高位往地位循环. (如果从地位开始循环, 会存在地位的元素覆盖高位元素)

  3. 元素比较的 if 分支中, 如果不满足必须break, 否则会有 bug.

    • 因为从高位开始循环, 所以当高位的第一个元素都不满足条件, 那就没有必要在继续循环了, 所以直接break.
    • n[j+1] = value这里用到了 j, 如果不break, 就会执行 for 的j--操作, 会产生 bug.

问题#

  • 插入排序是原地排序算法吗?

插入排序的空间复杂度为 O(1), 所以是原地排序算法.

  • 插入排序是稳定排序算法吗?

在插入排序算法中, 元素移位只发生在大于的情况, 对于值相同的元素, 会保持排序之前得前后顺序. 所以插入排序是稳定的排序算法.

  • 插入排序的时间复杂度是多少?

    • 最好情况: O(n), 如 [1, 2, 3, 4, 5, 6]
    • 最坏情况: O(n²), 如 [6, 5, 4, 3, 2, 1]
    • 平均情况:

    往数组中插入一个数据的平均时间复杂度为 O(n), 所以对于插入排序, 每次插入操作相当于在数组中插入一个数据, 循环执行 n 次插入操作, 所以插入排序的时间复杂度为 O(n²)

选择排序(Selection Sort)#

选择排序与插入排序类似, 也分两个区域已排序区域和未排序区域. 区别是选择排序每次会从未排序区域中找到最小的元素, 将其放在已排序区域的最右边.


func SelectionSort(n []int) {
	for i, l := 0, len(n); i < l; i++ {
		value, index := n[i], i
		for j := i; j < l; j++ {
			if value > n[j] {
				value = n[j]
				index = j
			}
		}
		n[i], n[index] = value, n[i]
	}
}

问题#

  • 选择排序是原地排序算法吗?

选择排序算法的空间复杂度为 O(1), 所以选择排序是原地排序算法.

  • 选择排序的时间复杂度是什么?

    • 最好情况: O(n²), [1, 2, 3, 4, 5, 6]
    • 最坏情况: O(n²), [6, 5, 4, 3, 2, 1]
    • 平均情况: O(n²)

  • 选择排序是稳定排序算法吗?

选择排序不是稳定排序算法, 选择排序每次都要找到未排序区域内最小值元素, 然后元素交换, 所以当未排序区域内有两个相同最小值, 交换后会改变这两个值的元素顺序了. 比如 [5, 8, 5, 2, 9], 第一次找到 2 后与 5 交换, 那么 5 的顺序就与原来 5 的顺序不一致了.

  • 冒泡排序与插入排序的时间复杂度都是 O(n²), 且都是原地排序算法, 为什么插入排序要比冒泡排序受欢迎呢?

因为从代码的实现上来看, 冒泡排序的数据交换插入排序的数据移动要复杂, 冒泡排序需要 3 个赋值操作, 而插入排序这需要 1 个.

归并排序(MergeOrder)#

归并排序简单来说就是把一个数组从中间分为两部分, 对这两部分分别排序, 然后在将排序好的两部分合并在一起.

归并排序采用了分治思想, 分治, 就是分而治之, 将一个大问题分解为小的子问题. 小的问题解决了, 大的问题也就解决了.

分治与递归很像. 但是分治是一种解决问题的思想, 递归是一种编程技巧.


func MergeSort(n []int) {
	if len(n) <= 1 {
		return
	}
	copy(n, merge(n))
}

func merge(n []int) []int {
	if len(n) <= 1 {
		return n
	}

	middle := len(n) / 2

	m1, m2 := merge(n[0:middle]), merge(n[middle:])

	return func(m1, m2 []int) []int {
		r := make([]int, 0, len(m1)+len(m2))
		i, j := 0, 0
		var s []int
		for {
			v1, v2 := m1[i], m2[j]
			switch {
			case v1 > v2:
				j++
				r = append(r, v2)
			case v2 > v1:
				i++
				r = append(r, v1)
			default:
				i++
				j++
				r = append(r, v1, v2)
			}
			if i >= len(m1) {
				s = m2[j:]
				break
			}
			if j >= len(m2) {
				s = m1[i:]
				break
			}
		}
		r = append(r, s...)
		return r
	}(m1, m2)
}

注意点:

* 归并排序采用分而治支之的思想, 所以它把原始数组按递归的思想拆成最少为一个元素的数组.
* 在合并的时候, 入参的两个数组再 for 循环时, 有可能不会同时 put 到新的数组中, 所以需要把剩余数组中的元素再次添加到新数组中(`r = append(r, s...)`)

问题#

  • 归并排序是稳定排序算法吗?

是否稳定需要看meger()函数对相同数据的处理, 所以归并排序是一个稳定排序算法

  • 归并排序算法的时间复杂度是什么?

归并排序使用了递归. 递归的适用场景是, 一个问题可以分解为多个相同的子问题.

假设对 n 个元素进行归并排序需要的时间是 T(n). 因为归并每次都要按半分解, 所以一半的元素的归并时间为T(n/2). 因为归并的最后一步需要合并, 对于 n 个元素, 那么就是 O(n), 合到一起, 公式如下:

T(1) = C; n = 1 时, 只需要常量级的执行时间, 所以用大 C 表示
T(n) = 2 * T(n/2) + n; n > 1

我们对上面公式进行分解:

因为归并每次都是对半分解, 所以我们可以将 T(n/2)每次对半分解:

# 注意必须对半分解
T(n) = 2 * T(n/2) + n
# n/2 的一半 n/4
= 2 * (2 * T(n/4) + n/2) + n = 4 * T(n/4) + 2n
# n/4 的一半 n/8
= 4 * (2 * T(n/8) * n/8) + 2n = 8*T(n/8) + 3n
# n/8 的一半 n/16
= 8 * (2 * T(n/16) + n/16) + 3n = 16*T(n/16) + 4n
# 依此类推...
= 2^m * T(n/2^m) + m*n

所以时间公式为: T(n) = 2^m * T(n/2^m) + m * n 因为分解最终条件, 即递归的终止条件为数组长度为 1 时, 停止递归, 所以 T(n/2^m) = T(1), 即: n/2^m = 1 => n = 2^m, 所以 m = log2n, 将 m 代入公式中. 所以大 O 表示法为: O(n) = n*logn

所以归并排序的时间复杂度为: nlogn, 且最好情况, 最坏情况, 平均时间下时间复杂度都为: nlogn

归并排序的执行效率与原始数据的有序程度无关

  • 归并排序是否为原地排序, 如果不是那它的空间复杂度是多少?

归并排序不是原地排序, 这是它的致命弱点. 因为排序时归并排申请了原始数据大小的空间, 它的空间复杂度为 O(n).

快速排序(QuickSort)#

快速排序也是利用分治+递归的思想, 它从数组中选任意一个数据作为分区点, 即pivot. 然后把大于pivot 的数据放在右边, 小于pivot 的数据放在右边. 这样数据就被分为三部分: 小于pivot, 大于pivot 和pivot 自身. 利用递归的思想, 把前后两部分数据继续递归, 直到只有一个元素为止.

随机选取一个元素作为pivot, 一般选取入参数组的最后一个元素.

func QuickSort(n []int) {
	if len(n) <= 1 {
		return
	}
	p := position(n)
	QuickSort(n[:p])
	QuickSort(n[p+1:])
}

func position(n []int) int {
	maxIndex := len(n) - 1
	pivot := n[maxIndex]
	index := 0

	for i := 0; i < maxIndex; i++ {
		if n[i] < pivot {
			n[index], n[i] = n[i], n[index]
			index++
		}
	}
	n[index], n[maxIndex] = pivot, n[index]
	return index
}

问题#

  • 快速排序与归并排序的区别

    • 归并排序处理过程是由下向上的, 即先处理子问题, 再合并.
    • 快速排序则是由上向下的, 先分区, 再处理子问题.

  • 快速排序是稳定排序算法吗?

不是, 快速排序每次随机获取一个数(一般这个数取数组中最后一个元素), 然后比它小的放在右边, 大的放在左边. 这时有可能会改变相同元素元素的原始顺序.

  • 快速排序是原地算法吗?

快速排序返回中间数字位置时, 使用了一个巧妙的方法, 类似插入排序, 即始终把比随机数小的元素放在右边, 即从数组下标 0 开始, 这样就不用申请新的空间存储再合并. 所以排序算法是原地算法.

  • 快速排序的时间复杂度是什么?

推导过程与归并一样.

T(1) = C；   n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n； n>1

但是让公式成立很难, 因为每次随机获取的这个数, 不一定对应分区的元素都是一半.

所以当每次分区都是均等时, 快速排序的时间复杂度为 O(nlogn).

当分区数据不均等时, 快排的时间复杂度就会变为: O(n²)

#阅读/数据结构与算法之美

6 排序总结
https://fuwari.vercel.app/posts/algo/sort/
作者
Morse Hsiao
发布于
2020-05-10
许可协议
CC BY-NC-SA 4.0
Kubernetes - Pod
通过 `Gossip协议` 与 `StatefulSet` 构建监控报警模块集群