[数据结构与算法]“排序”学习提纲

前言

“排序”学习提纲。

代码模板

• 排序的C++语言描述实现模板

排序的基本概念

相关概念

• 排序：关键字无序序列排列成有序序列的过程

关键字可以是主关键字、次关键字和关键字组合等

多关键字可以转换为单关键字

• 稳定性：排序前后，两个或两个以上相同的关键字，相对位置没有变化，称算法是稳定的，反之是不稳定的

若关键字无重复，则排序结果唯一
若关键字有重复，则排序结果不唯一，需要考虑算法的稳定性

判断方式：
若存在相邻地比较和移动/交换关键字，则是稳定的
若存在跳跃地比较和移动/交换关键字，则是不稳定的

类型（依据思想）

• 插入类排序
• 交换类排序
• 选择类排序
• 归并类排序
• 基数类排序

插入类排序：

• 直接插入排序
• 折半插入排序
• 希尔排序

交换类排序：

• 冒泡排序
• 快速排序

选择类排序：

• 简单选择排序
• 堆排序

归并类排序：

• 二路归并排序

基数类排序：

• 基数排序

类型（依据复杂度）

• 简单排序
• 复杂排序

简单排序：

• 直接插入排序
• 冒泡排序
• 简单选择排序

复杂排序：

• 希尔排序
• 快速排序
• 堆排序
• 归并排序

类型（依据数据是否完全在内存中）

• 内部排序（是）
• 外部排序（否）

内部排序：

• 插入类排序
• 交换类排序
• 选择类排序
• 归并类排序
• 基数类排序

基本操作

• 比较
• 移动

注意：基数类排序基于多关键字比较

时间复杂度->比较和移动的次数

插入类排序

直接插入排序

//直接插入排序
//时间复杂度：O(n2)。n为数据规模
//时间复杂度：数据规模×比较次数
//最好：O(n)。n为数据规模。（有序）
//平均：O(n2)。n为数据规模
//最坏：O(n2)。n为数据规模。（无序的逆序）
//空间复杂度：O(1)。未使用额外辅助空间
//稳定性：稳定
void insertSort(vector<ELEM_TYPE> &elems) //参数：需排序元素的向量
{
    int i = 0; //循环变量
    int j = 0;
    int temp = 0; //需排序元素

    //第一个元素values[0]前无元素，不需要排序
    //从第二个元素values[1]开始遍历，需要排序
    for (i = 1; i < elems.size(); ++i)
    {
        temp = elems[i]; //记录需排序元素
        //需排序元素前的元素向后移动时，会覆盖需排序元素

        //遍历需排序元素前的元素
        //比较需排序元素和需排序元素前的元素
        for (j = i - 1; j >= 0; --j)
        {
            if (temp < elems[j]) //需排序元素<需排序元素前的元素   1.比较   <：稳定性体现
            {
                elems[j + 1] = elems[j]; //需排序元素前的元素向后移动 2.移动
            }
            else //>=
            {
                break;
            }
        }

        //遍历需排序元素前的元素结束时：需排序元素>=需排序元素前的元素    有插入位置
        elems[j + 1] = temp; //插入
    }

    return;
}

折半插入排序

