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

• 排序主要分为两类：内排序和外排序：

  1. 内排序：待排序的记录个数较少，整个排序过程中所有的记录都可以直接存放在内存中
  2. 外排序：待排序的记录数量太大，内存无法容纳所有记录，在排序过程中还需要访问外存

• 基于比较的排序方式，时间代价为O(nlogn)

排序问题的基本概念

• 排序码 (Sort Key)：作为排序运算依据的一个或多个域

• 记录或元素 (Record)：结点，进行排序的基本单位

• 序列 (Sequence)：线性表，由记录组成

• 关键码 (Key)：唯一确定记录的一个或多个域，有人翻译为“键”

• 排序码不一定是关键码，关键码是唯一确定记录的一个域或多个域

• 排序：将序列中的记录按照排序码顺序排列起来的过程。其中，排序码域的值具有不减（或不增）的顺序。如果排序码不重复，则递增或递减

• 排序问题：

  1. 给定一个序列 R = { r0, r1, …，rn-1 }，其排序码分别为 k = { k0, k1, …，kn-1 }
  2. 排序的目的：将记录按排序码重排。形成新的有序序列 R’= { r’0, r’1, …，r’n-1 }。相应排序码为 k’= { k’0, k’1, …，k’n-1 }
  3. 其中 k’0 ≤ k’1 ≤ … ≤ k’n-1，称为不减序(不取等为升序)； k’0 ≥ k’1 ≥ … ≥ k’n-1 ，称为不增序(不取等为降序)

• 正序 vs. 逆序

  1. “正序”序列 ：待排序序列正好符合排序要求
  2. “逆序”序列 ：把待排序序列逆转过来，正好符合排序要求

• 排序的稳定性：存在多个具有相同排序码的记录，排序后这些记录的相对次序保持不变

• 排序算法的衡量标准：
  1. 时间代价：记录的比较和移动次数
  2. 算法本身的繁杂程度

插入排序 ( Shell 排序)

• 插入排序的算法思想：对待排元素逐个处理，对每个新纪录与同组的那些已经排好的记录进行比较，然后插入到适当的位置。重点在于找到序列中插入的位置以及如何移动序列中那些已经排好的元素

直接插入排序

• 线性搜索确定待插入记录的位置

• 思想：按照从大到小(或从小到大)依次逐个与新纪录进行比较，直到找到第一个不大于新记录的值，这就是新记录插入的位置。依次把新记录插入到逐步扩大的已排序子序列中直到最后完全排序

// 直接插入排序算法
template <class Record>
void ImprovedInsertSort (Record Array[], int n)
{
    //Array[] 为待排序数组，n 为数组长度
    Record TempRecord; // 临时变量
    for (int i=1; i<n; i++)
    {   // 依次插入第 i 个记录
        TempRecord = Array[i];
        //从 i 开始往前寻找记录 i 的正确位置
        int j = i-1;
        //将那些大于等于记录 i 的记录后移
        while ((j>=0) && (TempRecord < Array[j]))
        {
            Array[j+1] = Array[j];
            j = j - 1;
        }
        //此时 j 后面就是记录 i 的正确位置，回填
        Array[j+1] = TempRecord;
    }
}

• 直接插入排序算法是稳定的。如果前面有等于新记录的排序码值的记录，该记录仍然会在前面位置

• 算法分析：

  1. 空间代价：Θ(1)
  2. 时间代价：
     1. 最佳情况：n-1 次比较，2(n-1) 次移动，Θ(n)
     2. 最差情况： Θ(n²)
     3. 平均情况：Θ(n²)

Shell排序

• 直接插入排序的两个性质：

  1. 在最好情况（序列本身已是基本有序的）下时间代价为 Θ(n)
  2. 对于短序列，直接插入排序比较有效

• Shell 排序有效地利用了直接插入排序的这两个性质

