选择排序：简单选择排序和堆排序

一、原理

简单选择排序

• 1.第一轮，找数组中最小的元素并与第一个元素交换。
• 2.第二轮，找(排除第一个元素的)数组中最小数的元素并与第二个元素交换。
• 3.依次迭代。

特点：比较次数多，时间复杂度为；但移动/交换次数少，时间复杂度为。

堆排序

• 相关概念：
  • 堆(Heap)数据结构的特点：
    • 1）完全二叉树。
    • 2）heap中存储的值是偏序。堆分为两类：
      • Min-heap(小根堆)：父节点的值<=子节点的值。
      • Max-heap(大根堆)：父节点的值>=子节点的值。
  • 将数组arr构建成完全二叉树，令n=len(arr)，有：
    • 1）第一个叶子节点的索引：n-1。
    • 2）第一个非叶子节点的索引：n//2-1(n>=2)。
    • 3）父节点的索引为i，则其左右孩子节点的索引分别为：2i+1、2i+2。
• 堆排序流程：
  • 1.给定一个序列arr，先构建成一个完全二叉树，继而构建成堆(若从小到大排序，则构建成大根堆)：
    • 首先，找到第一个非叶子节点的位置start_index=len(arr)//2-1。
    • 从start_index开始由后往前依次遍历每个节点(start_index-->0)，将每个节点调成堆(adjust函数)。
      • 将某一个节点调成堆(adjust函数)的流程：
        • 1）获取当前节点的孩子节点组成family，将family调成堆。
        • 2）一旦有发生父子节点互换的情况，递归将这个互换的子节点的调整成堆(adjust函数)。
  • 2.将堆顶与末尾元素互换，并删除末尾节点(已排序好)，重新将堆顶节点调整成堆(adjust函数)。
  • 3.重复2的过程，直到未排序的元素个数为1。

二、代码实现

题目：随机给定一个数组，按从小到大排序。

逻辑代码：

from time import time
import numpy as np

# 简单选择排序
def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 将某一个节点调整成堆
def adjust_heap(arr, n, parent_idx, reverse=False):
    """
    n表示arr中未排序的元素个数，取arr[0:n]进行调整操作。
    默认reverse=Fasle，表示从小到大排序；reverse=True则表示从大到小排序。
    """
    if n <= 1:
        return
    
    flag_idx = parent_idx  # 标记索引。如果是从小到大排序，flag_idx表示最大值的索引；否则表示最小值的索引。
    l_child_idx = 2 * parent_idx + 1  # 左孩子节点
    r_child_idx = 2 * parent_idx + 2  # 右孩子节点
    if l_child_idx >= n:  # 左孩子节点越界(超过数组的索引范围)
        return
    elif l_child_idx == n - 1:  # 左孩子节点为数组最后一个元素，右孩子节点越界
        if reverse:  # 从大到小排序
            if arr[parent_idx] <= arr[l_child_idx]:  # 父节点最小
                return
            else:  # 左孩子节点最小
                flag_idx = l_child_idx
        else:  # 从小到大排序
            if arr[parent_idx] >= arr[l_child_idx]:  # 父节点最大
                return
            else:
                flag_idx = l_child_idx  # 左孩子节点最大
    else:  # 左、右孩子节点都不越界
        if reverse:  # 从大到小排序
            if arr[parent_idx] <= arr[l_child_idx] and arr[parent_idx] <= arr[r_child_idx]:  # 父节点最小
                return
            elif arr[l_child_idx] <= arr[r_child_idx] and arr[l_child_idx] < arr[parent_idx]:  # 左孩子节点最小
                flag_idx = l_child_idx
            else:  # 右孩子节点最小
                flag_idx = r_child_idx
        else:  # 从小到大排列
            if arr[parent_idx] >= arr[l_child_idx] and arr[parent_idx] >= arr[r_child_idx]:  # 父节点最大
                return
            elif arr[l_child_idx] >= arr[r_child_idx] and arr[l_child_idx] > arr[parent_idx]:  # 左孩子节点最大
                flag_idx = l_child_idx
            else:  # 右孩子节点最大
                flag_idx = r_child_idx
    
    # 标记索引位置改变，则互换父子节点，并递归将子节点调整成堆
    if flag_idx != parent_idx:
        arr[parent_idx], arr[flag_idx] = arr[flag_idx], arr[parent_idx]
        adjust_heap(arr, n, flag_idx, reverse)
        
# 将序列构建成堆
def build_heap(arr, reverse=False):
    """
    默认reverse=Fasle，表示从小到大排序；reverse=True则表示从大到小排序。
    """
    n = len(arr)
    start_index = len(arr) // 2 - 1  # 第一个非叶子节点
    # 从start_index开始由后往前依次遍历每个节点，将每个节点调成堆。
    while start_index >= 0:
        adjust_heap(arr, n, start_index, reverse)
        start_index -= 1
        
# 堆排序
def heap_sort(arr, reverse=False):
    """
    默认reverse=Fasle，表示从小到大排序；reverse=True则表示从大到小排序。
    """
    if len(arr) < 2:
        return arr
    
    # 1.将序列构建成堆
    build_heap(arr, reverse)

    # 2.将堆顶与末尾元素互换，并删除末尾节点(已排序好)，重新将堆顶节点调整成堆。
    # 3.重复2的过程，直到未排序的元素个数为1。
    n = len(arr)  # 未排序的元素个数
    while True:
        arr[0], arr[n - 1] = arr[n - 1], arr[0]  # 将堆顶与末尾元素互换
        n -= 1
        if n == 1:  # 说明未排序的元素个数为1
            break
        adjust_heap(arr, n, 0, reverse)  # 对堆顶元素重新调整成堆
        
        
if __name__ == "__main__":
    # 简单选择排序
    np.random.seed(10)
    array = list(np.random.randint(0, 1000, size=(2000,)))
    start = time()
    selection_sort(array)
    end = time()
    print(f"selection_sort()函数耗时{end - start}秒")
    print(array[:100])
    
    print("----------")
    # 堆排序
    np.random.seed(10)
    array = list(np.random.randint(0, 1000, size=(2000,)))
    start = time()
    heap_sort(array)
    end = time()
    print(f"heap_sort()函数耗时{end - start}秒")
    print(array[:100])

运行结果如下，：