//折半插入排序
//时间复杂度：O(n2)。n为数据规模
//时间复杂度：数据规模×比较次数
//最好：O(nlogn)。n为数据规模
//平均：O(n2)。n为数据规模
//最坏：O(n2)。n为数据规模
//空间复杂度：O(1)。未使用额外辅助空间
//稳定性：稳定
void binarySort(vector<ELEM_TYPE> &elems) //参数：需排序元素的向量
{
    int i = 0; //循环变量
    int j = 0;
    int temp = 0; //需排序元素

    int left = 0;                 //左位置指针
    int right = elems.size() - 1; //右位置指针
    int mid = 0;                  //中间位置指针

    //第一个元素elems[0]前无元素，不需要排序
    //从第二个元素elems[1]开始遍历，需要排序
    for (i = 1; i < elems.size(); ++i)
    {
        temp = elems[i]; //记录需排序元素
        //需排序元素前的元素向后移动时，会覆盖需排序元素

        //折半查找插入位置  1.比较
        left = 0;      //更新左位置指针
        right = i - 1; //更新右位置指针
        //查找范围：0~i-1

        while (left <= right) //左位置指针<=右位置指针时，循环
        {
            mid = left + (right - left) / 2; //取中间位置

            if (temp == elems[mid]) //需排序元素=中间位置元素时，在右区间查找    稳定性体现
            {
                left = mid + 1;
            }
            else if (temp > elems[mid]) //需排序元素>中间位置元素，在右区间查找
            {
                left = mid + 1;
            }
            else if (temp < elems[mid]) //需排序元素<中间位置元素，在左区间查找
            {
                right = mid - 1;
            }
        }

        //折半查找插入位置结束时：可推导插入位置为right + 1
        // right + 1 ~ i - 1的元素向后移动  2.移动
        for (j = i - 1; j >= right + 1; --j)
        {
            elems[j + 1] = elems[j];
        }

        elems[right + 1] = temp; //插入
    }

    return;
}

希尔排序/缩小增量排序

//希尔排序
//时间复杂度：O(n的1.3次方)~O(n2) 。n为数据规模
//时间复杂度：增量的函数/选取规则（仍是数学难题）
//最好：O(n的1.3次方)。n为数据规模（n在特定范围）
// O(n的1.5次方)。n为数据规模（增量选取规则：2的k次方+1，...，5，3，1。k为整数，k>=1，2的k次方+1 < n）
//最坏：O(n2)。n为数据规模。（增量选取规则：[n/2]下取整，[n/4]下取整，...，1）
//空间复杂度：O(1)。未使用额外辅助空间
//稳定性：不稳定（依据增量划分序列时，可能改变元素的相对位置）
void shellSort(vector<ELEM_TYPE> &elems) //参数：需排序元素的向量
{
    int i = 0; //循环变量
    int j = 0;
    int temp = 0; //需排序元素

    //增量/步长范围：elems.size() / 2 ~ 1
    //步长变化规则：step /= 2
    //对每步长序列进行直接插入排序  类比直接插入排序过程
    for (int step = elems.size() / 2; step >= 1; step /= 2)
    {
        //需排序元素位置：step ~ elems.size() - 1
        //需要比较需排序元素和需排序元素前的元素，从步长的位置开始才有意义
        for (i = step; i < elems.size(); ++i)
        {
            temp = elems[i]; //记录需排序元素
            //需排序元素前的元素向后移动时，会覆盖需排序元素

            //遍历需排序元素前的元素
            //比较需排序元素和需排序元素前的元素
            //需排序元素前的元素位置：j = i - step ~ 0
            for (j = i - step; j >= 0; j -= step)
            {
                if (temp < elems[j]) //需排序元素<需排序元素前的元素   1.比较
                {
                    elems[j + step] = elems[j]; //需排序元素前的元素向后移动 2.移动/交换
                }
                else //>=
                {
                    break;
                }
            }

            //遍历需排序元素前的元素结束时：需排序元素>=需排序元素前的元素    有插入位置
            elems[j + step] = temp; //插入
        }
    }

    return;
}

交换类排序

冒泡排序/起泡排序 简单版

//冒泡排序  简单版
//时间复杂度：O(n2)。n为数据规模
//时间复杂度：数据规模×比较次数
//最好：O(n)。n为数据规模。（有序）
//平均：O(n2)。n为数据规模
//最坏：O(n2)。n为数据规模。（无序的逆序）
//空间复杂度：O(1)。未使用额外辅助空间
//稳定性：稳定
void bubbleSort1(vector<ELEM_TYPE> &elems) //参数：需排序元素的向量
{
    int i = 0; //循环变量
    int j = 0;
    int temp = 0; //需排序元素

    //遍历需排序元素
    //需排序元素位置：0 ~ elems.size() - 2
    // elems.size()个元素需elems.size() - 1次比较
    for (i = 0; i < elems.size() - 1; ++i)
    {
        //遍历需排序元素后的元素
        //需排序元素后的元素位置：i + 1 ~ elems.size() - 1
        for (j = i + 1; j < elems.size(); ++j)
        {
            if (elems[i] > elems[j]) //需排序元素>需排序元素后的元素   1.比较   稳定性体现
            {
                // 2.移动/交换
                temp = elems[i];
                elems[i] = elems[j];
                elems[j] = temp;
            }
        }
    }

    return;
}

