快排代码的多种实现方式

快速排序是一种经典的排序算法，其主要思想是通过分治法将一个数组分为两个子数组，然后递归地对两个子数组进行排序。

以下是快速排序的几种常见实现方式：

1. Hoare算法

Hoare算法是最初实现快速排序的算法，它使用两个指针分别从数组的两端开始扫描，当左指针指向的元素大于基准元素时，停止扫描；当右指针指向的元素小于基准元素时，停止扫描，然后交换左右指针所指向的元素，最后将基准元素放到最终的位置上。

void quicksort(int arr[], int left, int right) {
    if (left >= right) return;
    int i = left, j = right, pivot = arr[left];
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++; j--;
        }
    }
    quicksort(arr, left, j);
    quicksort(arr, i, right);
}

2. Lomuto算法

Lomuto算法是另一种常见的快速排序实现方式，它使用单个指针从左向右扫描数组，并将小于基准元素的元素交换到数组的左侧，最后将基准元素放到最终的位置上。

void quicksort(int arr[], int left, int right) {
    if (left >= right) return;
    int i = left, j = left;
    for (; j < right; j++) {
        if (arr[j] < arr[right]) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[right]);
    quicksort(arr, left, i - 1);
    quicksort(arr, i + 1, right);
}

3. 双向扫描

双向扫描是一种优化的快速排序算法，它使用两个指针分别从数组的两端开始扫描，并且每次交换的元素都是不同的。这种算法可以减少交换次数，并且可以处理有大量重复元素的情况。

void quicksort(int arr[], int left, int right) {
    if (left >= right) return;
    int i = left, j = right, pivot = arr[left + (right - left) / 2];
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            if (i < j) swap(arr[i], arr[j]);
            i++; j--;
        }
    }
    quicksort(arr, left, j);
    quicksort(arr, i, right);
}

无论使用哪种实现方式，快速排序的平均时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n^2)，空间复杂度为O(logn)。