• Shell排序算法思想：

  1. 先将序列转化为若干小序列，在这些小序列内进行插入排序
  2. 逐渐增加小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态
  3. 最后对整个序列进行扫尾直接插入排序，从而完成排序

• 例如n=8，增量每次除以2时具体的实现过程如下：

  1. 首先，将原始序列分为n/2=4个子序列，每个子序列包含两个记录，记录下标间距d=4(0和4,1和5……)，分别对4个子序列进行插入排序
  2. 再将序列分为n/4=2个子序列，每个子序列包含4个记录，记录下标间距d=2(0246和1357),然后分别对这两个子序列进行插入排序
  3. 最后对整个序列进行插入排序

// 增量每次除以2递减的Shell排序
template <class Record>
void ShellSort(Record Array[], int n) 
{
    // Shell排序，Array[]为待排序数组，n为数组长度
    int i, delta;
    // 增量delta每次除以2递减
    for (delta = n/2; delta>0; delta /= 2)
        for (i = 0; i < delta; i++)
        // 分别对delta个子序列进行插入排序
        //“&”传 Array[i]的地址，数组总长度为n-i
            ModInsSort(&Array[i], n-i, delta);
    // 如果增量序列不能保证最后一个delta间距为1
    // 可以安排下面这个扫尾性质的插入排序
    // ModInsSort(Array, n, 1);
}


template <class Record> // 参数delta表示当前的增量
void ModInsSort(Record Array[], int n, int delta) 
{
    int i, j;
    for (i = delta; i < n; i += delta) // 第i个记录找插入位置
        // j以dealta为步长向前寻找逆置对进行调整
        for (j = i; j >= delta; j -= delta) 
        {
            if (Array[j] < Array[j-delta]) // 逆置对
                swap(Array, j, j-delta); // 交换
            else break;
        }
}

• 增量每次除以2递减可以保证最后一次的间距为1，如果采用其他增量序列，一定注意人为的增加一个间距为1的增量元素

• Shell排序子序列互相交错，而且跨度很大，是一种不稳定的排序算法

• Shell 排序算法分析：

  1. 空间代价：Θ(1)
  2. 时间代价：
     1. 增量每次除以2递减，Θ(n²)
     2. 增量每次除以3递减 & Hibbard 增量序列，Θ(n ^(3/2))
     3. 甚至有的Shell排序的时间代价可以达到Θ(n ^(7/6))，接近Θ(nlogn)

选择排序

• 选择排序的算法思想：逐个找出第i小的元素，并将元素放到数组的第i个位置。重点在于如何在剩余的未排序的记录中找出最小(大)的记录

直接选择排序

• 算法思想：逐个找出第i小的记录，并将这个记录与数组的第i个位置的记录进行交换，第i小的记录一次交换到位

// 直接选择排序
template <class Record>
void SelectSort(Record Array[], int n) 
{
    // 依次选出第i小的记录，即剩余记录中最小的那个
    for (int i=0; i<n-1; i++) 
    {
        // 首先假设记录i就是最小的
        int Smallest = i;
        // 开始向后扫描所有剩余记录
        for (int j=i+1;j<n; j++)
            // 如果发现更小的记录，记录它的位置
            if (Array[j] < Array[Smallest])
                Smallest = j;
        // 将第i小的记录放在数组中第i个位置
        swap(Array, i, Smallest);
    }
}

• 直接选择排序是不稳定的

• 直接选择排序算法分析：
  1. 空间代价：Θ(1)
  2. 时间代价：
     1. 比较次数：Θ(n²)
     2. 交换次数：n-1
     3. 总时间代价：Θ(n²)

堆排序

• 直接选择排序的局限性：没有充分利用前一轮查询所能得到的信息

• 堆排序利用堆数据结构保持剩余记录相对大小的信息，因而是更有效的选择排序

• 如果从小到大排序，那么需要建立最大堆；如果从大到小排序，则要建立最小堆

• 最大堆：父结点中的数据项大于等于子结点中的数据项，因此最大堆的堆顶记录整个堆中的最大记录。而次大的记录则存放在堆顶的左右子结点中

