C语言实现快速排序算法

C语言实现快速排序算法攻略

什么是快速排序算法

快速排序算法是一种常用的排序算法, 它使用递归的方式不断地将待排序序列分为两个部分，直到每个子序列中只有一个元素，最终合并完成整个序列的排序。

步骤

快速排序算法的步骤如下：

1. 从序列中选取一个基准元素
2. 将所有小于基准元素的元素放到基准元素左边，大于基准元素的元素放到基准元素右边
3. 对基准元素左右两个子序列分别执行上述两个步骤，直到每个子序列中只有一个元素

代码实现

以下是C语言实现快速排序算法的代码

void quicksort(int a[], int left, int right){
    int i, j, t, pivot;

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

示例说明

假设有以下待排序数组

int a[] = {3, 7, 2, 9, 1, 4, 6, 8, 5};

1. 选取基准元素为a[0], 即3
2. 将小于3的数放到左边，大于3的数放到右边, 得到以下序列

{2, 1, 3, 9, 7, 4, 6, 8, 5}

1. 分别对左右两个子序列执行上述两个步骤, 直到每个子序列中只有一个元素, 序列变为

{1, 2, 3, 4, 5, 6, 7, 8, 9}

另外，下面是利用快速排序算法实现搜索一个未排序数组中第k大的元素的示例代码

int find_kth_largest(int a[], int len, int k){
    int left = 0, right = len - 1;
    int i, t, pivot;

    while(left <= right){
        pivot = a[left];
        i = left;
        for(int j = left + 1; j <= right; j++){
            if(a[j] > pivot){
                i++;
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        t = a[i];
        a[i] = a[left];
        a[left] = t;

        if(i == k - 1)
            return a[i];
        else if(i < k - 1)
            left = i + 1;
        else
            right = i - 1;
    }
    return -1;
}

可以通过以下方式调用函数

int a[] = {3, 7, 2, 9, 1, 4, 6, 8, 5};
int len = sizeof(a)/sizeof(a[0]);
int k = 4;
int kth_largest = find_kth_largest(a, len, k);
printf("第%d大元素是%d\n", k, kth_largest);

假设k = 4，输出应为

第4大元素是6

总结

快速排序算法是一个高效的排序算法，相信通过上述讲解，读者对它有了更深刻的理解。当然，快速排序也有一些局限性，例如，当待排序序列基本有序或逆序时，算法复杂度会退化为O(n^2)，因此在应用时需要根据具体情况综合考虑。