快速排序算法的三种代码实现

快速排序算法是一种高效的排序算法，提供了多种不同的实现方式。无论是基本实现、双边循环法还是挖坑法，快速排序都具有较好的时间复杂度和排序效率。不同的实现方式针对不同的场景和需求，可以选择适合的实现方式来提高算法性能。理解这三种实现方式的代码逻辑和优化技巧，有助于读者更好地理

• 快慢指针单循环

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 选择基准元素
        int pivot = arr[high];
        int i = low - 1;

        // 划分过程
        for (int j = low; j <= high - 1; j++) {
            if (arr[j] < pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);

        // 递归排序
        int partitionIndex = i + 1;
        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
}

• 快速排序的双边循环法实现

int partition(int arr[], int low, int high) {
    // 选择基准元素
    int pivot = arr[low];
    int left = low;
    int right = high;

    while (left < right) {
        // 从右边开始找到小于基准元素的值
        while (left < right && arr[right] >= pivot)
            right--;

        // 从左边开始找到大于基准元素的值
        while (left < right && arr[left] <= pivot)
            left++;

        // 交换左右两个元素
        std::swap(arr[left], arr[right]);
    }
    // 将基准元素放在数组分割点的位置
    std::swap(arr[low], arr[left]);

    return left;
}

void quickSortBilateral(int arr[], int low, int high) {
    if (low < high) {
        int partitionIndex = partition(arr, low, high);

        // 递归排序
        quickSortBilateral(arr, low, partitionIndex - 1);
        quickSortBilateral(arr, partitionIndex + 1, high);
    }
}

• 快速排序的挖坑法实现

int partition(int arr[], int low, int high) {
    // 选择基准元素
    int pivot = arr[low];
    int left = low;
    int right = high;

    while (left < right) {
        // 从右边找到小于基准元素的值并填坑
        while (left < right && arr[right] >= pivot)
            right--;
        arr[left] = arr[right];

        // 从左边找到大于基准元素的值并填坑
        while (left < right && arr[left] <= pivot)
            left++;
        arr[right] = arr[left];
    }

    // 将基准元素放入最终分割点
    arr[left] = pivot;

    return left;
}

void quickSortPit(int arr[], int low, int high) {
    if (low < high) {
        int partitionIndex = partition(arr, low, high);

        // 递归排序
        quickSortPit(arr, low, partitionIndex - 1);
        quickSortPit(arr, partitionIndex + 1, high);
    }
}