数据结构与算法-第八章-内排序

第八章内排序

内部排序：待排序记录数少，放在内存，排序过程在内存进行，称为内部排序（internal sorting）
外部排序：待排序记录数大，内存无法容纳所有记录，排序过程中还需要访问外存，称为外部排序（external sorting）

8.1 基本概念

记录（Record）：进行排序的基本单位
关键码（Key）：唯一确定记录的一个或多个域
排序码（Sort Key）：作为排序运算依据的一个或多个域
序列（Sequence）：线性表，由记录组成的集合
排序（Sorting）：将序列中的记录按照排序码特定的顺序排列起来，即排序码，即排序码域的值具有不减（或不增）的顺序

排序定义

给定一个序列 $R = { r_1, r_2, \ldots, r_n }$，其排序码分别为 $K = { k_1, k_2, \ldots, k_n }$，排序的目的就是将 R 中的记录按照特定的顺序重新排列，形成一个新的有序序列 $R’ = { r’_1, r’_2, \ldots, r’_n }$

相应排序码为K
排序码有不减序和不增序
稳定算法与不稳定算法
- 若序列中的两个记录排序码相等，排序前后的相对位置保持不变，则是稳定算法，否则是不稳定的。
排序算法的衡量标准
- 时间代价：记录的比较和交换次数
  - 最小时间代价
  - 最大时间代价
  - 平均时间代价
- 空间代价：所需附加空间的大小
排序算法的种类
- 简单排序：O（n^2）
  - 插入排序（Insert sort）
  - 直接选择排序（Selection sort）
  - 冒泡排序（Bubble sort）
- Shell排序（Shell sort）
- 分治排序
  - 快速排序（Quicksort）
  - 归并排序（Mergesort）
- 堆排序（Heapsort）
- 分配排序（Binsort）

8.2 三种O（n^2）的简单排序

优点：简单，易于实现
缺点：复杂性高，不适合对大规模记录文件进行排序

插入排序

依次将每个待排序的记录插入到一个有序子文件的合适位置

void StraightInsertSorter(Record Array[], int n){
    for (int i=1; i<n; i++) {        //依次插入第i个记录
        for (int j=i; j>0; j--){
            if (Array[j]< Array[j-1])
                swap(Array,j, j-1);
            else break;            //此时前面记录已排序
        }
    }
}

算法是稳定的
空间代价：$\Theta(1)$，交换操作需要一个辅助空间
时间代价
- 最佳情况（正序）：$n-1$次比较，0次交换，$\Theta(n)$复杂度
- 最差情况（逆序）：比较和交换次数为 $\sum_{i=1}^{n-1} i = n(n-1)/2 = \Theta(n^2)$
- 平均情况：$\Theta(n^2)$

优化的插入排序算法

Void ImprovedInsertSorter (Record Array[], int n) {
    Record TempRecord;          //临时变量
    for (int i=1; i<n; ++i) {   //依次插入第i个记录
        TempRecord=Array[i];    //待插入记录存入临时变量
        int j = i-1;
        while ((j>=0) && (TempRecord < Array[j])){
            Array[j+1] = Array[j]; j = j - 1;
        }
        Array[j+1] = TempRecord; //临时变量值回填到j位置
    }
}

将待插入值存储起来，需要的交换的值只进行后移覆盖。可以减少一半的操作

基于二分查找的插入排序

void BinaryInsertSorter(Record Array[], int n) {
    Record TempRecord; int left, right, middle;
    for (int i=1; i<n; ++i) {      //依次插入第i个记录
        TempRecord = Array[i];     //保存当前待插入记录
        left = 0; right = i-1;     //记录已排好序列的左右位置
        while (left <= right) {
            middle = (left+right)/2;
            if (TempRecord < Array[middle])
                right = middle-1;
            else left = middle+1;
        }
        for(int j = i-1; j >= left; --j) { //记录后移
            Array[j+1] = Array[j];
        }
        Array[left] = TempRecord;  //插入left指针位置
    }
}

移动条件： <middle，right左移（middle-1）； ≥middle，left右移（middle+1）。
结束条件：left>right；
插入位置：left

算法是稳定的
空间代价：$\Theta(1)$
时间代价
- 比较次数降为$n\log n$量级：插入每个记录需$\Theta(\log n)$次比较
- 移动次数仍为$n^2$量级：每插入一个记录最多移动$i+1$次
- 因此，最佳情况下总时间代价为$\Theta(n \log n)$，最差和平均情况仍为$\Theta(n^2)$

