用c++写个快速排序

### 回答1：

我可以为你编写一个快速排序的C程序：#include <stdio.h>
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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
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);
}
}

void printArray(int arr[], int size)
{
for (int i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}

### 回答2：
快速排序是一种常用的排序算法，它使用分治的思想将一个数组按照某个基准值划分为两部分，然后分别对这两部分进行递归排序。具体的步骤如下：

1. 首先，选择一个基准值。可以选择数组的第一个元素作为基准值。

2. 将数组分为两部分，使得左边的元素都比基准值小，右边的元素都比基准值大。

3. 递归地对左边和右边的子数组进行快速排序，直到子数组的长度为1或0。

4. 合并排序后的子数组。

以下是使用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 && i < j) {
            j--;
        }
        // 从左往右找第一个比基准值大的元素
        while (arr[i] <= pivot && i < j) {
            i++;
        }
        // 交换找到的两个元素
        swap(&arr[i], &arr[j]);
    }
    
    // 将基准值放到正确的位置
    swap(&arr[low], &arr[i]);
    
    return i;
}

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[] = {5, 3, 8, 4, 2};
    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;
}

以上是一个简单的使用C语言实现的快速排序程序。使用基准值将数组分为两部分，然后分别对这两部分进行递归排序，最后将排序后的子数组进行合并，即可得到一个有序的数组。

### 回答3：
快速排序是一种常用的排序算法，使用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 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[] = {24, 18, 38, 43, 32, 9, 12};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组：");
    printArray(arr, size);
    
    quickSort(arr, 0, size - 1);
    
    printf("排序后的数组：");
    printArray(arr, size);
    
    return 0;
}

以上就是用C语言实现快速排序的代码，运行结果为：
原始数组：24 18 38 43 32 9 12
排序后的数组：9 12 18 24 32 38 43

快速排序的时间复杂度为O(nlogn)，是一种非常高效的排序算法。