帮我写一个c++快速排序
时间: 2023-09-17 12:06:00 浏览: 153
c++快速排序
### 回答1:
很高兴为您服务!下面是这段C语言快速排序的代码: void quick_sort(int array[], int left, int right)
{
int i = left;
int j = right;
int pivot = array[(left + right) / 2];
int temp;
while (i <= j)
{
while (array[i] < pivot)
i++;
while (array[j] > pivot)
j--;
if (i <= j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (j > left)
quick_sort(array, left, j);
if (i < right)
quick_sort(array, i, right);
}
### 回答2:
快速排序是一种高效的排序算法,其基本思想是通过确定一个基准元素,将小于等于基准的元素放在左边,大于基准的元素放在右边,然后递归地对左右两部分分别进行快速排序。
以下是一个用C语言编写的快速排序算法的示例:
```c
#include <stdio.h>
// 交换两个元素的值
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 pivot = partition(arr, low, high); // 将数组分为两部分
quickSort(arr, low, pivot - 1); // 对左半部分进行快速排序
quickSort(arr, pivot + 1, high); // 对右半部分进行快速排序
}
}
// 打印数组
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组: \n");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}
```
以上代码实现了一个基本的快速排序算法,首先选择最后一个元素作为基准,然后通过递归对左右两个子数组进行排序,最后得到一个有序的数组。该算法的时间复杂度为O(nlogn),适用于大规模数据的排序。
### 回答3:
快速排序是一种高效的排序算法,其基本思想是将待排序的序列划分为两部分,左边部分的所有元素小于等于指定的枢纽元素,右边部分的所有元素大于等于指定的枢纽元素,然后分别对左右两部分进行递归排序,最后合并得到有序序列。
下面是一个用C语言实现的快速排序的示例代码:
```c
#include <stdio.h>
// 交换两个元素的值
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 获取枢纽元素的索引
int getPivotIndex(int arr[], int low, int high) {
int pivot = arr[low]; // 选择第一个元素作为枢纽元素
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
swap(&arr[low], &arr[high]);
while (low < high && arr[low] <= pivot) {
low++;
}
swap(&arr[low], &arr[high]);
}
return low;
}
// 快速排序
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = getPivotIndex(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int main() {
int arr[] = {53, 37, 65, 48, 23, 10, 99, 78};
int size = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, size - 1);
printf("排序结果:");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
以上代码首先定义了交换两个元素值和获取枢纽元素索引的辅助函数。然后,在快速排序函数中,选择第一个元素作为枢纽元素,通过一次划分操作将数组分成两部分,再递归地对左右两部分进行排序。最后,在主函数中调用快速排序函数对给定的数组进行排序,并输出排序结果。
运行以上代码,输出结果为:10 23 37 48 53 65 78 99,即为按升序排列的数组元素。
阅读全文