冒泡排序

基本思想：不断比较相邻记录，不满足排序要求则交换，直到所有记录有序
原理：若序列有n个元素，通常进行n-1趟；第i趟针对第0至n-i-1个元素比较交换

void BubbleSorter(Record Array[], int n){
    for (int i=1; i<n; i++)       //向前冒泡
        //依次比较相邻记录，发现逆序则交换
        for (int j=n-1; j>=i; j--)
            if (Array[j] < Array[j-1])
                swap(Array,j,j-1);
}

算法是稳定的
空间代价：$\Theta(1)$的临时空间
时间代价
- 比较次数：$\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2} = \Theta(n^2)$
- 交换次数：最多$\Theta(n^2)$、最少0，平均$\Theta(n^2)$
- 总时间代价：最佳/最差/平均均为$\Theta(n^2)$

优化的冒泡排序

优化思路：检查每趟是否发生交换，若无则数组已有序，提前结束排序
结束条件：不再有元素交换

void ImprovedBubbleSorter(Record Array[], int n) {
    bool NoSwap;  //是否交换的标志
    for (int i=1; i<n; i++) {
        NoSwap = true;
        for (int j=n-1; j>=i; j--) {
            if (Array[j] < Array[j-1]) {
                swap(Array,j,j-1);
                NoSwap = false;
            }
        }
        if (NoSwap) return;  //无交换则直接结束
    }
}

时间代价：最佳情况（已有序）为$\Theta(n)$，其他情况仍为$\Theta(n^2)$

直接选择排序

基本思想：每一趟在后续n-i个待排记录中选取最小记录，与第i个记录互换
具体过程：
1. 先在n个记录中选最小者与r[0]互换；
2. 再从剩余n-1个记录中选最小者与r[1]互换；
3. 重复至全部有序
优点：实现简单
缺点：每趟仅确定一个元素，表长为n时需n-1趟

void StraightSelectSorter(Record Array[], int n) {
    //依次选出第i小的记录（剩余记录中最小的那个）
    for (int i=0; i<n-1; i++){
        int Smallest = i;        //假设当前记录是最小的
        for (int j=i+1; j<n; j++)//向后扫描剩余记录
            if (Array[j] < Array[Smallest])
                Smallest = j;    //记录更小记录的位置
        swap(Array, i, Smallest);//将第i小的记录放到第i个位置
    }
}

时间效率：$\Theta(n^2)$（移动次数少，但比较次数多）
空间效率：$\Theta(1)$（仅用1个中间变量）
算法的稳定性：不稳定（如排序中25*会到25前面）

8.3 Shell排序

提出基础：基于直接插入排序的两个性质
1. 待排序列较短时效率高
2. 整体有序时时间代价低
别称：“缩小增量排序”，1959年由D.L.Shell提出

核心思路（利用上述性质）

初始无序时，等间隔分割小序列：将待排序列拆分为若干小序列，在小序列内做直接插入排序；
序列趋向有序后，逐步扩大序列规模：扩大小序列范围、减少小序列个数，让序列更有序；
最后，对整个序列做一次插入排序。

具体实现方法

选定间隔增量序列：$n>d_1>d_2>…>d_t=1$（$n$为序列长度，$d_i$为间隔增量）；
按$d_1$分组：相距$d_1$的元素为一组，组内直接插入排序；
按$d_2,…,d_t$重复分组+排序；
- Shell最初提出的增量序列：$d_1=\lfloor n/2 \rfloor, d_{i+1}=\lfloor d_i/2 \rfloor$

Shell排序过程

原始序列：8, 9, 1, 7, 2, 3, 5, 4, 6, 0（长度$n=10$）

$d=5$（$\lfloor10/2\rfloor$）分组排序：
- 分组规则：下标差为5的元素为一组，共5组：[8,3]、[9,5]、[1,4]、[7,6]、[2,0]
- 组内插入排序后：[3,8]、[5,9]、[1,4]、[6,7]、[0,2]
- 排序后序列：3, 5, 1, 6, 0, 8, 9, 4, 7, 2
$d=2$（$\lfloor5/2\rfloor$）分组排序：
- 分组规则：下标差为2的元素为一组，共2组：[3,1,0,9,7]、[5,6,8,4,2]
- 组内插入排序后：[0,1,3,7,9]、[2,4,5,6,8]
- 排序后序列：0, 2, 1, 4, 3, 5, 7, 6, 9, 8
$d=1$全序列插入排序：
- 对整体序列做直接插入排序，最终结果：0, 1, 2, 3, 4, 5, 6, 7, 8, 9

