C++ Quick Sort数组代码怎么写?
时间: 2023-08-31 21:27:12 浏览: 58
### 回答1:
快速排序数组代码的实现可以如下: def quickSort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quickSort(left) + middle + quickSort(right)
### 回答2:
快速排序(Quick Sort)是一种常用的排序算法。它基于分治的思想,将一个未排序的数组按照主元(pivot)的大小分为两部分,较小的部分在左边,较大的部分在右边。然后对这两部分分别进行快速排序,直到所有的子数组都有序。
以下是一种通用的C语言实现快速排序的代码:
```c
// 交换两个元素的值
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);
printf("排序后的数组:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
以上代码中,`swap`函数用于交换两个元素的值。`partition`函数选取主元,将小于主元的值移到主元的左边,大于主元的值移到主元的右边,并返回主元的位置。`quickSort`函数是快速排序的递归函数,根据主元将数组分为两部分,分别对这两部分进行快速排序。`main`函数用于测试快速排序的结果。
这段代码中的数组为{64, 25, 12, 22, 11},经过快速排序后的结果为{11, 12, 22, 25, 64}。
### 回答3:
快速排序(Quick Sort)是一种经典的排序算法,其基本思想是通过将数组划分成较小和较大的两部分,分别对这两部分进行排序,最终实现整个数组的有序。
下面是使用C语言实现快速排序的代码:
```c
#include <stdio.h>
// 交换两个元素的值
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); // 对基准元素右边的子数组进行快速排序
}
}
// 测试函数
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
该代码首先定义了一个swap函数,用于交换数组中两个元素的值。然后,在partition函数中选择最后一个元素作为基准元素,将数组划分为小于基准的一部分和大于基准的一部分,并返回基准元素的正确位置。
最后,quickSort函数采用递归的方式,对基准左侧和右侧的子数组进行快速排序。在main函数中,我们可以输入需要排序的数组,并输出排序后的结果。
注意,该代码实现的是升序排序,如果需要降序排序,只需修改partition函数中的比较符号即可。