C语言简单实现快速排序

C语言简单实现快速排序

什么是快速排序？

快速排序（Quicksort）是一种分治的排序算法，由Tony Hoare于1960年提出。快速排序使用两个指针i,j分别指向待排序数组的最左侧和最右侧，以一个值作为基准（pivot），一般为数组的中间值。快速排序的主要思路是将数组中小于基准值的数放到基准值左边，将大于基准值的数放到右边。然后通过递归的方式，对左右两个子数组分别进行排序，直到整个数组有序。

算法实现

以下是快速排序的一个简单实现：

void quick_sort(int arr[], int left, int right) {
    if(left >= right) return; // 当left >= right时，递归到底，返回
    int i = left, j = right, pivot = arr[(left + right) / 2]; // 初始化左右指针i,j，以及基准值pivot
    while(i <= j) { // 当i <= j时，执行以下循环体
        while(arr[i] < pivot) i++; // 从左边开始找比基准值大的数，找到则停止
        while(arr[j] > pivot) j--; // 从右边开始找比基准值小的数，找到则停止
        if(i <= j) { // 如果i <= j，则交换arr[i]和arr[j]的值
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    quick_sort(arr, left, j); // 对左子数组进行递归排序
    quick_sort(arr, i, right); // 对右子数组进行递归排序
}

示例说明

以下是一个使用快速排序的示例：

#include <stdio.h>

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

int main() {
    int i, arr[10] = {5, 3, 7, 1, 2, 4, 9, 8, 6, 0};
    quick_sort(arr, 0, 9);
    for(i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

void quick_sort(int arr[], int left, int right) {
    if(left >= right) return;
    int i = left, j = right, pivot = arr[(left + right) / 2];
    while(i <= j) {
        while(arr[i] < pivot) i++;
        while(arr[j] > pivot) j--;
        if(i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    quick_sort(arr, left, j);
    quick_sort(arr, i, right);
}

输出结果为：

0 1 2 3 4 5 6 7 8 9 

以下是另一个使用快速排序的示例：

#include <stdio.h>

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

int main() {
    int i, arr[5] = {5, 1, 3, 4, 2};
    quick_sort(arr, 0, 4);
    for(i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

void quick_sort(int arr[], int left, int right) {
    if(left >= right) return;
    int i = left, j = right, pivot = arr[(left + right) / 2];
    while(i <= j) {
        while(arr[i] < pivot) i++;
        while(arr[j] > pivot) j--;
        if(i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    quick_sort(arr, left, j);
    quick_sort(arr, i, right);
}

输出结果为：

1 2 3 4 5 

以上两个示例都展示了使用快速排序对一个整型数组进行升序排序的过程。当然，快速排序同样可以用于其他类型的数据，只需要更改排序函数的参数类型即可。