• 堆排序的两个主要步骤：

  1. 对所有记录建立最大堆
  2. 取出堆顶的最大记录与数组末端的记录交换，最大记录放在下标n-1的位置，原数组末端元素临时处于根结点；将根元素向下调整到合适的位置，即剩下的n-1个记录重新调整为堆，再取新堆顶的最大记录，与数组n-2位交换…
  3. 不断重复这一操作直到堆为空。数组正好从小到大排序

• 堆排序是不稳定的，因为再建堆过程中，二叉树的父子节点之间的移动不能保证两个重复记录一定能够保持原始输入输出顺序

// 堆排序
template <class Record>
void sort(Record Array[], int n)
{
    int i;
    // 建堆
    MaxHeap<Record> max_heap= MaxHeap<Record>(Array,n,n);
    // 算法操作n-1次，最小元素不需要出堆
    for (i = 0; i < n-1; i++)
    // 依次找出剩余记录中的最大记录，即堆顶
        max_heap. RemoveMax();
}

• 堆排序算法分析：
  1. 空间代价：Θ(1)
  2. 时间代价：
     1. 建堆：Θ(n)
     2. 删除堆顶: Θ(log n )
     3. 一次建堆，n 次删除堆顶，总时间代价为 Θ(nlogn)

交换排序

• 交换排序的基本思想：两两比较待排序记录的关键码，发现记录逆置则进行交换，直到没有逆置为止

冒泡排序

• 冒泡排序的基本思想：不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。检查每轮冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排序结束

• 冒泡排序的流程：

  1. 从数组末端开始，不断比较相邻的元素，不满足排序要求的就交换。比较完一轮后最小的记录就已经被推到最左端r0的位置上
  2. 第二轮冒泡的过程只需要对rn-1到r1进行比较。第二轮冒泡完成后次小的记录就被推到r1
  3. 重复上述过程直到数组中所有的记录都已经排好位置

• 冒泡排序算法还可以按照不断找出第i大的记录来进行：即第一次冒泡找出最大的记录到数组最末端，第二次找出第二大的…

template <class Record>
void BubbleSort(Record Array[], int n) 
{
    bool NoSwap; // 是否发生了交换的标志
    int i, j;
    for (i = 0; i < n-1; i++) 
    {
        NoSwap = true; // 标志初始为真
        for (j = n-1; j > i; j--)
        {
            if (Array[j] < Array[j-1]) 
            { // 判断是否逆置
            swap(Array, j, j-1); // 交换逆置对
            NoSwap = false // 发生了交换，标志变为假
            }
        }
        if (NoSwap) // 没发生交换，则已排序
            return;
    }
}

• 冒泡排序是稳定的

• 冒泡排序算法分析：
  1. 空间代价：Θ(1)
  2. 时间代价：
     1. 最小时间代价为 Θ(n)：最佳情况下只运行第一轮循环
     2. 最大，平均时间代价均为 Θ(n²)

快速排序

• 快速排序基于分治法的排序算法

• 分治法的关键是“分、治、合”：

  1. 分：将给定的问题分成若干个子问题
  2. 治：再对每个子问题求解
  3. 合：最后将所有子问题的解合并成一个综合的解

• 快速排序几乎是最快的排序算法，平均时间代价为Θ(nlog n)

• 快速排序的算法思想：

  1. 从待排序列中任意选择一个记录轴值(pivot)
  2. 将序列划分为两个子序列 L 和 R，使得 L 中所有记录都小于或等于轴值，R 中记录都大于轴值
  3. 对子序列 L 和 R 递归进行快速排序，直到子序列中只含有1个或0个元素，退出递归

• 下图为快速排序的例子，其中方框圈起来的为轴值

• 轴值的选择对快速排序的时间性能影响很大，轴值的选择应该尽量使得序列可以划分为均匀的两半

