经典的排序算法——快速排序

快速排序是一种非常著名的基于比较的排序算法，其基本思想和步骤如下：

1. 选择基准（Pivot）：

• 在待排序的数组中选取一个元素作为基准。通常选择第一个、最后一个或者随机选择一个元素。

2. 分区操作（Partitioning）：

• 遍历数组其余部分，将所有小于基准值的元素移动到基准前面，所有大于基准值的元素移动到基准后面。完成这一步后，基准位置就处于最终正确的位置上，该位置左侧的所有元素都不大于基准，右侧的所有元素都不小于基准。

3. 递归调用：

• 对基准左右两侧的子数组分别重复上述两个步骤。对于左半边，基准是当前子数组的第一个元素；对于右半边，基准是分割后子数组的第一个元素。这个过程一直持续到每个子数组只剩下一个或零个元素（即已有序）。

4. C++实现示例（简化版）：

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pivot is the partitioning index
        int pivot = partition(arr, low, high);

        // Recursively sort elements before and after pivot
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

// Function to partition the array around a pivot element
int partition(int arr[], int low, int high) {
    // Choose the rightmost element as pivot
    int pivotValue = arr[high];
    int i = (low - 1); // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than or equal to the pivot
        if (arr[j] <= pivotValue) {
            i++; // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// Swap utility function
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

1. 性能分析：

? 平均时间复杂度：在大多数情况下，快速排序的时间复杂度为O(n log n)，这是因为每次划分都将问题规模减半，并且需要对n个元素进行log n层划分。

? 最好情况：当每次划分都均匀地将数组分为两部分时，时间复杂度达到最佳状态。

? 最坏情况：如果每次划分得到的分割都是最不平衡的（例如，每次都只有一个元素在一边），则时间复杂度会退化至O(n^2)。不过通过合理的策略选择基准（如三数取中法），可以很大程度上避免这种情况。

2. 空间复杂度：

快速排序的空间复杂度取决于递归栈的深度，平均情况下为O(log n)，最坏情况下也是O(n)。由于快速排序具有内在的并行性以及在实践中良好的表现，它被广泛应用于实际数据处理领域。