C++实现快速排序算法

快速排序算法是一种分治算法，它的基本思路是：1. 选择一个基准元素；2. 把所有比基准元素小的数放到它的左边，所有比基准元素大的数放到它的右边；3. 对左右两边的子序列重复步骤 1 和 2，直到序列的所有元素都有序为止。

相关问题

c++实现快速排序算法

代码实现了快速排序算法，以下是实现步骤：
1. 定义一个快速排序函数，接受一个整数数组、数组的起始位置和终止位置作为参数。
2. 如果起始位置大于等于终止位置，说明待排序序列只有一个元素，直接返回。
3. 定义两个指针i和j，分别指向起始位置和终止位置。
4. 将起始位置的元素作为基准数key。
5. 使用while循环来分别从右边和左边查找小于和大于基准数key的元素，并将它们交换位置。
6. 当i和j相遇时，将基准数key赋值给指针i处。
7. 递归调用快速排序函数对i左边的序列进行快速排序。
8. 递归调用快速排序函数对i右边的序列进行快速排序。
9. 在主函数中定义一个整数数组，调用快速排序函数进行排序并输出结果。

c++ 实现快速排序算法

下面是用 C++ 实现的快速排序算法的示例代码：

#include <iostream>
using namespace std;

// 交换两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 找到分区点，并将数组划分为两部分
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选取最后一个元素作为分区点
    int i = (low - 1);  // 记录比分区点小的元素的位置

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 获取分区点

        // 对分区点左侧和右侧的子数组进行递归排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

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

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组为：" << endl;
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    cout << "排序后的数组为：" << endl;
    printArray(arr, size);

    return 0;
}

这段代码实现了快速排序算法。快速排序是一种高效的排序算法，其基本思想是通过选择一个分区点（通常是数组中的一个元素），将数组划分为两个子数组，左侧子数组的元素都小于分区点，右侧子数组的元素都大于分区点。然后对子数组进行递归排序，直到整个数组有序。在代码中，`partition` 函数用于找到分区点并进行划分，`quickSort` 函数用于递归排序子数组，`swap` 函数用于交换两个元素的值。最后，在 `main` 函数中测试了该算法的功能。