c语言快速排序 c语言快速排序算法

C语言快速排序算法详解

快速排序是一种高效的排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的，下面详细介绍C语言实现快速排序的方法。

1、算法原理

快速排序采用分治法策略，其基本步骤如下：

（1）选择一个基准元素pivot。

（2）通过一趟排序将待排序的数据分割成两个子序列，使得其中一个子序列的所有数据都比另一个子序列的所有数据都要小。

（3）然后再按此方法对这两个子序列分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

2、C语言实现

下面是C语言实现快速排序的代码：

#include <stdio.h>
void quick_sort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left, j = right, pivot = arr[left];
    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);
}
int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quick_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

3、算法分析

（1）最佳情况：每次划分都能使枢轴元素左右两边的元素个数相等，即nlogn。

（2）最坏情况：每次划分都使枢轴元素左右两边的元素个数相差1，即n^2，但是这种情况发生的概率较小，因为可以通过随机选择枢轴元素来降低这种概率。

（3）平均情况：时间复杂度为O(nlogn)。