• 可以选择中间点(start + end) 作为轴值，这种轴值在输入数据位正序或逆序的时候可以平分序列，效果很好

• 分割过程：

  1. 选择轴值并存储轴值
  2. 最后一个元素放到轴值位置
  3. 初始化下标 l, r，分别指向头尾
  4. i 递增直到遇到比轴值大的元素，将此元素覆盖到 j 的位置；j 递减直到遇到比轴值小的元素，将此元素覆盖到 i 的位置
  5. 重复上一步直到 l==r，将轴值放到 i 的位置，完毕

• 改进方法：从序列两端交替检查空闲位置，将逆置记录移动到空闲位置上，而不是直接交换逆置记录。不同的分割方法分出来的子序列不同

• 分割完毕后分别对左边和右边的子序列进行快速排序

// 快速排序
template <class Record>
void QuickSort(Record Array[], int left, int right) 
{
    // Array[]为待排序数组，left,right分别为数组两端
    if (right <= left) // 只有0或1个记录，就不需排序
        return;
    int pivot = SelectPivot(left, right); // 选择轴值
    swap(Array, pivot, right); // 轴值放到数组末端
    pivot = Partition(Array, left, right); // 分割后轴值正确
    QuickSort(Array, left, pivot-1); // 左子序列递归快排
    QuickSort(Array, pivot +1, right); // 右子序列递归快排
}

int SelectPivot(int left, int right) 
{
    // 选择轴值，参数left,right分别表示序列的左右端下标
    return (left+right)/2; // 选中间记录作为轴值
}

template <class Record>
int Partition(Record Array[], int left, int right) 
{
    // 分割函数，分割后轴值已到达正确位置
    int l = left; // l 为左指针
    int r = right; // r 为右指针
    Record TempRecord = Array[r]; // 保存轴值
    while (l != r) 
    { // l, r 不断向中间移动，直到相遇
        // l 指针向右移动，直到找到一个大于轴值的记录
        while (Array[l] <= TempRecord && r > l)
            l++;
        if (l < r) 
        { // 未相遇，将逆置元素换到右边空位
            Array[r] = Array[l];
            r--; // r 指针向左移动一步
        }
        // r 指针向左移动，直到找到一个小于轴值的记录
        while (Array[r] >= TempRecord && r > l)
            r--;
        if (l < r) 
        { // 未相遇，将逆置元素换到左空位
            Array[l] = Array[r];
            l++; // l 指针向右移动一步
        }
    } //end while
    Array[l] = TempRecord;// 把轴值回填到分界位置 l 上
    return l; // 返回分界位置l
}

• 快速排序不稳定

• 快速排序的比较次数比移动次数要多得多，因此主要考虑比较次数。由于快速排序是递归排序，因此可以递归推理计算时间代价：其中cn为轴值选择的时间

• 快速排序算法代价分析：

  1. 空间代价：
     1. 平均空间代价为Θ(nlog n)
     2. 空间代价： O(n)
  2. 时间代价：
     1. 最佳情况时间代价：Θ(nlog n)
     2. 最差情况时间代价：Θ(n²)
     3. 平均情况时间代价：Θ(nlog n)

• 随机化的快速排序(RQS)的主要思想：随机的选择一个数作为轴值，平均复杂度仍为Θ(nlog n)

• Median-of-3 partition：随机找出3个元素，并取其中间的元素作为轴值

• 改进：当快速排序的子数组小于某个长度时，不必继续递归。虽然子数组中的数值是无序的，但是整块看待这些子数组，可以发现一块块地有序，即左边的数组排序码都要小于右边数组的排序码。此时正适合使用插入排序

归并排序

• 归并排序简单的将原始的序列划分为两个子序列，然后分别对每个子序列递归排序，最后再将有序子序列合并

• 归并排序的主要步骤为：

  1. 划分为两个子序列
  2. 对每个子序列分别进行归并排序
  3. 有序子序列合并

