​

1.排序算法

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减排列起来的操作。排序是计算机内经常进行的一种操作，其目的是将一组无序的记录序列调整为有序的记录序列。

评价指标

• 时间复杂度
• 空间复杂度
• 使用场景：针对实际对节省时间和空间的不同需求，选择适用于不同场景的排序算法
• 稳定性：稳定的算法在排序过程中不会改变元素彼此之间次序

选择排序算法O(n)分类

2. 选择排序

• 直接选择排序
• 树形选择排序
• 堆排序

2.1 直接选择排序

直接选择排序（Selection-sort）在冒泡排序基础上做了改进。

排序思想

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
2. 再从剩余未排序元素中继续寻找最小（大）元素，存放到已排序序列的末尾。
3. 依此类推，直到所有元素均排序完毕。

也可以在每一轮中将最小值移动到序列开始，如下图：

伪代码

for i = 1 to n - 1
    k = i
    for j = i + 1 to n
        if A[j] < A[k]
            k = j
    if k != i
        exchange A[i] with A[k]

算法评价

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$
• 适用条件：
  • 参加排序序列的数据量较小（移动较多次元素）
  • 在空间复杂度要求较高时，可以考虑选择排序 （就地排序，空间复杂度低）
• 稳定性： 不稳定 （在不相邻元素间进行交换，所以可能会改变相同元素的相对位置）

2.2 树形选择排序

树形选择排序 又称 锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。

排序思想

1. 两两比较待排序的n个记录的关键字，并取出较小者。
2. 在n/2个较小者中，采用同样的方法比较选出每两个中的较小者。
3. 重复上述过程，直至选出最小关键字记录为止。

可以用n个节点的树来表示，选出的最小关键字记录就是这棵树的根节点。当输出最小关键字之后，为了选出次小关键字，可以设置根节点（最小关键字记录所对应的叶节点）的关键字值为 $\infty$ ，然后再重复上述过程，直到所有记录全部输出为止。

分析：

1. 在树形选择排序中，被选中的关键字都走了一条由叶节点到根节点的比较过程。
2. 因为含有n个叶节点的完全二叉树的深度为${\log }_{2}n+1$（向下取整），所以在树形选择排序中，每当选择一个关键字都需要进行 ${\log }_{2}n$ 次比较，比较的时间复杂度为$O({\log }_{2}n)$。总的算法时间复杂度为$O(n{\log }_{2}n)$。
3. 与简单选择排序相比:
   • 树形选择排序降低了比较次数的数量级 ： $O(n^2)⟶O(n{\log }_{2}n)$
   • 增加了 $n-1$ 个存放中间比较结果的额外存储空间
   • 附加了与 $\infty$ 进行比较的时间耗费

算法评价

• 时间复杂度：$O(n\ast \log n)$
• 空间复杂度：$O(n)$
• 稳定性：稳定 （比较的是相邻元素）

2.3 堆排序

堆排序（Heapsort） 是指利用 堆 这种数据结构所设计的一种排序算法。解决了树形选择排序中 需要额外存储空间 和 需要与 $\infty$ 比较过程。

堆（Heap）：符合以下两个条件之一的完全二叉树：

• 大顶堆：根节点值 ≥ 子节点值。
• 小顶堆：根节点值 ≤ 子节点值。

排序思想

1. 建立初始堆：将无序序列构造成第 1 个大顶堆（初始堆），使得 n 个元素的最大值处于序列的第 1 个位置。
2. 调整堆：交换序列的第 1 个元素（最大值元素）与第 n 个元素的位置。将序列前 n - 1 个元素组成的子序列调整成一个新的大顶堆，使得 n - 1 个元素的最大值处于序列第 1 个位置，从而得到第 2 个最大值元素。
3. 调整堆：交换子序列的第 1 个元素（最大值元素）与第 n - 1 个元素的位置。将序列前 n - 2 个元素组成的子序列调整成一个新的大顶堆，使得 n - 2 个元素的最大值处于序列第 1 个位置，从而得到第 3 个最大值元素。
4. 依次类推，不断交换子序列的第 1 个元素（最大值元素）与当前子序列最后一个元素位置，并将其调整成新的大顶堆。直到子序列剩下一个元素时，排序结束。此时整个序列就变成了一个有序序列。

从堆排序算法步骤中可以看出：堆排序算法主要涉及「调整堆」和「建立初始堆」两个步骤。