算法代码（delta=2版本）

// Shell排序主函数
Void ShellSorter (Record Array[], int n){
    for (int delta=n/2; delta>0; delta/=2)
        // 对delta个子序列分别排序
        for (int j=0; j<delta; j++)
            ModifiedInsertSort(&Array[j], n-j, delta);
}

// 带增量的插入排序（子序列排序）
ModifiedInsertSort(Record Array[], int n, int delta) {
    // 对子序列中第i个记录排序
    for (int i=delta; i<n; i+=delta)
        for (int j=i; j>=delta; j-=delta){
            if (Array[j] < Array[j-delta])
                swap(Array,j,j-delta);
            else break;
        }
}

分析

增量序列：可自定义（只要满足$d_1<n、d_t=1$）；
- Hibbard增量序列：${2^k-1, 2^{k-1}-1,…,7,3,1}$，此时时间复杂度可达$\Theta(n^{3/2})$；
稳定性：不稳定的排序方法；
性能：比直接插入排序快，平均时间复杂度约$\Theta(n^{1.3})$，空间复杂度$\Theta(1)$。

8.4 基于分治法的排序

分治法核心：将原序列拆分为若干子部分，分别排序后合并，是常用的问题求解思想。典型算法：快速排序、归并排序

快速排序（C.A.R.Hoare，1962）

分治思想

轴值选择：选待排序列中一个元素（轴值）作为划分基准；
序列划分：将序列分为子序列L和R，L中元素≤轴值，R中元素≥轴值（轴值处于最终位置）；
递归排序：对L、R递归执行划分，直到子序列长度≤1。

算法代码

void QuickSort(Record Array[], int left, int right) {
    if (left < right) {
        int pivot = SelectPivot(left, right); // 选择轴值
        pivot = Partition(Array, left, right); // 划分序列
        QuickSort(Array, left, pivot-1); // 递归左子序列
        QuickSort(Array, pivot+1, right); // 递归右子序列
    }
}

关键问题

轴值选择（目标：让L、R长度接近）
- 固定位置法（如选首/尾元素）；
- 中值计算法（选首、尾、中间元素的中值）；
- 随机选择法。

序列划分（以首元素为轴值为例）

int Partition(Record Array[], int left, int right) {
 int i = left, j = right;
 Record pivotValue = Array[left]; // 轴值存临时变量
 while (i != j) {
     while ((Array[j] > pivotValue) && (i < j)) j--; // 右指针左移
     if (i < j) Array[i++] = Array[j]; // 交换
     while ((Array[i] <= pivotValue) && (i < j)) i++; // 左指针右移
     if (i < j) Array[j--] = Array[i]; // 交换
 }
 Array[i] = pivotValue; // 轴值归位
 return i; // 返回轴值位置
}

排序过程示例

原始序列：50, 10, 90, 30, 70, 40, 80, 60, 20

选50为轴值，划分后：20, 10, 40, 30, 50, 70, 80, 60, 90（50归位，左子序列20,10,40,30，右子序列70,80,60,90）；
递归排序左子序列20,10,40,30：选20为轴值，划分后10, 20, 40, 30，再递归排序40,30得30,40，左子序列最终为10,20,30,40；
递归排序右子序列70,80,60,90：选70为轴值，划分后60, 70, 80, 90，右子序列最终为60,70,80,90；
合并所有有序子序列，最终结果：10, 20, 30, 40, 50, 60, 70, 80, 90。

算法分析

| 情况 | 时间复杂度 | 空间复杂度（递归栈） | |——–|————|———————-| | 最佳 | $\Theta(n\log n)$ | $\Theta(\log n)$ | | 最差 | $\Theta(n^2)$ | $\Theta(n)$ | | 平均 | $\Theta(n\log n)$ | $\Theta(\log n)$ |

2、归并排序

基本思想