• 归并排序也是一种基于分治法的排序。快速排序侧重于“分”，没有明显的“合”，而归并排序的“分”很简单，侧重于“治”和“合”

• 归并的过程：

  1. 每次比较序列头，取出较小的进入结果序列中
  2. 随后次小的记录顶上来，继续比较两个子序列头，取出较小的进入结果序列
  3. 重复上述过程直到其中一个子序列为空，此时剩余子序列中的记录可以直接进入结果序列

// 两路归并排序
template <class Record>
void MergeSort(Record Array[], Record TempArray[], int left,int right) 
{
    // Array为待排序数组，left，right两端
    int middle;
    if (left < right) 
    { // 序列中只有0或1个记录，不用排序
        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++];
}

• 归并排序是稳定的

• 归并排序算法算法复杂度分析：

  1. 空间代价：Θ(n)
  2. 时间代价：最大、最小以及平均时间代价均为 Θ(nlog n)

• 优化归并排序方法：R.Sedgewick 优化：先把右子序列置逆，归并时从两端开始处理，向中间推进，简化边界判断；同优化的快速排序一样，对基本已排序序列直接插入排序

template <class Record>
void ModMergeSort(Record Array[], Record TempArray[], int left, int right) 
{
    // Array为待排序数组，left，right两端
    int middle;
    if (right-left+1 > THRESHOLD) 
    { // 长序列递归
        middle = (left + right) / 2; // 从中间划为两个子序列
        ModMergeSort(Array, TempArray ,left,middle); // 左
        ModMergeSort(Array, TempArray ,middle+1,right);// 右
        // 对相邻的有序序列进行归并
        ModMerge(Array, TempArray ,left,right,middle); // 归并
    }
    else InsertSort(&Array[left],right-left+1); // 小序列插入排序
}

template <class Record> void ModMerge(Record Array[],Record 
TempArray[],int left,int right,int middle) 
{
    int index1,index2; // 两个子序列的起始位置
    int i,j,k ;
    for (i = left; i <= middle; i++)
        TempArray[i] = Array[i]; // 复制左边的子序列
    for (j = 1; j <= right-middle; j++) // 颠倒复制右序列
        TempArray[right-j+1] = Array[j+middle];
    for (index1=left, index2=right, k=left; k<=right; k++)
        if (TempArray[index1] <= TempArray[index2])
            Array[k] = TempArray[index1++];
        else
            Array[k] = TempArray[index2--];
}

• 优化后的归并排序依然是稳定的

• 优化后的算法时空代价相同

分配排序和索引排序

• 分配排序不需要进行关键码之间的比较，但是需要事先知道记录序列的一些具体情况

• 如果事先知道序列中记录的排序码都位于某个小区间内，就可以使用桶式排序

• 当排序码值域m很大时，可以拆分为多个部分进行比较，这就是基于桶式排序的基数排序

• 为减少记录的移动，可以采取基于静态联的基数排序，这本质上是一种索引排序(地址排序)

桶式排序

• 桶式排序是一种简单的分配排序。记录都位于某小区间段 [0, m) 内，分配到各桶，再收集

• 假如知道长度为n的序列中的所有记录的值都在0m-1间，可以用一个长度为n的辅助数组，还需要m个计数器统计0m-1出现的次数，将具有想通知的记录都分配到一个桶中，然后依次按编号从桶中取出记录，责成有序序列

• 桶式排序的流程：

  1. 扫描一遍序列，统计处0~m-1这m个数的出现次数，放到count数组中
  2. 根据count[i] += count[i-1]计算出元素i的结束位置，即元素i应该从array[count[i]-1]往前追溯，存放count[i] - count[i-1]个
  3. 最终，输出排序结果应该从初始序列的尾部开始往前扫描，以保证算法的稳定性

