快速排序

强大，简洁，优美

查尔斯·霍尔惨遭隐姓埋名

---

原理

快速排序对冒泡排序进行了改进

其思想是：
通过一次排序将整个无序表分成相互独立的$A,B$两部分
$\forall x \lbrace x\in A \rbrace < \forall y \lbrace y\in B \rbrace$
然后继续用此法分别对$A,B$进行同样的操作
直到每一个小部分不可再分
所得的序列就成为了有序序列

其最核心的思想就是二分

单次过程图解

只是一种比较常用的分割方式

来源

整个过程中最重要的是实现分割操作 具体实现过程为：

• 设置两个指针 low(left) 和 high，分别指向无序表的表头和表尾，如下图所示：

• 先由 high 指针从右往左依次遍历，直到找到一个比 49 小的关键字，所以 high 指针走到 27 的地方停止。找到之后将该关键字同 low 指向的关键字进行互换：

• 然后指针 low 从左往右依次遍历，直到找到一个比 49 大的关键字为止，所以 low 指针走到 65 的地方停止。同样找到后同 high 指向的关键字进行互换：

• 指针 high 继续左移，到 13 所在的位置停止（13<49），然后同 low 指向的关键字进行互换：

• 指针 low 继续右移，到 97 所在的位置停止（97>49），然后同 high 指向的关键字互换位置：

• 指针 high 继续左移，此时两指针相遇，整个过程结束；

交换是为了储存keyValue，如果用一个变量储存keyValue，也可以不交换

---

代码实现

不同的人有不同的写法
但那个不同的部分都有一个相同的功能：
*把小值放在keyValue左边，把大值放在keyValue右边*
其他部分都是大差不差的

C标准库代码

void Qsort(void* base, int left, int right, int size, int (*cmp)(const void* a, const void* b))
{
    /* left may be < 0 because of the last - 1 */
    assert(base != NULL && size >= 1 && cmp != NULL);
    if (left >= right) return;
    char* pleft = (char*)base + left * size;
    char* pkey = (char*)base + (left + (right - left) / 2) * size;
    swap(pleft, pkey, size);
    int last = left;
    char* plast = (char*)base + last * size;
    //这里的for做的操作是把keyValue放在第一个位置（第一个位置是暂存位）
    //把所有小于keyValue的值放在第一个位置的后面
    //第一个值再与小值的最后一个交换
    //这样所有小值就在keyValue左边，所有大值在keyValue右边
    for (int i = left + 1; i <= right; ++i) {
        char* pi = (char*)base + i * size;
        if (cmp(pi, pleft) < 0) {
            ++last;
            plast = (char*)base + last * size;
            swap(pi, plast, size);
        }
    }
    swap(pleft, plast, size);
    //交换后*plast的值对应keyValue
    Qsort(base, left, last - 1, size, cmp);
    Qsort(base, last + 1, right, size, cmp);
}

不使用交换

此处用width替代size

void c_qsort(void* _arr, int left, int right, int size, int(*cmp)(const void* a, const void* b))
{
    //字节化_arr（使_arr内的数据进行字节对齐，方便操作）
    char* arr = (char*)_arr;
    if (left < right)
    {
        int low = left;
        int high = right;
        char* keyValue = (char*)malloc(size);
        memcpy(keyValue, arr + low * size, size);
        //过程与图示相同，但直接覆盖元素
        while (low < high)
        {
            while (low < high)
            {
                if (cmp(arr + high * size, keyValue) < 0)
                {
                    memcpy(arr + low * size, arr + high * size, size);
                    break;
                }
                high--;
            }
            while (low < high)
            {
                if (cmp(arr + low * size, keyValue) > 0)
                {
                    memcpy(arr + high * size, arr + low * size, size);
                    break;
                }
                low++;
            }
        }
        //while完成之后将key指向的元素替换成keyValue
        memcpy(arr + low * size, keyValue, size);
        c_qsort(arr, low + 1, right, size, cmp);
        c_qsort(arr, left, low - 1, size, cmp);
    }
}

省流版

其实vector有自带的sort

template<typename T>
void c_qsort(vector<T>& arr, int left = -2, int right = -2) {
    left = left == -2 ? 0 : left;
    right = right == -2 ? arr.size() - 1 : right;
    bool flag = false;
    if (left < right)
    {
        int lowKey = left;
        int highKey = right;
        while (lowKey < highKey) {
            if (arr[lowKey] > arr[highKey]) {
                swap(arr[lowKey], arr[highKey]);
                flag = !flag;
                continue;
            }
            flag ? lowKey++ : highKey--;
        }
        c_qsort(arr, lowKey + 1, right);
        c_qsort(arr, left, lowKey - 1);
    }
}