南京邮电大学数据结构排序

### 南京邮电大学数据结构排序算法教程示例

#### A. 直接插入排序
对于给定的数据元素关键字序列 `65, 78, 21, 30, 80, 7, 79, 57, 35, 26`，采用直接插入排序方法，在第1趟操作之后的结果如下：

- 初始状态：`65 | 78, 21, 30, 80, 7, 79, 57, 35, 26`
- 第1趟结束：`65, 78 | 21, 30, 80, 7, 79, 57, 35, 26`

在第2趟操作之后的状态变为：

- 第2趟结束：`21, 65, 78 | 30, 80, 7, 79, 57, 35, 26`[^1]

#### B. 简单选择排序
同样针对上述序列执行简单选择排序，则有：

- 初始状态：`65, 78, 21, 30, 80, 7, 79, 57, 35, 26`
- 第1趟结束后最小值被选中并交换位置得到新序列：`7, 78, 21, 30, 80, 65, 79, 57, 35, 26`
- 第2趟继续选取次小值进行相应调整后获得：`7, 21, 78, 30, 80, 65, 79, 57, 35, 26`

#### C. 冒泡排序
考虑相同输入情况下应用冒泡排序技术可得：

- 开始时列表为无序态：`65, 78, 21, 30, 80, 7, 79, 57, 35, 26`
- 完成第一次遍历（即第一轮）后的样子是：`65, 21, 30, 78, 7, 79, 57, 35, 26, 80`
- 进行第二次扫描（第二轮），最终形成这样的部分有序化结果：`21, 30, 65, 7, 78, 57, 35, 26, 79, 80`

#### D. 快速排序
当运用快速排序处理同样的数值集时，假设每次都取最左边数作为基准点来进行划分。

- 起初数组呈现随机分布形式：`65, 78, 21, 30, 80, 7, 79, 57, 35, 26`
- 执行首次分割动作后会变成这样两个子区间组合而成的新布局：`(21, 30, 7, 26), 65, (78, 80, 79, 57, 35)`
- 对各分区重复此过程直至完全有序化。这里只展示前两次迭代的效果，具体细节取决于每次选定的枢轴及其周围元素相对大小关系的变化情况

#### E. 两路合并排序
关于二分归并策略的应用实例说明如下所示：

- 原始未整理过的向量表示为：`65, 78, 21, 30, 80, 7, 79, 57, 35, 26`
- 首先将其分解成更小规模的问题求解，比如分成左右两侧分别独立解决后再合起来；经过初次拆分重组可以达到一定程度上的局部有序性：`(21, 30), (65, 78)` 和 `(7, 80), (57, 79)` 及其后续进一步细分直到只剩下一个元素为止。
- 接着逐步向上层回溯过程中不断实施配对式的融合工作来构建全局范围内的递增趋势，从而实现整体上由乱至治的过程转变。此处仅列举最初几步的操作示意而非全部完成形态下的确切表现

#### F. 堆排序
为了便于理解堆排序机制的作用原理以及实际效果体现方式，下面给出了基于最大堆性质的具体实践案例分析：

- 构建初始的最大堆之前原始队列排列状况如下：`65, 78, 21, 30, 80, 7, 79, 57, 35, 26`
- 创建完毕后的完美二叉树形结构对应线性表中的节点顺序应满足父结点总是大于等于孩子结点的要求，此时形成的近似金字塔状图形内部存储单元间存在特定层次级联关联特性，例如可能呈现出类似于 `[80, 78, 79, 30, 26, 7, 21, 57, 35, 65]` 的模式特征。
- 实施首轮下沉式筛选流程过后能够获取到当前集合里的极大项置于首位准备参与后续移除环节，剩余部分继续保持原有形状不变等待下一轮循环检测更新，如此这般反复交替运作直至整个系列变得井然有序为止。本处也仅仅描述了初步转换阶段的情形发展脉络而已

def binary_insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        low, high = 0, i - 1
        
        while low <= high:
            mid = int((low + high) / 2)
            if key < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1
                
        for j in range(i - 1, low - 1, -1):
            arr[j + 1] = arr[j]
            
        arr[low] = key
    
    return arr


if __name__ == "__main__":
    test_arr = [65, 78, 21, 30, 80, 7, 79, 57, 35, 26]
    sorted_result = binary_insertion_sort(test_arr.copy())
    print(f"Original array: {test_arr}")
    print(f"After Binary Insertion Sort: {sorted_result}")