用c++写一个快速排序
时间: 2023-09-09 10:05:22 浏览: 56
### 回答1:
好的,我可以写一个快速排序的程序:// 快速排序函数
void QuickSort(int array[], int left, int right) {
int i = left, j = right;
int pivot = array[(left + right) / 2];
while (i <= j) {
while (array[i] < pivot)
i++;
while (array[j] > pivot)
j--;
if (i <= j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (left < j)
QuickSort(array, left, j);
if (i < right)
QuickSort(array, i, right);
}
### 回答2:
快速排序是一种常用且高效的排序算法,使用递归的方式实现。
首先,选择一个基准元素作为比较的标准,通常是选择数组的第一个元素。接下来,遍历整个数组,将比基准元素小的元素放在左边,大于基准元素的元素放在右边。最后,递归地对左右两部分进行排序,直到每个子数组只有一个元素。
下面是使用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[low]; // 选择第一个元素作为基准
int i = low, j = high;
while (i < j) {
// 找到右边第一个比基准小的元素
while (arr[j] > pivot) {
j--;
}
// 找到左边第一个比基准大的元素
while (arr[i] <= pivot) {
i++;
}
if (i < j) {
swap(&arr[i], &arr[j]); // 交换这两个元素的值
}
}
// 把基准元素放到正确的位置上
arr[low] = arr[j];
arr[j] = pivot;
return j; // 返回基准元素的索引
}
// 快速排序
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high); // 分割数组
quickSort(arr, low, pivotIndex - 1); // 对左半部分排序
quickSort(arr, pivotIndex + 1, high); // 对右半部分排序
}
}
int main() {
int arr[] = {10, 2, 7, 8, 9, 1, 5};
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;
}
```
这段代码中,使用`partition`函数分割数组,并获取基准元素的索引。然后,递归地对左半部分和右半部分进行快速排序。最后,打印排序结果。
运行上述代码,输出结果为:1 2 5 7 8 9 10,即对数组进行了升序排序。
### 回答3:
快速排序(Quicksort)是一种常用的排序算法,基于分治思想。下面是用C语言实现的快速排序的代码:
```c
#include<stdio.h>
void swap(int* a, int* b){
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int array[], int low, int high){
int pivot = array[high];
int i = (low - 1);
for(int j = low; j <= high - 1; j++){
if(array[j] < pivot){
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i+1], &array[high]);
return (i+1);
}
void quickSort(int array[], int low, int high){
if(low < high){
int pi = partition(array, low, high);
quickSort(array, low, pi-1);
quickSort(array, pi+1, high);
}
}
int main(){
int array[] = {5, 2, 6, 8, 3};
int n = sizeof(array) / sizeof(array[0]);
quickSort(array, 0, n-1);
printf("排序后的数组:");
for(int i = 0; i < n; i++){
printf("%d ", array[i]);
}
return 0;
}
```
这个快速排序算法的过程如下:
1. 选取数组中的一个元素作为枢纽元(pivot),一般选择最后一个元素。
2. 对数组进行划分,将小于枢纽元的元素放在枢纽元的左边,大于枢纽元的元素放在右边。
3. 对枢纽元左边和右边的子数组分别递归地进行快速排序。
4. 当子数组的长度只有1或0时,递归终止,排序完成。
以上给出的代码通过交换数组元素的方式实现快速排序,可以将输入数组{5, 2, 6, 8, 3}排序为{2, 3, 5, 6, 8}。