冒泡排序 正版

//冒泡排序  正版
void bubbleSort2(vector<ELEM_TYPE> &elems) //参数：需排序元素的向量
{
    int i = 0; //循环变量
    int j = 0;
    int temp = 0; //需排序元素

    //遍历需排序位置
    //需排序位置：0 ~ elems.size() - 2
    // elems.size()个元素需elems.size() - 1次比较

    //注意：
    //排序位置而不是元素：一趟排序确定一个位置
    for (i = 0; i < elems.size() - 1; ++i)
    {
        //遍历需排序位置后的元素
        //需排序位置后的元素位置：i + 1 ~ elems.size() - 1

        //注意：
        //从后往前遍历
        //两两相邻元素排序  思想体现
        for (j = elems.size() - 1; j > i; --j)
        {
            if (elems[j - 1] > elems[j]) //前需排序元素>后需排序元素   1.比较   稳定性体现
            {
                // 2.移动/交换
                temp = elems[j - 1];
                elems[j - 1] = elems[j];
                elems[j] = temp;
            }
        }
    }

    return;
}

冒泡排序 改进版

//冒泡排序  改进版
void bubbleSort3(vector<ELEM_TYPE> &elems) //参数：需排序元素的向量
{
    int i = 0; //循环变量
    int j = 0;
    int temp = 0; //需排序元素

    bool flag = false;
    //标志：
    // true：一趟排序中，有交换过程，序列无序，算法继续进行
    // false：一趟排序中，无交换过程，序列有序，算法结束

    //遍历需排序位置
    //需排序位置：0 ~ elems.size() - 2
    // elems.size()个元素需elems.size() - 1次比较

    //注意：
    //排序位置而不是元素：一趟排序确定一个位置
    for (i = 0; i < elems.size() - 1; ++i)
    {
        //遍历需排序位置后的元素
        //需排序位置后的元素位置：i + 1 ~ elems.size() - 1

        //注意：
        //从后往前遍历
        //两两相邻元素排序  思想体现
        for (j = elems.size() - 1; j > i; --j)
        {
            if (elems[j - 1] > elems[j]) //前需排序元素>后需排序元素   1.比较   稳定性体现
            {
                // 2.移动/交换
                temp = elems[j - 1];
                elems[j - 1] = elems[j];
                elems[j] = temp;

                flag = true; //有交换过程
            }
        }

        if (flag == false) //无交换过程
        {
            return;
        }
    }

    return;
}

快速排序

//快速排序
//时间复杂度：O(nlogn)。n为数据规模
//最好：O(nlogn)。n为数据规模。（无序）
//平均：O(nlogn)。n为数据规模。
//最坏：O(n2)。n为数据规模。（有序或无序的逆序）
//空间复杂度：O(logn)。n为数据规模
//空间复杂度：递归调用栈的大小/树的深度/高度
//最好：O(logn)。n为数据规模（平衡树）
//平均：O(logn)。n为数据规模
//最坏：O(n)。n为数据规模（斜树）
//稳定性：不稳定（依据枢轴划分并交换时，可能改变元素的相对位置）
//注意：时间复杂度和空间复杂度是平均而不是最坏情况