将原始序列划分为两个子序列，递归划分至不可再分；
最后将有序子序列合并（归并）为整体有序序列；
与快速排序的区别：快排侧重“分割”，归并排序侧重“归并”。

归并思想（示例）

原始序列：25 34 45 32 78 12 34' 64

先划分：递归拆分为单个元素 → (25)(34)(45)(32)(78)(12)(34')(64)；
再归并：逐步合并有序子序列 →
- 合并为(25 34)(32 45)(12 78)(34' 64)；
- 再合并为(25 32 34 45)(12 34' 64 78)；
- 最终合并为12 25 32 34 34' 45 64 78。

两路归并排序算法

template <class Record>
void MergeSort(Record Array[], Record TempArray[], int left, int right) {
    // Array为待排序列，left/right为两端
    int middle;
    if (left < right) {
        middle = (left + right) / 2; // 划分为两个子序列
        MergeSort(Array, TempArray, left, middle);   // 递归左子序列
        MergeSort(Array, TempArray, middle+1, right); // 递归右子序列
        Merge(Array, TempArray, left, right, middle); // 归并
    }
}

template <class Record>
void Merge(Record Array[], Record TempArray[], int left, int right, int middle) {
    int i, j, index1, index2;
    // 数组暂存到临时数组
    for (j = left; j <= right; j++)
        TempArray[j] = Array[j];
    index1 = left;       // 左子序列起始
    index2 = middle + 1; // 右子序列起始
    i = left;            // 归并起始位置
    
    // 合并两个有序子序列
    while (index1 <= middle && index2 <= right) {
        // 相等时选左，保证稳定性
        if (TempArray[index1] <= TempArray[index2])
            Array[i++] = TempArray[index1++];
        else
            Array[i++] = TempArray[index2++];
    }
    // 复制剩余左子序列
    while (index1 <= middle)
        Array[i++] = TempArray[index1++];
    // 复制剩余右子序列
    while (index2 <= right)
        Array[i++] = TempArray[index2++];
}

性能分析

时间复杂度：$\Theta(n\log n)$（每趟归并$\Theta(n)$，共$\lceil\log n\rceil$趟）；
空间复杂度：$\Theta(n)$（需额外临时数组）；
稳定性：稳定排序算法。

8.5 堆排序

基本概念

堆的分类：
- 最小堆：$K_i ≤ K_{2i+1}$ 且 $K_i ≤ K_{2i+2}$；
- 最大堆：$K_i ≥ K_{2i+1}$ 且 $K_i ≥ K_{2i+2}$（$i=0,…,\lfloor n/2 \rfloor-1$）；
堆的表示：用完全二叉树表示，$K_{2i+1}$是$K_i$的左孩子，$K_{2i+2}$是右孩子。

基本思想

对所有记录建立最大堆（时间$\Theta(n)$）；
取出堆顶最大记录，移到数组末端；对剩余$n-1$个记录重建最大堆（时间$\Theta(\log n)$），重复此操作直到堆空；
最终数组按从小到大排序。

排序过程示例（原始序列：`49,25,21,25*,16,08`）

初始最大堆：[49,25,21,25*,16,08]；
交换堆顶49与末尾08 → 序列[08,25,21,25*,16,49]，重建前5个元素为最大堆 → [25,25*,21,08,16,49]；
交换堆顶25与倒数第2位16 → 序列[16,25*,21,08,25,49]，重建前4个元素为最大堆 → [21,25*,16,08,25,49]；
重复交换+重建，最终结果：[08,16,21,25,25*,49]。

堆排序算法

template <class Record>
void sort(Record Array[], int n) {
    int i;
    MaxHeap<Record> max_heap = MaxHeap<Record>(Array, n); // 建堆
    // 依次取出堆顶最大记录
    for (i = 0; i < n; ++i)
        max_heap.RemoveMax();
}

算法分析

时间复杂度：建堆$\Theta(n)$，每次重建堆$\Theta(\log n)$，总时间$\Theta(n\log n)$（最佳/最差/平均均为此复杂度）；
空间复杂度：$\Theta(1)$；
稳定性：不稳定排序算法。

8.6 分配排序

核心特点

非基于“比较&交换”，而是通过“分配&收集”实现；
前提：需预先知道待排序列的部分属性（如关键字范围）。

1. 桶排序

基本思想

待排记录关键字范围为[0, m)，设m个桶；
将关键字为k的记录分到第k个桶；
按桶号依次收集记录，得到有序序列。

排序过程示例（待排数组：`7,3,8,9,6,8,1,2`）

初始化count数组（桶计数）为全0；
统计每个关键字出现次数：count[7]=1, count[3]=1, count[8]=2, count[9]=1, count[6]=1, count[1]=1, count[2]=1；
计算桶的后继起始下标（累计计数）；
按后继下标将记录分配到对应桶，再依次收集 → 结果：1,2,3,6,7,8,8,9。

桶排序算法

template <class Record>
void BucketSort(Record Array[], int n, int m) {
    Record *TempArray = new Record[n]; // 临时数组
    int *count = new int[m+1];         // 计数数组
    // 计数数组初始化
    for (int i=0; i<=m; i++) count[i] = 0;
    // 统计每个关键字出现次数
    for (int i=0; i<n; i++) count[Array[i]]++;
    // 计算后继起始下标
    for (int i=1; i<=m; i++) count[i] += count[i-1];
    // 分配记录到临时数组（保证稳定性）
    for (int i=n-1; i>=0; i--) 
        TempArray[--count[Array[i]]] = Array[i];
    // 复制回原数组
    for (int i=0; i<n; i++) Array[i] = TempArray[i];
    delete []TempArray;
    delete []count;
}

算法分析

时间代价：统计$\Theta(n)$、分配$\Theta(n)$、收集$\Theta(m)$，总$\Theta(n+m)$；
空间代价：$\Theta(n+m)$（临时数组+计数数组）；
适用场景：关键字范围m远小于n的情况；
稳定性：稳定排序。

2. 基数排序

基本思想

将记录按关键字的位（如个位、十位） 分组，每位作为一个“基数”；
按位依次排序（从低位/高位开始），最终得到有序序列。

基于数组的基数排序（LSD）

以关键字为2位十进制数为例，步骤：

按个位进行桶排序；
按十位进行桶排序；
收集后得到有序序列。

基于链表的基数排序（LSD）

用链表存储记录，避免数组的大量移动操作，步骤与数组版一致，但通过链表的插入/删除实现“分配&收集”。

算法分析

时间代价：设关键字有d位，每位基数为r，总时间$\Theta(d(n+r))$；
空间代价：$\Theta(n+r)$；
稳定性：稳定排序。

8.7 索引排序

核心概念

当记录规模很大时，减少记录移动次数能有效降低排序时间。

索引排序（地址排序）：让数组中每个单元存储对应记录的地址，移动记录时仅移动地址（索引），不移动记录本身。

两种索引形式

IndexArray1（“我到哪里去？”）：
- 对原数组Array而言，IndexArray1[i]存储Array[i]在排序后序列中的位置，即：SortedArray[IndexArray1[i]] = Array[i]。
IndexArray2（“我从哪里来？”）：
- 对排序后数组SortedArray而言，IndexArray2[j]存储SortedArray[j]在排序前序列中的位置，即：SortedArray[j] = Array[IndexArray2[j]]。

索引排序的两个关键问题

索引排序（index sort）：生成索引数组的过程；
物理排序（Array Sort）：根据索引数组调整原数组，得到物理有序的序列。

索引排序示例

以Array和Index数组为例：

原数组Array（每个元素含两个值）：[ (2,9), (2,5), (3,4), (6,4), (3,4), (1,2), (3,2), (4,5) ]
索引数组Index：[5, 1, 0, 6, 2, 4, 7, 3]
排序后数组SortedArray：通过Index映射得到有序序列。

排序过程分析

排序过程包含多个环（Cycle），每个环中拷贝操作的数目为环长度+1。

索引排序算法

template<class Record>
void IndeSort(Record Array[], int IndexArray[], int n) {
    int i;
    for (i=0; i<n; ++i) IndexArray[i] = i; // 初始化索引下标
    // 简单插入排序的索引排序过程
    for (i=1; i<n; ++i) { // 依次插入第i个记录
        for (int j=i; j>0; --j) {
            // 发现逆序就交换索引
            if (Array[IndexArray[j]] < Array[IndexArray[j-1]])
                swap(IndexArray,j,j-1);
            else break; // 前面记录已排序
        }
    }
    AdjustRecord(Array, IndexArray, n); // 调整记录
}

记录物理调整（根据索引数组调整原数组）

template<class Record>
void AdjustRecord(Record Array[], int IndexArray[], int n) {
    Record TempRec; // 临时空间
    int i, j;
    for (i=0; i<n; ++i) {
        j = i; // 当前环中的当前元素
        TempRec = Array[j]; // 暂存下标j中的当前记录
        while (IndexArray[j] != i) { // 下标不是目的则调整
            int k = IndexArray[j]; // 取下标j指向的下标
            Array[j] = Array[k]; // 把k中值复制到j
            IndexArray[j] = j; // 正确归位，索引是自身
            j = k; // 跳到环的下一个元素
        }
        Array[j] = TempRec; // 第i个元素正确入位
        IndexArray[j] = j; // 正确归位，索引是自身
    }
}

调整算法中，每个元素最多参与一轮调整，时间代价$\Theta(n)$，空间代价$\Theta(1)$。

8.8 各种排序算法的理论和实验时间代价

理论时间代价对比

算法	最大时间	平均时间	最小时间	辅助空间代价	稳定性
直接插入排序	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n)$	$\Theta(1)$	稳定
二分插入排序	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n\log n)$	$\Theta(1)$	稳定
冒泡排序	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(1)$	稳定
改进的冒泡排序	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n)$	$\Theta(1)$	稳定
选择排序	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(1)$	不稳定
Shell排序(2)	$\Theta(n^2)$	$\Theta(n^{3/2})$	$\Theta(n^{3/2})$	$\Theta(1)$	不稳定
Shell排序(3)	$\Theta(n^{3/2})$	$\Theta(n^{3/2})$	$\Theta(n^{3/2})$	$\Theta(1)$	不稳定
快速排序	$\Theta(n^2)$	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(\log n)$	不稳定
归并排序	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n)$	稳定
堆排序	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(1)$	不稳定
桶排序	$\Theta(n+m)$	$\Theta(n+m)$	$\Theta(n+m)$	$\Theta(n+m)$	稳定
基数排序	$\Theta(d(n+r))$	$\Theta(d(n+r))$	$\Theta(d(n+r))$	$\Theta(n+r)$	稳定

