快速排序算法


设计

快速排序的原理是在要排序的数列中找到一个基准数k(一般选取第一个),然后将这个待排序的数列中小于k的数字全部移到k的左边,大于k的数字全部移到k的右边。这样我们就得到了两个数列,再对以上两个数列重复上面的操作,直到全部排序完成,再组合成一个数列即可。

代码

#include <stdio.h>

/*按序输出数组元素*/
void display(int *a, int length)
{
    for (int i = 0; i < length; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

/*快速排序算法*/
void quick_sort(int *a, int low, int high)
{
    if (low < high)
    {
        int i = low, j = high;
        int k = a[i];
        while (i < j)
        {
            while (a[j] >= k && i < j)
                j--;
            if (i < j)
                a[i++] = a[j];
            while (a[i] <= k && i < j)
                i++;
            if (i < j)
                a[j--] = a[i];
        }
        a[i] = k;
        quick_sort(a, low, i - 1);
        quick_sort(a, i + 1, high);
    }
}

int main()
{
    int length;
    printf("请输入要排序的元素个数:");
    scanf("%d", &length);
    int a[length];
    printf("请输入各元素的值:");
    for (int i = 0; i < length; ++i)
    {
        scanf("%d", &a[i]);
    }
    printf("原顺序为:");
    display(a, length);
    quick_sort(a, 0, length - 1);
    printf("快速排序后的顺序为:");
    display(a, length);

    return 0;
}

分析

快速排序的时间复杂度变化较大,在最坏的情况下yu冒泡排序一样,为$O(n^2)$,这种情况下每次比较都需要交换。平均时间复杂度和最优时间复杂度都是$O(n\log{n})$。

最优情况下的空间复杂度为$O(\log{n})$,最差情况下为$O(n)$。


文章作者: 恰醋
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 恰醋 !
评论
  目录