//快速排序的优化
// 1.枢轴选取优化
//（1）随机法
//需排序元素的向量中，随机选取一个元素作为枢轴
//（2）三数取中法
//需排序元素的向量中，最左位置、中间位置和最右位置的元素排序，选取中间的元素作为枢轴
//适用小数据规模
//（3）九数取中法
//需排序元素的向量中，取样三次，每次取三个元素得中间元素，三个中间元素得中间元素
//可适用大数据规模
// 2.不必要交换优化
//备份枢轴
//左和右位置指针遍历时，进行元素替换而不是交换
//遍历后，枢轴放到确定位置
// 3.小数据规模优化
//设置数据规模阈值
//若数据规模<阈值，使用直接插入排序
//若数据规模>=阈值，使用快速排序
// 4.递归优化
//使用尾递归/迭代
//示例：
/*
void quickSort(...)
{
    while (left < right) //使用while
    {
        int i = left;  //逻辑处理
        int j = right;

        ...

        quickSort(elems, left, privot - 1);  //左递归
        left = prvot + 1; //右迭代
        //左递归后，left无用，赋值为prvot + 1
        //while在下次迭代，i = pivot + 1，j = right，相当于右递归的逻辑处理
    }

    ...
}
*/
void quickSort(vector<ELEM_TYPE> &elems, int left, int right) //参数：需排序元素的向量，左位置指针，右位置指针
{
    int i = left;  //左位置指针    用于划分
    int j = right; //右位置指针

    if (left < right) //左位置指针<右位置指针时，递归
    {
        // 1.划分   确定枢轴
        ELEM_TYPE privot = elems[left];
        //当前排序表的第一个元素作为枢轴    枢轴划分当前排序表为左排序表和右排序表

        while (i < j) //左位置指针小于右位置指针时，循环
        {
            //左位置指针小于右位置指针时
            //右位置指针向左移动，直到找到比枢轴小的元素
            while (i < j)
            {
                if (elems[j] >= privot) //右位置指针>=枢轴  向左移动    1.比较
                {
                    --j;
                }
                else //<
                {
                    break;
                }
            }

            elems[i] = elems[j]; //比枢轴小的元素放在左指针位置  2.移动/交换

            //左位置指针小于右位置指针时
            //左位置指针向右移动，直到找到比枢轴大的元素
            while (i < j)
            {
                if (elems[i] <= privot) //左位置指针<=枢轴  向右移动    1.比较
                {
                    ++i;
                }
                else //>
                {
                    break;
                }
            }

            elems[j] = elems[i]; //比枢轴大的元素放在左指针位置  2.移动/交换
        }

        //循环结束时，左排序表的元素比枢轴小，右排序表的元素比枢轴大
        elems[i] = privot; //枢轴放在左位置指针 可推导

        // 2.递归
        //注意：使用left和right
        quickSort(elems, left, privot - 1);  //左递归
        quickSort(elems, privot + 1, right); //右递归
    }

    return;
}

堆

概念

• 数据结构中的完全二叉树。满足：任意一个非叶结点的关键字都不小于（或不大于）其左和右孩子结点的关键字

类型

• 大顶/根堆：任意一个非叶结点的关键字都不小于其左和右孩子结点的关键字
• 小顶/根堆：任意一个非叶结点的关键字都不大于其左和右孩子结点的关键字

插入过程

1. 在最右下位置插入（满足完全二叉树定义）
2. 调整（满足堆定义）

删除过程

1. 交换最右下位置和删除位置的关键字（满足完全二叉树定义）
2. 从最右下位置删除（满足完全二叉树定义）
3. 调整（满足堆定义）

堆排序的过程

对大顶堆：

1. 无序序列->完全二叉树（依据层序遍历方法）
2. 完全二叉树->大顶堆（依据大顶堆调整方法）
3. 大顶堆->有序序列（依据堆排序方法）

层序遍历方法：

• 从上到下，从左到右，构造完全二叉树

大顶堆调整方法：

• 从完全二叉树的最后一个非叶子结点开始，从右到左，从下到上，调整结点
• 交换结点以满足大顶堆定义

堆排序方法：

1. 交换树根结点和最右下位置结点，删除最右下位置结点，输出最右下位置结点（最右下位置结点进入有序序列）
2. 调整（最右下位置结点被交换到树根结点，可能不满足堆定义）
3. 重复1和2步，堆无结点时结束

选择类排序

简单选择排序