8.9 排序问题的界

上下界定义

下界（Lower Bound）：解决排序问题能达到的最佳效率（即使尚未设计出算法）。
上界（Upper Bound）：已知算法所达到的最佳效率。

排序问题的下界在$\Omega(n)$到$\Omega(n\log n)$之间。

判定树模型（基于比较的排序）

判定树的深度是排序算法在最差情况下需要的比较次数；
最小深度是最佳情况下的最少比较次数。

对$n$个记录，共有$n!$个叶结点，判定树的深度为$\log_2(n!)$，因此基于比较的排序算法最差情况需$\Omega(n\log n)$次比较。

第八章 内排序

8.1 基本概念

排序定义

8.2 三种O（n^2）的简单排序

插入排序

优化的插入排序算法

基于二分查找的插入排序

冒泡排序

优化的冒泡排序

直接选择排序

8.3 Shell排序

核心思路（利用上述性质）

具体实现方法

Shell排序过程

算法代码（delta=2版本）

分析

8.4 基于分治法的排序

快速排序（C.A.R.Hoare，1962）

分治思想

算法代码

关键问题

排序过程示例

算法分析

2、归并排序

基本思想

归并思想（示例）

两路归并排序算法

性能分析

8.5 堆排序

基本概念

基本思想

排序过程示例（原始序列：49,25,21,25*,16,08）

堆排序算法

算法分析

8.6 分配排序

核心特点

1. 桶排序

基本思想

排序过程示例（待排数组：7,3,8,9,6,8,1,2）

桶排序算法

算法分析

2. 基数排序

基本思想

分类

基于数组的基数排序（LSD）

基于链表的基数排序（LSD）

算法分析

8.7 索引排序

核心概念

两种索引形式

索引排序的两个关键问题

索引排序示例

排序过程分析

索引排序算法

记录物理调整（根据索引数组调整原数组）

8.8 各种排序算法的理论和实验时间代价

理论时间代价对比

8.9 排序问题的界

上下界定义

判定树模型（基于比较的排序）

第八章内排序

排序过程示例（原始序列：`49,25,21,25*,16,08`）

排序过程示例（待排数组：`7,3,8,9,6,8,1,2`）