交换类

冒泡排序

进行两两交换，一趟下来把一个最值移到了最右边

1. 【最坏时间复杂度】\(O(n^2)\)；待排序列逆序，基本操作总的执行次数为(n-1+1)(n-1)/2=n(n-1)/2
2. 【最好时间复杂度】\(O(n)\)；待排序序列已经有序，第二层循环不进行
3. 【平均时间复杂度】\(O(n^2)\)
4. 【空间复杂度】O(1)

快速排序

第一个同学出列，其他人以他为中心，比他矮的到他的左边，比他高的到他的右边

步骤：[low, high]

1. 取左边第一个作为哨兵，并且保存下来key
2. i=low，然后从左到右搜索（即i++）；j=high然后从右到左搜索（即j--）；直到i>j，每次循环执行
   1. 如果arr[j] < key，将把它放到arr[i]的位置
   2. 如果arr[i] > key，就把它放到arr[j]的位置

void QuickSort(int arr[], int low, int high) {
    if(low >= high) return; //超出范围，直接退出

    auto key = arr[low]; //把最左边的元素作为哨兵

    auto i = low;
    auto j = high;
    while(i < j) {
        //# j从右到左进行移动
        // 如果arr[j]比哨兵大就继续位移
        while(i<j && arr[j] >= key) --j;
        //如果遇到比key小，要放在哨兵左边，放到i空出来的位置
        // 放完后，因为i的位置被填上了，因此要向右位移
        if(i < j) arr[i++] = arr[j];

        //# i从左到右移动
        // 如果arr[i]比哨兵小就继续位移
        while(i<j && arr[i] <= key) ++i;
        //如果遇到比tmp大的，要放在左边
        // 放完后，因为j的位置被填上了，因此要向右位移
        if(i < j) arr[j--] = arr[i];
    }

    //比哨兵小的都排在左边了，比哨兵大的都排在右边了
    // 因此这个哨兵就弄完了，继续剩下的范围
    arr[i] = tmp;
    QuickSort(arr, low, i-1);
    QUickSort(arr, i+1, high);
}

【评价】

1. 快速排序的排序趟数和初始序列有关；
2. 在同级别的算法中（\(O(X*nlog_2n)\)），此算法的X最小

【最好】\(O(nlog_2n)\)序列越接近无序，越有效

【最坏】\(O(n^2)\)序列元素越有序，越无效

【平均】\(O(nlog_2n)\)

【空间复杂度】\(O(log_2n)\)递归算法，空间消耗大，需要用到系统栈