• 调整堆方法
  把移走了最大值元素以后的剩余元素组成的序列构造为一个新的堆积。具体步骤如下：
  1. 从根节点开始，自上而下地调整节点的位置，使其成为堆积。
  2. 判断序号为 i 的节点与其左、右子树节点的值关系。
     - 如果 i 节点值 >= 左、右子节点值，则排序结束。
     - 如果 i 节点值 <= 左、右子节点值，则 i 节点与左右节点中较大节点交换位置。
  3. 交换了位置，使得当前节点的左右子树原有的堆积特性被破坏。于是，从当前节点的左右子树节点开始，自上而下继续进行类似的调整。
  4. 依次类推，直到整棵完全二叉树成为一个大顶堆。

• 建立初始堆方法

  1. 如果原始序列对应的完全二叉树（不一定是堆）的深度为 d，则从 d - 1 层最右侧分支节点（序号为 $\frac{n}{2}$ ）开始，初始时令 $i=\frac{n}{2}$ ，调用调整堆算法。
  2. 每调用一次调整堆算法，执行一次 i = i - 1，直到 i == 1 时，再调用一次，就把原始序列调整为了一个初始堆。

对 $[6,2,3,5,1,4]$ 建立初始堆，如下：

算法评价

• 时间复杂度：$O(n\ast \log n)$
• 空间复杂度：$O(1)$
• 稳定性：不稳定 （交换的不是相邻元素）

3. 算法实践(Python)

3.1 直接选择排序

# 直接选择排序选择 max 移动到序列末尾
def selection_max_sort(alist):
	for i in range(len(alist) - 1, 0, -1):
		target = i
		for j in range(0, i):
			if alist[j] > alist[target]:
				target = j
		if target != i:
			alist[i], alist[target] = alist[target], alist[i]
		print('第{}次排序：{}'.format(len(alist) - i,alist))
	return alist

# ---------------------------------------------------------------
# 直接选择排序选择 min 移动到序列开始
def selection_min_sort(alist):
	for i in range(0, len(alist) - 1):
		target = i
		for j in range(i + 1, len(alist)):
			if alist[j] < alist[target]:
				target = j
		if target != i:
			alist[i], alist[target] = alist[target], alist[i]
		print('第{}次排序：{}'.format(len(alist) - i,alist))
	return alist


if __name__ == '__main__':
	alist = [6,2,3,5,1,4]
	print(selection_max_sort(alist))

第1次排序：[4, 2, 3, 5, 1, 6]
第2次排序：[4, 2, 3, 1, 5, 6]
第3次排序：[1, 2, 3, 4, 5, 6]
第4次排序：[1, 2, 3, 4, 5, 6]
第5次排序：[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

3.2 堆排序

参考代码算法通关手册

class Solution:
    # 调整为大顶堆
    def heapify(self, arr: [int], index: int, end: int):
        # 根节点为 index，左节点为 2 * index + 1， 右节点为 2 * index + 2
        left = index * 2 + 1
        right = left + 1
        while left <= end:
            # 当前节点为非叶子结点
            max_index = index
            if arr[left] > arr[max_index]:
                max_index = left
            if right <= end and arr[right] > arr[max_index]:
                max_index = right
            if index == max_index:
                # 如果不用交换，则说明已经交换结束
                break
            arr[index], arr[max_index] = arr[max_index], arr[index]
            # 继续调整子树
            index = max_index
            left = index * 2 + 1
            right = left + 1

    # 初始化大顶堆
    def buildMaxHeap(self, arr: [int]):
        size = len(arr)
        # (size - 2) // 2 是最后一个非叶节点，叶节点不用调整
        for i in range((size - 2) // 2, -1, -1):
            self.heapify(arr, i, size - 1)
        return arr

    # 升序堆排序，思路如下：
    # 1. 先建立大顶堆
    # 2. 让堆顶最大元素与最后一个交换，然后调整第一个元素到倒数第二个元素，这一步获取最大值
    # 3. 再交换堆顶元素与倒数第二个元素，然后调整第一个元素到倒数第三个元素，这一步获取第二大值
    # 4. 以此类推，直到最后一个元素交换之后完毕。
    def maxHeapSort(self, arr: [int]):
        self.buildMaxHeap(arr)
        size = len(arr)
        for i in range(size):
            arr[0], arr[size - i - 1] = arr[size - i - 1], arr[0]
            self.heapify(arr, 0, size - i - 2)
        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.maxHeapSort(nums)

参考

1.一文学懂经典算法系列之直接选择排序
2.张清云.《Python数据结构学习笔记》(ISBN：9787113269999)
3. 算法通关手册

@夏日回音
​