// 桶式排序
template <class Record> void BucketSort(Record Array[], int n, int max) 
{
    Record *TempArray = new Record[n]; // 临时数组
    int *count = new int[max]; // 桶容量计数器
    int i;
    for (i = 0; i < n; i++) // 把序列复制到临时数组
        TempArray[i] = Array[i];
    for (i = 0; i < max; i++) // 所有计数器初始都为0
        count[i] = 0;
    for (i = 0; i < n; i++) // 统计每个取值出现的次数
        count[Array[i]]++;
    for (i = 1; i < max; i++) // 统计小于等于i的元素个数
        count[i] = count[i-1]+count [i]; // c [i]记录i+1的起址
    for (i = n-1; i >= 0; i--) // 尾部开始，保证稳定性
        Array[--count[TempArray[i]]] = TempArray[i];
}

• 桶式排序具有稳定性

• 桶式排序算法分析：数组长度为 n, 所有记录区间 [0, m) 上

  1. 空间复杂度：长度为 n 的临时数组，m 个计数器， Θ(n+m)
  2. 时间复杂度：总的时间代价为 Θ(n+m)

• 桶式排序适用于m很小的情况

基数排序

• 基数排序： 当 m 很大时，可以将一个记录的值即排序码拆分为多个部分来进行比较。基数排序是将排序码按照其进制的基数进行拆分的排序

• 假设长度为 n 的序列R = { r0，r1，…，rn-1}记录的排序码 K 包含 d 个子排序码K = ( kd-1，kd-2，…，k1，k0)

• R 对排序码有序，即对于任意两个记录 R i，R j(0 ≤ i< j ≤ n-1)，都满足(k i ,d-1，k i ,d-2， …，k i ,1，k i,0 ) ≤ (k j ,d-1，k j, d-2，…，k j,1，k j,0 )

• 按照排序码的先后顺序，分配排序可以分成两种：高位优先法和低位优先法

  1. 高位优先法(MSD)：分、分、…、分、收 的过程
     1. 先处理最高位 kd-1 将序列分到若干桶中
     2. 然后再对每个桶处理次高位 kd-2 ，分成更小的桶
     3. 依次重复，直到对 k0 排序后，分成最小的桶，每个桶内含有相同排序码 (kd-1，…，k1，k0)
     4. 最后将所有的桶中的数据依次连接在一起，成为一个有序序列
  2. 低位优先法(LSD)：分、收；分、收；…；分、收的过程
     1. 从最低位 k0 开始排序
     2. 对于排好的序列再用次低位 k1 排序
     3. 依次重复，直至对最高位 kd-1 排好序后，整个序列成为有序的

• 计算机常用LSD分配排序，因为速度快便于统一处理

• 具体实现基数排序的时候，数据项的存储方式可以分为：

  1. 顺序存储
  2. 链式存储

顺序存储

• 原始输入数组 R 的长度为 n，基数为 r，排序码个数为 d。排序可以通过调用d次桶式排序来实现

// 基于数组的基数排序
template <class Record>
void RadixSort(Record Array[], int n, int d, int r) 
{
    Record *TempArray = new Record[n];
    int *count = new int[r]; int i, j, k;
    int Radix = 1; // 模进位，用于取Array[j]的第i位
    for (i = 0; i <= d-1; i++) 
    { // 对第 i 个排序码分配
        for (j = 0; j < r; j++)
            count[j] = 0; // 初始计数器均为0
        for (j = 0; j < n; j++) 
        {   // 统计每桶记录数
            k = (Array[j] / Radix) % r; // 取第i位
            count[k]++; // 相应计数器加1
        }
        for (j = 1; j < r; j++) // 给桶划分下标界
        count[j] = count[j-1] + count[j]; // count[i]记录了i+1桶的开始位置
        for (j = n-1; j >= 0; j--) 
        {   // 从数组尾部收集
            k = (Array[j] / Radix ) % r; // 取第 i 位
            count[k]--; // 桶剩余量计数器减1
            TempArray[count[k]] = Array[j]; // 入桶
        }
        for (j = 0; j < n; j++) // 内容复制回 Array 中
            Array[j] = TempArray[j];
        Radix *= r; // 修改模Radix
    }
}