//简单选择排序
//时间复杂度：O(n2)。n为数据规模
//时间复杂度：数据规模×比较次数
//最好：O(n2)。n为数据规模
//平均：O(n2)。n为数据规模
//最坏：O(n2)。n为数据规模
//空间复杂度：O(1)。未使用额外辅助空间
//稳定性：不稳定（最小元素和需排序元素交换时，可能改变元素的相对位置）
void selectSort(vector<ELEM_TYPE> &elems) //参数：需排序元素的向量
{
    int i = 0; //循环变量
    int j = 0;

    int min = 0;        //最小元素位置
    ELEM_TYPE temp = 0; //交换时，记录暂存元素

    //遍历需排序位置
    //需排序位置：0 ~ elems.size() - 2
    //最后一个位置elems.size() - 1不需要排序
    // elems.size()个位置需elems.size() - 1趟排序

    //注意：
    //排序位置而不是元素：一趟排序确定一个位置
    for (i = 0; i < elems.size() - 1; ++i)
    {
        min = i; //记录最小元素位置
        //理解：
        // i记录需排序位置
        // min记录最小元素位置
        //从最小元素位置，取最小元素，放到需排序位置

        //遍历需排序位置后的位置
        //比较当前最小元素和需排序位置后的位置的元素，取最小元素，放到需排序位置
        for (int j = i + 1; j < elems.size(); ++j)
        {
            if (elems[min] > elems[j]) //当前最小元素>需排序元素位置后的位置的元素  1.比较/选择
            {
                min = j; //记录最小元素位置
            }
        }

        // 2.移动/交换
        //最小元素，放到需排序位置
        //需排序位置元素，放到最小元素位置
        if (min != i) //最小元素位置!=需排序元素位置
        {
            temp = elems[i];
            elems[i] = elems[min];
            elems[min] = temp;
        }
    }

    return;
}

堆排序

//堆调整    大顶堆法
//参数：需排序元素的向量，闭区间[low，high]位置结点调整为大顶堆
//关键理解：实际上，调整以low位置结点为根的树
void heapAdjust(vector<ELEM_TYPE> &elems, int low, int high)
{
    int i = low; //调整以i位置结点为根的树    调整时，i位置可能会从上到下更新

    ELEM_TYPE temp = elems[low]; //暂存i位置结点的关键字

    //关键理解：
    // j：需比较和交换结点的位置
    //范围：以i位置结点为根的树

    // int j = 2 * i：i位置结点的左孩子结点是2 * i位置结点（依据完全二叉树的性质）
    // j <= high：位置不越界
    // j *= 2：左孩子结点的位置（依据完全二叉树的性质）

    //每循环，比较i位置结点、2 * i位置结点和2 * i + 1位置结点的关键字
    //即比较i位置结点、i位置结点的左孩子结点和i位置结点的右孩子结点的关键字
    for (int j = 2 * i; j <= high; j *= 2)
    {
        // 1. 比较左孩子结点和右孩子结点的关键字

        //  j < high：j不是最后一个结点的位置->i位置结点存在右孩子结点
        //  elems[j] < elems[j + 1]：左孩子结点的关键字<右孩子结点的关键字
        if (j < high && elems[j] < elems[j + 1])
        {
            ++j; //更新需比较和交换结点的位置
        }
        //目的：
        // j：需比较和交换结点的位置
        //取左孩子结点和右孩子结点中，关键字最大的位置
        // j = 2 * i或j = 2 * i + 1

        // 2.比较i位置结点、左孩子结点和右孩子结点中，关键字最大的结点
        // i位置结点<左孩子结点和右孩子结点中，关键字最大的结点
        //需要调整
        if (temp < elems[j])
        {
            elems[i] = elems[j]; // i位置结点的关键字赋值为j位置结点的关键字
            i = j;               //更新i位置
        }
        else //>=    不需要调整
        {
            break; //调整结束
        }
    }

    elems[i] = temp; // i位置结点的关键字赋值为暂存的关键字 注意：i可能已更新

    return;
}

