C语言实现快速排序算法实例

下面是“C语言实现快速排序算法实例”的完整攻略：

快速排序算法简介

快速排序是一种高效的排序算法，属于比较排序中的一种，采用分治策略，通过将原序列划分为若干个子序列依次排序，最终得到有序序列。该算法的平均时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n^2)，因此在实际应用中要根据数据规模和数据分布情况选择合适的算法。

C语言快速排序实现示例

下面我们通过C语言实现快速排序算法，具体思路如下：

1. 以序列中第一个元素为基准值，将序列划分为左右两个子序列；
2. 对左右子序列分别进行快速排序，直到子序列长度小于等于1；
3. 将子序列重新合并。

void quick_sort(int arr[], int left, int right) {
    if (left >= right) return;  // 子序列长度小于等于1，直接返回
    int pivot = arr[left];  // 以第一个元素为基准值
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;  // 从右往左扫描，找到第一个小于pivot的元素
        arr[i] = arr[j];  // 将小于pivot的元素移动到序列左边
        while (i < j && arr[i] <= pivot) i++;  // 从左往右扫描，找到第一个大于pivot的元素
        arr[j] = arr[i];  // 将大于pivot的元素移动到序列右边
    }
    arr[i] = pivot;  // 将基准值归位    
    quick_sort(arr, left, i - 1);  // 对左子序列进行快速排序
    quick_sort(arr, i + 1, right);  // 对右子序列进行快速排序
}

我们可以使用以下示例来测试快速排序的效果：

#include <stdio.h>

void quick_sort(int arr[], int left, int right);

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

输出结果为：1 2 3 4 5 6 7 8 9，满足我们的预期。

优化快速排序算法

快速排序的时间复杂度与待排序序列中选取的基准值有关，因此选取合适的基准值可以提高算法的效率。以下是选取三数中值作为基准值的示例代码：

void quick_sort(int arr[], int left, int right) {
    if (left >= right) return;

    // 选取三数中值作为基准值
    int mid = left + (right - left) / 2;  // 计算序列中间位置
    if (arr[left] > arr[right]) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
    if (arr[mid] > arr[right]) {
        int temp = arr[mid];
        arr[mid] = arr[right];
        arr[right] = temp;
    }
    if (arr[left] < arr[mid]) {
        int temp = arr[left];
        arr[left] = arr[mid];
        arr[mid] = temp;
    }

    int pivot = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) i++;
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}

我们使用以下示例测试优化后的快速排序算法：

#include <stdio.h>

void quick_sort(int arr[], int left, int right);

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

输出结果为：0 1 2 3 4 5 6 7 8 9，也满足我们的预期。

以上是对“C语言实现快速排序算法实例”的详细讲解和示例说明。