• 顺序基数排序的算法分析：
  1. 空间代价：总空间代价 Θ(n+r)
  2. 时间代价：总时间代价 Θ(d·(n+r))

链式存储(静态链)

• 顺序存储的局限性：

  1. 由于桶中的记录个数未定，因此空间代价高
  2. 分配收集都需要移动所有记录，导致时间代价也较高

• 链式存储的思想：给每个记录设置整数next域，指向同一个桶中下一个元素的下标，r个桶组成r个静态队列：

  1. LSD分配第i位时，按照某记录的排序码i位的值分配到相应的队列，实际上只需要修改该记录的next域
  2. 收集时，只需要利用next域依次把各队首尾相连

// 静态队列定义
template<class T>
class Node 
{   // 结点类
    public:
        int key; // 结点的排序码值
        int next; // 下一个结点在数组中的下标
        // T value; 属性域
};
class StaticQueue 
{   // 静态队列类
    public:
        int head;
        int tail;
};

// 基于静态链的基数排序
template <class Record>
void RadixSort(Record *Array, int n, int d, int r) 
{
    int i, first = 0; // first指向第一个记录
    StaticQueue *queue = new StaticQueue[r];
    for (i = 0; i < n-1; i++)
        Array[i].next = i + 1; // 初始化静态指针域
    Array[n-1].next = -1; // 链尾next为空
    // 对第i个排序码进行分配和收集，一共d趟
    for (i = 0; i < d; i++) 
    {
        Distribute(Array, first, i, r, queue);
        Collect(Array, first, r, queue);
    }
    delete[] queue;
    AddrSort(Array, n, first); // 整理后，按下标有序
}

// 分配过程
template <class Record>
void Distribute(Record *Array, int first, int i, int r, StaticQueue *queue) 
{
    int j, k, a, curr = first;
    for (j = 0; j < r; j++) 
        queue[j].head = -1;
    while (curr != -1) 
    { // 对整个静态链进行分配
        k = Array[curr].key;
        for (a = 0; a < i; a++) // 取第i位排序码数字k
            k = k / r;
        k = k % r;
        if (queue[k].head == -1) // 把数据分配到第k个桶中
            queue[k].head = curr;
        else 
            Array[queue[k].tail].next = curr;
        queue[k].tail = curr;
        curr = Array[curr].next; // curr移动，继续分配
    }
}

// 收集过程
template <class Record>
void Collect(Record *Array, int& first, int r, StaticQueue *queue) 
{
    int last, k=0; // 已收集到的最后一个记录
    while (queue[k].head == -1) 
        k++; // 找到第一个非空队
    first = queue[k].head; last = queue[k].tail;
    while (k < r-1) 
    {   // 继续收集下一个非空队列
        k++;
        while (k < r-1 && queue[k].head == -1)
            k++;
        if (queue[k].head != -1) 
        {   // 试探下一个队列
            Array[last].next = queue[k].head;
            last = queue[k].tail; // 最后一个为序列的尾部
        }
    }
    Array[last].next = -1; // 收集完毕
}

• 链式存储基数排序的算法分析：
  1. 空间复杂度：总空间代价 Θ(n + r)
  2. 时间复杂度：总时间代价 Θ(d·(n+r))

索引排序

• 让数组中的每一个元素存储指向该元素记录的指针，在需要移动记录 时，只移动指针值(索引地址)而不一定记录本身。这种排序称为“索引排序”或“地址排序”

• 可以看到下图中原始待排数组尚未整理，记录的序被保持在索引数组中。排序后需要根据辅助的索引数组来调整原始的待排数组，使其按照下标有序的存放记录，可以在O(n)时间内完成

• 可以观察到下标0应该放入目前下标5的排序码12，(5,12) -> (0,12)

• 索引排序算法的核心排序算法是直接插入排序。从0~n-1扫描数组，如果索引值与当前位置不符合，就顺着索引链进行循环调整，直到找到等于当前下标的索引位置为止

