8.3 交换排序

8.3.1 冒泡排序

空间复杂度$O(1)$

时间复杂度$O\left( n^{2}\right)$

8.3.2 快速排序

每次枢轴把表分成长度相近的两个子表时，速度是最快的。当表本身已经有序或逆序时，速度最慢。

时间复杂度$O\left( n\log_{2} n\right)$

递归平均次数$\log_{2}n$乘以每次递归的复杂度 n

void Quicksort(int *a, int low, int high)
{
    if (low < high)
    {
        int pivotpos = Partition(a, low, high);
        Quicksort(a, low, pivotpos - 1);
        Quicksort(a, pivotpos + 1, high);
    }
}
int Partition(int *a, int low, int high)
{
    int pivot = a[low];
    while (low < high)
    {
        while (low < high && a[high] >= pivot)
        {
            high--;
        }
        a[low] = a[high];
        while (low < high && a[low] <= pivot)
        {
            low++;
        }
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}