根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

1.冒泡排序

算法原理

从后往前（或从前往后）两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。称这个过程为“一趟”冒泡排序，最多只需n-1趟排序
每一趟排序后都可以使一个元素的移动到最终位置，以确定最终位置的元素在之后的处理中无需对比
如果某一趟排序过程中未发生“交换”，则算法可以提前结束

性能

空间复杂度：O(1)
时间复杂度：
- 最好（有序）：O(n)
- 最差（逆序）：O(n^2)
- 平均：O(n^2)
稳定性：稳定
适用性：顺序表、链表都可以

代码

// 冒泡排序
void bulleSort(SqList& L)
{
    if (L.length <= 1)
        return;
    // 提前退出标志位
    bool flag = false;
    for (int i = 0; i < L.length; i++)
    {
        flag = false;
        for (int j = 0; j < L.length - i - 1; j++)
        {
            // 前面的元素比后面的大，交换顺序
            if (L.data[j] > L.data[j + 1])
            {
                int tmp = L.data[j];
                L.data[j] = L.data[j + 1];
                L.data[j + 1] = tmp;
                // 数据交换标志位
                flag = true;
            }
        }
        // 若没有数据交换，提前退出
        if (!flag)
            break;
    }
}

2.快速排序

2.1算法思想

从待排序序列中任取一个元素为基准（枢轴）pivot
比它小的往前放，比它大的往后放，则pivot放在最中间位置，这个过程称为一趟快速排序
一次划分为左右两个子表，再分别递归两个子表重复上述过程，直到每个部分只有一个元素为止

2.2实现

high直至指向表尾，low指针指向表头，low指向元素存为基准元素pivot
从high开始，向前比较，比基准大，high--，继续比较
若比基准小，则high所指元素移动到low的位置
再从low指针所指元素和基准元素比较，比基准小，low++，继续比较
若比基准大，则low所指元素移动到high位置
......

当dk=1时，就是直接插入排序

2.3性能

（1）空间复杂度

最好情况：树的高度与递归调用深度一样：

O(log_2n)

最坏情况：n-1次调用，栈深度 n-1

平均情况：

O(log_2n)

空间复杂度 = 递归调用层数

（2）时间复杂度

快速排序的时间复杂度 = O(n * 递归层数)，运行时间与划分是否对称有关

最好情况：做平衡划分：

O(nlog_2n)

最坏情况：发生在两个区域分别包括n-1个元素和0个元素

优化思路：尽量选取数组在中间的元素，从头尾各去一个，它们的中间值作为枢轴元素；或从表中随机选取；

平均情况：

O(nlog_2n)

快速排序是所有内部排序算法中平均性能最优的

（3）稳定性

不稳定

（4）适用性

仅适用于线性表为顺序存储的情况

（5）说明

一次划分：确定一个元素的最终位置
一趟排序：可能确定多个元素的最终位置

2.4 代码

// 一次划分区间
int partiteRegion(SqList& L, int low, int high)
{
    // 当前表的第一个元素作为枢轴，对其划分
    ElemType pivot = L.data[low];
    // 循环条件
    while (low < high)
    {
        // high向前寻找比枢轴点小的元素
        while (low < high && L.data[high] > pivot)
            high--;
        // 将此小的元素移动到枢轴点左端
        L.data[low] = L.data[high];
        // low向后寻找比枢轴点大的元素
        while (low < high && L.data[low] <= pivot)
            low++;
        // 将此大的元素移动到枢轴点右端
        L.data[high] = L.data[low];
    }
    // 枢轴点元素放到最终位置
    L.data[low] = pivot;
    // 放回枢轴点元素
    return low;
}
void quickSort(SqList& L, int low, int high)
{
    if (low < high)
    {
        // 划分区间
        int pivotPos = partiteRegion(L, low, high);
        // 一次对两个子表进行递归排序
        quickSort(L, low, pivotPos - 1);
        quickSort(L, pivotPos + 1, high);
    }
}