//堆排序    大顶堆法
//时间复杂度：O(nlogn)。n为数据规模
//时间复杂度：建堆和堆排序
//建堆：O(n)。n为数据规模
//堆排序：排序次数×调整堆/树高
//堆排序：O(nlogn)。n为数据规模
//最好：O(nlogn)。n为数据规模
//平均：O(nlogn)。n为数据规模
//最坏：O(nlogn)。n为数据规模
//空间复杂度：O(1)。未使用额外辅助空间
//稳定性：不稳定（需排序元素交换时，可能改变元素的相对位置）
void heapSort(vector<ELEM_TYPE> &elems) //参数：需排序元素的向量
{
    ELEM_TYPE temp = 0; //暂存交换结点的关键字

    // 1.建堆
    //从完全二叉树的最后一个非叶子结点开始，从右到左，从下到上，调整结点
    //范围：1~(elems.size() - 1) / 2
    for (int i = (elems.size() - 1) / 2; i >= 1; --i)
    {
        heapAdjust(elems, i, elems.size() - 1); //注意：闭区间[low，high]位置结点调整为大顶堆   1.比较
    }

    // 2.堆排序
    //范围：2~elems.size() - 1
    //对1~elems.size() - 1个结点，需进行elems.size() - 2次排序，最后一个结点已有序
    for (int i = elems.size() - 1; i >= 2; --i)
    {
        //交换树根结点和最右下位置结点，删除最右下位置结点，输出最右下位置结点（最右下位置结点进入有序序列）    2.移动/交换
        temp = elems[1];
        elems[1] = elems[i];
        elems[i] = temp;

        //调整（最右下位置结点被交换到树根结点，可能不满足堆定义）  1.比较
        heapAdjust(elems, 1, i - 1);
        //注意：i - 1：因为最右下位置结点进入有序序列，无需进行调整
    }

    return;
}

归并类排序

二路归并排序 递归法 分治法

//二路归并
//参数：需排序元素的向量，归并闭区间[low，mid]和[mid + 1，high]序列
void merge(vector<ELEM_TYPE> &elems, int low, int mid, int high)
{
    vector<ELEM_TYPE> temp(elems.size(), 0); //暂存需排序元素的向量
    //因为需要修改elems，elems存储已排序元素

    //暂存需排序元素
    for (int i = low; i <= high; ++i)
    {
        temp[i] = elems[i];
    }

    //循环变量
    int i = low;     //闭区间[low，mid]序列位置
    int j = mid + 1; //闭区间[mid + 1，high]序列位置
    int k = low;     // elems位置

    //闭区间[low，mid]序列位置和闭区间[mid + 1，high]序列位置未越界时，循环
    //比较，取两区间中的最小元素，存储在elems位置
    while (i <= mid && j <= high)
    {
        if (temp[i] <= temp[j]) //闭区间[low，mid]序列元素 <= 闭区间[mid + 1，high]序列元素 两两比较，稳定性体现
        {
            elems[k] = temp[i];

            ++k; //更新位置
            ++i;
        }
        else //>
        {
            elems[k] = temp[j];

            ++k; //更新位置
            ++j;
        }
    }

    //闭区间[low，mid]序列位置或闭区间[mid + 1，high]序列位置越界
    //若另一个序列有未排序元素，存储在elems位置
    while (i <= mid)
    {
        elems[k] = temp[i];

        ++k; //更新位置
        ++i;
    }

    while (j <= high)
    {
        elems[k] = temp[j];

        ++k; //更新位置
        ++j;
    }

    return;
}

//二路归并排序	递归法  分治法
//时间复杂度：O(nlogn)。n为数据规模
//时间复杂度：归并趟数×一趟归并的操作次数
//归并趟数：O(nlogn)。n为数据规模
//一趟归并的操作次数：O(n)。n为数据规模
//最好：O(nlogn)。n为数据规模
//平均：O(nlogn)。n为数据规模
//最坏：O(nlogn)。n为数据规模
//空间复杂度：O(n)。n为数据规模
//空间复杂度：暂存需排序元素辅助空间的大小或递归调用栈的大小
//暂存需排序元素辅助空间的大小：O(n)。n为数据规模
//递归调用栈的大小：O(logn)。n为数据规模
//稳定性：稳定

