在C++中实现快速排序的代码如下:
#include <iostream>
using namespace std;
// 交换两个元素的值
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 将数组分区,并返回分区点的索引
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);
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "排序后的数组:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
快速排序是一种高效的排序算法,其时间复杂度为O(nlogn)。它通过选择一个分区点(通常选择最后一个元素),将数组分为两部分,一部分小于等于分区点,一部分大于分区点,然后对这两部分进行递归排序,最终得到有序数组。
快速排序的优势在于其高效性和原地排序特性,不需要额外的存储空间。它适用于大规模数据的排序,并且在实践中通常比其他排序算法表现更好。
在腾讯云中,可以使用云服务器(CVM)来运行C++代码。您可以通过以下链接了解腾讯云云服务器的相关产品和产品介绍:腾讯云云服务器
请注意,以上答案仅供参考,实际情况可能因环境和需求而异。
云+社区技术沙龙 [第31期]
云原生正发声
云+社区沙龙online [技术应变力]
云+社区沙龙online [技术应变力]
领取专属 10元无门槛券
手把手带您无忧上云