用c++写一个快速排序
时间: 2023-08-31 12:39:57 浏览: 53
### 回答1:
以下是使用C语言编写的快速排序示例代码:
```
#include <stdio.h>
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left < j) {
quickSort(arr, left, j);
}
if (i < right) {
quickSort(arr, i, right);
}
}
int main() {
int arr[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
此示例中的 `quickSort` 函数使用了递归来完成快速排序。它首先选择一个轴点(即数组的中间元素)并将其存储在 `pivot` 变量中。然后,它将数组分成两部分:左侧部分包含小于 `pivot` 的元素,右侧部分包含大于 `pivot` 的元素。接下来,它使用递归对左侧和右侧部分进行快速排序。最终,整个数组将按升序排列。
### 回答2:
快速排序(Quick Sort)是一种经典的排序算法,使用分治的思想来完成排序过程。以下是用C语言编写的快速排序算法示例:
```c
#include<stdio.h>
// 快速排序
void quickSort(int arr[], int left, int right) {
if (left < right) {
int i = left, j = right;
int pivot = arr[left]; // 基准值设为数组第一个元素
while (i < j) {
// 从右向左找小于基准值的元素
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
// 从左向右找大于基准值的元素
while (i < j && arr[i] < pivot) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot; // 将基准值插入到正确的位置
// 递归排序基准值左边的子数组
quickSort(arr, left, i - 1);
// 递归排序基准值右边的子数组
quickSort(arr, i + 1, right);
}
}
int main() {
int arr[] = {9, 2, 5, 1, 7, 6, 3, 8, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序前的数组:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
quickSort(arr, 0, n - 1);
printf("\n排序后的数组:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
以上代码实现了一个快速排序算法。快速排序是通过选择一个基准值,将数组分为两部分,并递归地对这两部分进行排序。在具体的实现中,通过两个指针分别从数组的两端向中间移动,找到两个需要交换的元素,然后交换它们的位置。最终将基准值放置到正确的位置,然后递归排序左右两个子数组。最终得到有序的数组。快速排序的时间复杂度为O(nlogn)。
### 回答3:
快速排序是一种常用的排序算法,通过递归地将数组不断分割为较小和较大的两个子数组,最终完成整个数组的排序。
首先,选择一个基准元素,可以是数组中的任意一个元素。然后,将数组中小于基准元素的数放在其左边,大于基准元素的数放在其右边。这个过程被称为分割。
接下来,对左右两个子数组递归地进行分割操作,直到每个子数组只剩下一个元素或为空。
以下是使用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);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
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]);
}
return 0;
}
```
以上代码实现了一个快速排序算法。通过调用`quickSort`函数来完成对整个数组的排序,最终输出排序后的结果。在输入数组`arr`和其起始和结束位置`low`和`high`的基础上,使用`partition`函数进行分割操作,并递归地处理左右子数组。最终,通过不断地分割和排序,完成整个数组的快速排序。