//二路归并排序  迭代法简介
//循环中：更新步长/增量，两两归并，归并剩余单个序列
//时间复杂度：无递归，比递归法更优，数量级不变
//空间复杂度：无递归调用栈，比递归法更优，数量级不变

//另：m = (log以k为底的n)上取整。m为归并趟数，k为归并路数，n为数据规模

//参数：需排序元素的向量，排序闭区间[low，high]序列：左位置指针，右位置指针
void mergeSort(vector<ELEM_TYPE> &elems, int low, int high)
{
    if (low < high) //左位置指针 < 右位置指针，区间合法
    {
        int mid = low + (high - low) / 2; //中间位置指针    划分左右区间

        mergeSort(elems, low, mid);      //左区间归并排序   左
        mergeSort(elems, mid + 1, high); //右区间归并排序   右
        merge(elems, low, mid, high);    //归并 中
    }

    return;
}

基数类排序

基数排序

//基数排序
//思想：多关键字比较，无需进行比较和移动
//类型：最高位优先（MSD）；最低位优先（LSD）
//最高位优先（MSD）：排序最高位，排序次高位...以此类推
//最低位优先（LSD）：分配和收集最低位，分配和收集次低位...以此类推。对每个数据分配入队列，对每个队列收集出队列数据
//注意和理解：最高位优先能够在一定程度上确定排序，最低位优先不能
//时间复杂度：O(d(n+r))。d为数据位数，n为数据规模，r为数据基数/取值范围。如十进制数字基数为10、小写字母基数为26
//时间复杂度：排序趟数×分配和收集次数。排序趟数为数据位数，分配次数为数据规模，收集次数为数据基数
//最好：O(d(n+r))
//平均：O(d(n+r))
//最坏：O(d(n+r))
//空间复杂度：O(r)。r为数据基数/取值范围。如十进制数字基数为10、小写字母基数为26
//空间复杂度：分配和收集队列的大小
//稳定性：稳定（按位排序时，稳定性体现）

总结

插入类排序

交换类排序

选择类排序

归并类排序

基数类排序

总表1

总表2

记忆

时间复杂度为O(n2)：

• 简单排序：直接插入排序，折半插入排序，冒泡排序，简单选择排序

时间复杂度为O(nlogn)：

• 复杂排序：希尔排序（可能），快速排序，堆排序
• 归并排序：二路归并排序

时间复杂度特殊：

• 基数排序

最好、平均和最坏时间复杂度相同：

• 简单选择排序
• 堆排序
• 二路归并排序
• 基数排序

最好和平均时间复杂度不同：

• 直接插入排序
• 折半插入排序
• 希尔排序
• 冒泡排序

最坏和平均时间复杂度不同：

• 希尔排序
• 快速排序

空间复杂度不为O(1)：

• 快速排序
• 二路归并排序
• 基数排序

稳定：

• 简单排序：直接插入排序，折半插入排序，冒泡排序
• 归并排序，基数排序：二路归并排序

不稳定：

• 复杂排序：希尔排序，快速排序
• 选择类排序：简单选择排序，堆排序

一趟排序，能够确定元素的最终位置：

• 交换类排序：冒泡排序，快速排序
• 选择类排序：简单选择排序，堆排序

比较次数和初始序列无关：

• 折半插入排序
• 简单选择排序
• 二路归并排序
• 基数排序

移动次数和初始序列无关：

• 基数排序

排序趟数和初始序列有关：

• 交换类排序：冒泡排序，快速排序

应用

数据基本有序：最好时间复杂度小

• 直接插入排序
• 冒泡排序

数据规模小（<10000）：简单排序

• 直接插入排序（性能最优；数据规模<=25）
• 折半插入排序（相对直接插入排序，适用数据规模更大）
• 冒泡排序
• 简单选择排序（相对冒泡排序，性能更优）

