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

快速排序（Quick Sort）是一种经典的排序算法，在计算机科学领域被广泛使用。它的思想是通过选择一个数作为枢轴（pivot），将所有小于枢轴的数放在它的左边，将大于枢轴的数放在它的右边，然后递归地对左右两部分进行排序，以达到整个数组有序的目的。快速排序的平均时间复杂度为O(nlogn)，具有较好的性能表现。

快速排序算法步骤

1. 选择一个枢轴元素（可以是数组的第一个元素）。
2. 将数组分为两部分，比枢轴元素小的放在左边，比枢轴元素大的放在右边。
3. 递归地对左右两部分进行快速排序。
4. 合并左右两部分得到有序的数组。

C语言实现快速排序

下面是用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;         // 枢轴元素的位置
    int right = high + 1;

    while (1) {
        while (arr[++left] < pivot && left < high);
        while (arr[--right] > pivot && right > low);
        if (left >= right)  // 交叉过界，退出循环
            break;
        else                // 交换左右元素
            swap(&arr[left], &arr[right]);
    }
    swap(&arr[low], &arr[right]);   // 枢轴元素归位
    return right;
}

// 快速排序
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotPos = partition(arr, low, high);// 划分
        quickSort(arr, low, pivotPos - 1);    // 对左半部分排序
        quickSort(arr, pivotPos + 1, high);   // 对右半部分排序
    }
}

// 测试排序结果
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    printf("Sorted array: ");
    printArray(arr, size);
    
    return 0;
}

输出结果为：

Original array: 10 80 30 90 40 50 70
Sorted array: 10 30 40 50 70 80 90

总结

快速排序是一种高效的排序算法，通过不断地递归划分数组来实现排序。它的平均时间复杂度为O(nlogn)，具有较好的性能表现。在实际开发中，如果需要对一个数组进行排序，可以考虑使用快速排序算法。