C语言中快速排序法的代码实现

好的，以下是C语言中快速排序法的代码实现：

void quick_sort(int arr[], int left, int right) {
    int i, j, pivot;

    if (left < right) {
        pivot = arr[left];
        i = left;
        j = right;

        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;
        quick_sort(arr, left, i - 1);
        quick_sort(arr, i + 1, right);
    }
}

希望能够帮到你！接下来，让我们来聊聊别的问题吧。

相关问题

使用C语言实现快速排序法

好的，以下是使用 C 语言实现快速排序算法的代码：

#include <stdio.h>
#include <stdlib.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quick_sort(int arr[], int start, int end) {
    if (start >= end) {
        return;
    }
    
    int pivot = arr[end];
    int i = start - 1;
    
    for (int j = start; j <= end - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[end]);
    
    quick_sort(arr, start, i);
    quick_sort(arr, i+2, end);
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    quick_sort(arr, 0, n-1);
    
    printf("Sorted Array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

在该实现中，我们选取数组中的一个元素作为中心点（pivot），然后将数组分为小于 pivot 和大于 pivot 的两个部分。接着，我们对这两个部分分别递归地进行上述操作，直到所有部分都只有一个元素。

在递归过程中，我们使用 i 变量来记录当前小于 pivot 的元素的最右侧位置。在遍历数组时，如果遇到小于 pivot 的元素，则将其与 i+1 位置的元素进行交换，并将 i 向右移动一个位置。最后，我们将 pivot 放在 i+1 的位置上，并递归地对小于 pivot 和大于 pivot 的两部分继续进行快速排序。

该实现的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。

用C语言实现快速排序代码

### 回答1：

下面是一个用C语言实现的快速排序代码： void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];

/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};

/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}

### 回答2：
快速排序（Quick Sort）是一种经典的排序算法，使用分治的思想。下面是用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; 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[] = {9, 5, 2, 7, 6, 1, 3, 8, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quickSort(arr, 0, n - 1); // 调用快速排序函数

    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

上述代码是用C语言实现了快速排序算法。快速排序的核心思想是通过选择一个中轴元素，将数组划分为两部分，左边的元素都小于中轴元素，右边的元素都大于中轴元素，然后递归地对划分出来的两部分进行排序，最终得到一个有序数组。快速排序的时间复杂度为O(nlogn)。

### 回答3：
快速排序（Quicksort）是一种常用的排序算法，它采用了分治法的思想，通过将一个数组分成两个子数组，再分别对这两个子数组进行递归排序，最终将整个数组排序。

以下是用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);  // 对分割的右子数组递归排序
    }
}

int main() {
    int arr[] = {5, 1, 9, 3, 7, 6, 2, 8, 4};
    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函数中，我们定义了一个待排序的数组，然后调用quickSort函数进行排序，并打印出排序后的结果。