数据规模小，信息量大（如：数据是数十位的数字->占用空间大->移动时间长）：

• 简单选择排序（移动次数少）

数据规模大：复杂排序

• 数据规模<=1000：希尔排序
• 数据随机分布：快速排序（性能最优；数据基本有序时，性能最差）
• 空间复杂度小；从大数据规模排序小部分数据：堆排序
• 稳定：归并排序
• 多关键字排序：基数排序

数据规模更大：外部排序

数据规模大，数据位数少：

• 基数排序

数据规模大，数据位数多：

• 最高位优先（MSD）的基数排序结合直接插入排序

其他：

• 堆排序只适用顺序存储方式
• 堆排序建堆时比较次数多，不适用数据规模小
• 归并排序尽量用迭代法而不是递归法
• 基数排序不适用实数类型
• 混合排序使用

外部排序

概念

• 内存作为工作/辅助空间，排序外存数据
• 算法相对复杂
• 时间=读写外存内存时间+内存排序时间+内存归并时间
• 时间->访问外存/输入/输出（I/O）次数
• 优化：减少访问外存/输入/输出（I/O）次数->减少初始归并段数，增多

流程

1. 外存数据分段
2. 段读入内存
3. 段在内存排序，为初始归并段
4. 初始归并段写回外存
5. 初始归并段读入内存
6. 初始归并段在内存归并，为归并段
7. 归并段写回外存

另：

1. 分段
2. 排序
3. 归并

排序方法

常用：

• 归并排序

子算法：

• 置换-选择排序
• 最佳归并树
• 败者树

置换-选择排序：

• 作用：排序时，生成初始归并段时不受内存限制；减少初始归并段数
• 外存段中，每记录读入内存
• 依据排序规则，选择一个最值生成初始归并段。不符合排序规则的最值等待生成下一初始归并段
• 初始归并段长度不同

最佳归并树：

• 作用：归并时，减少访问外存/输入/输出（I/O）次数；适应长度不同初始归并段的归并
• 生成哈夫曼树
• 权：初始归并段的数据规模
• 路径长度：归并次数
• 2：读和写
• 访问外存/输入/输出（I/O）次数 = 带权路径长度（WPL） × 2

败者树：

• 作用：排序和归并时，减少选最值的比较次数/时间复杂度；增多归并路数

对最小值败者树：

• 叶子结点：值为归并段的段首值，旁为归并段的序号
• 非叶子结点：值为归并段的序号，旁为归并段的段首值
• 构造：比较值，构造二叉树。败者（值大者）为双亲结点，胜者（值小者）为双亲结点的双亲结点
• 由树根结点的序号，取值写回外存，取另外值读入内存
• 调整：同构造过程

选择树：堆，败者树

时间复杂度：相对复杂

• 置换-选择排序中，每记录有两次访问外存/输入/输出（I/O）
• 每一趟归并，每记录有两次访问外存/输入/输出（I/O）
• 归并趟数：[log以k为底的m]上取整。k为归并路数，m为初始归并段数=外存记录数÷内存能容纳的记录数
• k路归并败者树：k个记录/叶子结点的二叉树
• k路归并败者树构造的时间复杂度：O(klogk)。k为归并路数
• k路归并败者树的树高：[log以2为底的k]上取整+1。k为归并路数（不包括树根结点层）
• 传统选最值的比较次数：k-1。k为归并路数
• k路归并败者树选最值的比较次数：[log以2为底的k]上取整。k为归并路数
• k路归并败者树选最值的时间复杂度：O(logk)。k为归并路数

空间复杂度：O(1)。未使用辅助空间

总结

“排序”学习提纲。

参考资料

• 《2023版数据结构高分笔记》主编：率辉
• 《2023年计算机组成原理考研复习指导》组编：王道论坛
• 《大话数据结构》作者：程杰

作者的话

• 感谢参考资料的作者/博主
• 作者：夜悊
• 版权所有，转载请注明出处，谢谢~
• 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
• 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
• 文章在认识上有错误的地方, 敬请批评指正
• 望读者们都能有所收获