c语言快速排序算法示例代码分享

首先，我们需要了解什么是快速排序。快速排序（QuickSort）是一种排序算法，其采用了分治的思想，并使用递归的方式处理数据集合。它的基本思想是从待排序的数据集合中选择一个元素作为分界点（一般称为pivot），然后将小于pivot的元素放到pivot左边，大于pivot的元素放到pivot右边，最后将pivot放到中间位置。然后递归处理pivot左右两边的子数组，直到所有的元素都被遍历过为止。

下面我们来看一下C语言的快速排序示例代码：

#include <stdio.h>

//定义快速排序函数
void quickSort(int arr[], int low, int high) {
    int i, j, temp, pivot;
    if (low < high) {
        pivot = low;
        i = low;
        j = high;
        while (i < j) {
            //从右边开始找到第一个小于pivot的元素
            while (arr[j] > arr[pivot]) {
                j--;
            }
            //从左边开始找到第一个大于pivot的元素
            while (i < j && arr[i] <= arr[pivot]) {
                i++;
            }
            //交换i和j位置的元素
            if (i < j) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //将pivot移到中间位置
        temp = arr[pivot];
        arr[pivot] = arr[j];
        arr[j] = temp;
        //递归处理pivot左右两边的子数组
        quickSort(arr, low, j - 1);
        quickSort(arr, j + 1, high);
    }
}

//测试代码
int main() {
    int arr[] = { 5, 1, 9, 3, 7, 4, 8, 6, 2 };
    int len = sizeof(arr) / sizeof(*arr);
    printf("Original array: ");
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    quickSort(arr, 0, len - 1);
    printf("Sorted array: ");
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

该示例代码中，我们自定义了一个快速排序函数quickSort()，传入数组arr、数组最小索引值low、数组最大索引值high三个参数，用于处理待排序的数组。

在函数内部，我们首先判断low是否小于high，如果是，则进行一些操作。接着定义pivot作为我们选择的分界点，i和j分别代表数组左右两个指针位置，开始从arr[low]作为pivot，然后我们从右边开始找到第一个小于pivot的元素，从左边开始找到第一个大于pivot的元素，然后交换i和j位置的元素，直到i和j相遇。最后将pivot移到中间位置，并递归处理pivot左右两边的子数组。

我们在main()函数中调用了quickSort()函数来实现排序。在测试代码中，我们定义了一个整型数组arr，并打印了原始顺序的数组arr，随后调用quickSort()函数对该数组进行排序，并打印排序后的结果。

下面我们来看看快速排序的算法复杂度：

最优情况下，时间复杂度为O(nlogn)。

最坏情况下，时间复杂度为O(n^2)。

平均情况下，时间复杂度为O(nlogn)。

下面我将会给出另一条示例：

#include<stdio.h>

//定义快速排序函数
void quickSort(int arr[], int left, int right) {
    if (left<right){
        int i = left, j = right, pivot = arr[left];
        while (i<j)
        {
            while (i<j&&arr[j]>=pivot)j--;//从右向左找第一个小于x的数  
            if (i<j)
            arr[i++] = arr[j];
            while (i<j&&arr[i]<pivot)i++;//从左向右找第一个大于等于x的数  
            if (i<j)
            arr[j--] = arr[i];
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

//测试代码
int main(){
    int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
    int len = sizeof(arr) / sizeof(*arr);
    printf("Original array:");
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    quickSort(arr, 0, len - 1);
    printf("Sorted array:");
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

该示例与上一条示例代码类似，同样是通过一次扫描数组递归处理的方式进行排序。但是该示例对于右端点元素的选择略有不同，这次我们选择了数组的最左端点元素为枢轴。又在交换元素时进行了优化。

属于一种更灵活的实现方式。

我们可通过执行该示例代码来检验一下结果是否与预期相符。

以上就是C语言快速排序算法示例代码的分享内容，希望能够帮助到大家。