原理

通过选定一个基准（通常是最后一个数），把数组排成两部分，一部分全小于基准一部分全大于基准（通常采用两个指针从两头扫描，两头都扫到应在另一边的数就交换），然后对两部分分别采用同样的算法，如此递归即可排完

代码实现

int partition(int* arr, int left, int right)
{
    int midPar = arr[right];
    int lPtr = left;
    int rPtr = right - 1;

    while (lPtr <= rPtr)
    {
        while (lPtr <= rPtr && arr[lPtr] < midPar)  //注意避免数组越界
        {
            lPtr++;
        }

        while (lPtr <= rPtr && arr[rPtr] >= midPar)
        {
            rPtr--;
        }

        if (lPtr < rPtr)
        {
            swap(&arr[lPtr], &arr[rPtr]);
        }

        //print(arr, 10);

    }

    swap(&arr[lPtr], &arr[right]);

    return lPtr;
}

void sort(int* arr, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int mid = partition(arr, left, right);
    sort(arr, left, mid - 1);
    sort(arr, mid + 1, right);
}

评价

n*logn级别的时间复杂度 快但不稳定