C++快速排序代码实现 |21xrx.com

2023-07-09 12:04:15 深夜i -- --

C++ 快速排序代码实现

快速排序是一种常用的排序算法，它利用了分治的思想，将一个大问题拆分成多个小问题，并通过递归求解，最终将这些小问题的解整合成一个完整的问题的解。在 C++ 中实现快速排序需要以下代码：

1. 函数实现：

void quickSort(int arr[], int left, int right) {

int i = left, j = right;

int tmp;

int pivot = arr[(left + right) / 2]; // 取中点作为基准

// 划分过程

while (i <= j) {

while (arr[i] < pivot) {

i++;

}

while (arr[j] > pivot)

j--;

if (i <= j) {

tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

i++;

j--;

}

// 递归排序左右两个子数组

if (left < j) {

quickSort(arr, left, j);

}

if (i < right) {

quickSort(arr, i, right);

}

2. 调用：

int main() {

int arr[] = 1;

int size = sizeof(arr) / sizeof(int);

quickSort(arr, 0, size - 1);

for (int i = 0; i < size; i++) {

cout << arr[i] << " ";

}

return 0;

}

快速排序的平均时间复杂度为 O(nlogn)，当然最坏时间复杂度是 O(n^2)。该算法的空间复杂度较低，只需要一个辅助变量即可实现。因此，快速排序具有速度快、内存占用小等特点。

总之，C++ 实现快速排序可以通过以上代码完成，而该算法在排序算法中占有一定的地位，具有实际应用意义。

上一篇: idea打包java可执行jar包

下一篇: 学习C++需了解数据结构吗？

()

相似文章