写一个快速排序算法

快速排序（Quick Sort）是一种基于分治思想的高效排序算法，其基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再对这两部分记录分别进行快速排序，以达到整个序列有序的目的。

具体步骤如下：

选择一个基准数（pivot），一般选择序列的第一个数。
将序列中小于基准数的数放在基准数左边，大于基准数的数放在基准数右边。
对基准数左右两个子序列分别进行递归快速排序。

实现代码如下：

void quickSort(int arr[], int left, int right) {
    if(left < right) {
        int pivot = partition(arr, left, right); // 将数组分为两个部分
        quickSort(arr, left, pivot - 1); // 对左部分进行快速排序
        quickSort(arr, pivot + 1, right); // 对右部分进行快速排序
    }
}

int partition(int arr[], int left, int right) {
    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; // 把基准数放到最终位置
    return i; // 返回基准数的位置
}