C程序 快速排序

C程序 快速排序使用攻略

概述

快速排序（Quicksort）是一种基于分治思想的排序算法，是最常用的排序算法之一。它的核心思想是通过一次排序将待排序序列分成两个子序列，其中一个子序列的所有元素都比另外一个子序列的所有元素小，接着对子序列继续递归进行快速排序，最终得到有序序列。

代码示例

下面是快速排序算法的C语言实现：

void quicksort(int a[], int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = a[left];
    int i = left + 1;
    int j = right;
    while (i <= j) {
        if (a[i] > pivot && a[j] < pivot) {
            swap(&a[i], &a[j]);
            i++;
            j--;
        } else if (a[i] <= pivot) {
            i++;
        } else if (a[j] >= pivot) {
            j--;
        }
    }
    swap(&a[left], &a[j]);
    quicksort(a, left, j - 1);
    quicksort(a, j + 1, right);
}

函数参数中，a是待排序数组，left是数组左端点下标，right是数组右端点下标。在函数中，首先判断是否需要进行排序，然后选取左端点作为枢轴元素（pivot），从左端点向右扫描（i），从右端点向左扫描（j），在扫描的过程中，将比枢轴元素大的数交换到右边，将比枢轴元素小的数交换到左边，一直扫描到i > j 为止，最后将枢轴元素和a[j]交换并且递归调用quicksort函数。

使用示例

示例1

假设有一个待排序数组a，长度为5，内容为{3, 1, 5, 4, 2}，如何使用快速排序算法进行排序？

int a[] = {3, 1, 5, 4, 2};
int n = sizeof(a) / sizeof(a[0]);
quicksort(a, 0, n - 1);
for (int i = 0; i < n; i++) {
    printf("%d ", a[i]);
}

输出结果为：1 2 3 4 5。

示例2

假设有一个待排序的字符数组str，长度为7，内容为{"hello", "world", "apple", "banana", "cat", "dog", "zebra"}，如何使用快速排序算法将字典序最小的前3个字符串输出？

char* str[] = {"hello", "world", "apple", "banana", "cat", "dog", "zebra"};
int n = sizeof(str) / sizeof(str[0]);
quicksort_string(str, 0, n - 1);
for (int i = 0; i < 3; i++) {
    printf("%s\n", str[i]);
}

需要注意的是，字符串数组的排序需要使用另外一个函数quicksort_string，其实现如下：

void quicksort_string(char* str[], int left, int right) {
    if (left >= right) {
        return;
    }
    char* pivot = str[left];
    int i = left + 1;
    int j = right;
    while (i <= j) {
        if (strcmp(str[i], pivot) < 0 && strcmp(str[j], pivot) > 0) {
            swap_string(&str[i], &str[j]);
            i++;
            j--;
        } else if (strcmp(str[i], pivot) >= 0) {
            i++;
        } else if (strcmp(str[j], pivot) <= 0) {
            j--;
        }
    }
    swap_string(&str[left], &str[j]);
    quicksort_string(str, left, j - 1);
    quicksort_string(str, j + 1, right);
}

其中使用了strcmp函数来进行字符串比较，swap_string函数用于交换字符串指针。