快速排序的算法设计与分析

问题描述：设计并分析快速排序

【算法设计思想】

1. 选择基准值：从待排序数组中选择一个元素作为基准值（pivot）。在这个示例中，选择了数组中的最后一个元素作为基准值。
2. 分割数组：将数组分割为两部分，小于等于基准值的元素放在基准值的左边，大于基准值的元素放在右边。这一步骤称为分割（partition）。
3. 递归排序：对分割后的左右两个子数组分别进行快速排序。递归调用快速排序函数。
4. 合并结果：排序完成后，所有的子数组都被排序，数组也就被完全排序了。

快速排序是一种分治算法，其基本思想是通过递归地将待排序数组划分为较小的子数组，然后分别对这些子数组进行排序。快速排序的核心是分割操作，通过一次遍历将数组分割为两个部分，并且保证左侧部分的元素都小于等于基准值，右侧部分的元素都大于基准值。这样，在递归过程中，每次排序都会将一个元素放置到其最终的位置上，直到整个数组排序完成。

【算法描述】

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 将数组划分为两部分，并获取分割点的索引
        int pivotIndex = partition(arr, low, high);

        // 对分割点左侧的子数组进行快速排序
        quickSort(arr, low, pivotIndex - 1);
        // 对分割点右侧的子数组进行快速排序
        quickSort(arr, pivotIndex + 1, high);
    }
}

// 分割函数，用于确定分割点的索引并调整数组
int partition(int arr[], int low, int high) {
    // 选取数组最后一个元素作为基准值
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        // 如果当前元素小于等于基准值，则将它与 i 指向的元素交换位置
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 将基准值放到正确的位置上
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

【完整的测试程序】

#include <iostream>

void quicksort(int arr[],int low,int high);
int partition(int arr[],int low,int high);

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 将数组划分为两部分，并获取分割点的索引
        int pivotIndex = partition(arr, low, high);

        // 对分割点左侧的子数组进行快速排序
        quickSort(arr, low, pivotIndex - 1);
        // 对分割点右侧的子数组进行快速排序
        quickSort(arr, pivotIndex + 1, high);
    }
}

// 分割函数，用于确定分割点的索引并调整数组
int partition(int arr[], int low, int high) {
    // 选取数组最后一个元素作为基准值
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        // 如果当前元素小于等于基准值，则将它与 i 指向的元素交换位置
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 将基准值放到正确的位置上
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

// 主函数
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "排序前的数组: " << std::endl;
    printArray(arr, n);

    // 调用快速排序函数
    quickSort(arr, 0, n - 1);

    std::cout << "排序后的数组: " << std::endl;
    printArray(arr, n);

    return 0;
}