快速排序 C++ 代码

### 回答1：

我们可以使用快速排序法来排序C代码，具体的代码实现可以参考下面的示例：int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

### 回答2：
快速排序是一种常用的排序算法，其思想是通过一趟排序将待排序的序列分割成独立的两部分，其中一部分的所有元素都比另一部分小。然后再对这两部分分别进行快速排序，最终得到有序序列。

下面是一个用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 left = low, right = high;
    
    while (left < right) {
        // 从右向左找第一个比基准值小的元素
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        // 从左向右找第一个比基准值大的元素
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        // 交换这两个元素的位置
        if (left < right) {
            swap(&arr[left], &arr[right]);
        }
    }
    // 将基准值与 left 和 right 相遇的位置交换
    swap(&arr[low], &arr[left]);
    
    return left;
}

// 快速排序
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[] = {9, 5, 2, 7, 1, 8, 4, 3, 6};
    int length = sizeof(arr) / sizeof(arr[0]);
    
    quickSort(arr, 0, length - 1);
    
    printf("排序结果：");
    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

以上代码中，`swap`函数用于交换两个元素的位置，`partition`函数用于将数组划分为两部分，并返回基准值的最终位置，`quickSort`函数用于进行快速排序。在`main`函数中，我们定义一个数组并进行快速排序，最后输出排序结果。

该快速排序算法的时间复杂度为O(nlogn)，空间复杂度为O(logn)。

### 回答3：
快速排序是一种常用的排序算法，它的思想是通过选取一个基准元素将待排序序列分成两个子序列，然后递归地对子序列进行排序，最终得到有序的序列。

下面是一个用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[low];  // 选取第一个元素作为基准元素
    int i = low, j = high;
    
    while(i < j){
        // 从右往左找到第一个小于基准元素的元素
        while(i < j && array[j] >= pivot){
            j--;
        }
        // 从左往右找到第一个大于基准元素的元素
        while(i < j && array[i] <= pivot){
            i++;
        }
        // 交换找到的两个元素
        if(i < j){
            swap(&array[i], &array[j]);
        }
    }
    
    // 将基准元素放到正确的位置
    array[low] = array[i];
    array[i] = pivot;
    
    return i;
}

// 快速排序算法
void quickSort(int array[], int low, int high){
    if(low < high){
        int pivotPos = partition(array, low, high);
        quickSort(array, low, pivotPos - 1);
        quickSort(array, pivotPos + 1, high);
    }
}

int main(){
    int array[] = {3, 7, 2, 9, 1, 5, 10, 8, 4, 6};
    int n = sizeof(array) / sizeof(array[0]);
    
    quickSort(array, 0, n - 1);
    
    printf("排序后的数组：");
    for(int i = 0; i < n; i++){
        printf("%d ", array[i]);
    }
    printf("\n");
    
    return 0;
}

在这段代码中，`partition`函数用于将基准元素放到正确的位置，并返回它的下标。`quickSort`函数则实现了递归地对子序列进行排序。最后，在`main`函数中，我们定义一个待排序的数组，并调用`quickSort`函数进行排序。最终输出排序后的数组。

快速排序的时间复杂度为O(n log n)，其中n是待排序序列的长度。因此，它是一种高效的排序算法。