pta7-5快速排序

快速排序（Quick Sort）是一种常用的排序算法，它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序的具体步骤如下：
1. 选择一个基准元素（通常选择第一个元素）。
2. 将序列中小于等于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边。
3. 对基准元素左右两边的子序列分别进行快速排序，直到子序列的长度为1或0。

以下是一个示例代码实现：

void quickSort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr[left]; // 选择第一个元素作为基准元素
    int i = left, j = right;
    while (i < j) {
        // 从右向左找到第一个小于基准元素的位置
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            arr[i++] = arr[j];
        }
        // 从左向右找到第一个大于基准元素的位置
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            arr[j--] = arr[i];
        }
    }
    arr[i] = pivot; // 将基准元素放到最终位置
    quickSort(arr, left, i - 1); // 对左边子序列进行快速排序
    quickSort(arr, i + 1, right); // 对右边子序列进行快速排序
}