// 插入排序的索引地址排序版本
template<class Record>
void AddrSort(Record Array[], int n) 
{
    // n为数组长度
    int *IndexArray = new int[n], TempIndex;
    int i,j,k;
    Record TempRec; // 只需一个临时空间
    for (i=0; i<n; i++)
        IndexArray[i] = i;
    for (i=1; i<n; i++) // 依次插入第i个记录
        for (j=i; j>0; j--) // 依次比较，发现逆置就交换
            if ( Array[IndexArray[j]] <Array[IndexArray[j-1]]))
                swap(IndexArray, j, j-1);
            else break; //此时i前面记录已排序
    // 调整为按下标有序
    for(i=0;i<n;i++) 
    {
        j= i;
        TempRec = Array[i];
        while (IndexArray[j] != i) 
        {
            k=IndexArray[j];
            Array[j]=Array[k];
            IndexArray[j] = j;
            j = k;
        }
        Array[j] =TempRec;
        IndexArray[j] = j;
    }
}

• 索引排序的时间代价：Θ(𝒏)

排序算法的时间代价

简单排序算法的时间代价

• 直接插入、直接选择和冒泡这三种排序方法思想简单而容易实现。但是时间代价都很大，时间代价为Θ(𝒏²)

• 关键原因：共同缺点为只对相邻的两个记录进行比较和移动，记录只能一步步的向目标位置移动，效率低下。而直接选择排序则是逐个进行线性比较，效率同样不高

• 一个长度为 n 的序列平均有n(n-1)/4 个逆置对。任何一种基于相邻记录比较的排序算法的平均时间代价都是 Θ(n²)

• n 很小或基本有序时插入排序比较有效

排序算法的理论和实验时间

• 实验：利用随机函数生成一个长度为n的整形数据。用若干个随机数据来测试，取平均时间

// 随机生成待排序数组
inline void Randomize() 
{ // 设置随机种子
    srand(1);
}
// 返回一个[0,n-1]之间的随机整数值
inline int Random(int n) 
{
    return rand() % (n);
}
// 产生随机数组
// 不能用申请静态数组ELEM sortarray[1000000];
ELEM *sortarray =new ELEM[1000000];
for(int i=0; i<1000000; i++)
    sortarray[i] = Random(32003);

// 时间测试
#include <time.h>
#define CLOCKS_PER_SEC 1000
clock_t tstart = 0; // 开始的时间
// 初始化计时器
void Settime() 
{
    tstart = clock();
}
// 上次 Settime() 之后经过的时间
double Gettime() 
{
    return (double)((double)clock() -(double)tstart) / (double)CLOCKS_PER_SEC;
}

// 排序的时间测试
Settime();
for (i=0; i<ARRAYSIZE; i+=listsize) 
{
    sort<int>(&array[i], listsize);
}
cout << "Sort with list size " << listsize<< ", array size " << ARRAYSIZE << ", and threshold " <<THRESHOLD << ": " << Gettime() << " seconds\n";

排序问题的下限

• 排序问题的下限：解决排序问题所能达到的最佳可能效率

• 任何算法的时间都不可能小于I/O时间，因此没有哪种算法能够将时间下限降到Ω(n)一下，排序问题的时间代价在 Ω(n) (单趟扫描) 到O(n log n) (平均, 最差情况) 之间

• 二叉判定树：

  1. 每个结点列举当前状态下可能得排列集合
  2. 边表示记录之间的比较，即一个判断
  3. 每个叶结点为一种排列情况，因此一共有n!个结点

• 对 n 个记录，共有 n! 个叶结点，树的层数至少为 Ω (log n!)。Ω (log(n!)) 在 Ω(n·logn) 中：在最差情况下任何基于比较的排序算法都至少需要 Ω(nlog n) 次比较而排序问题的上限是 O（nlogn）

• 因此可以推导出排序问题的时间代价为Θ (n·log n)

---