C语言快速排序代码（带有注释和解析）

快速排序是一种高效的排序算法，平均时间复杂度为O(n log n)，由 C. A. R. Hoare 在 1960 年提出。它采用分治法的策略，将数据分为较小和较大的两部分，然后递归地排序这两部分。

算法原理

快速排序的基本思想是选择一个元素作为基准（pivot），通过一趟排序将数据分为两部分，使得左边的元素都不大于基准，右边的元素都不小于基准。这个过程称为分区（partitioning）。

算法步骤

对一组数据（存储在数组中）进行排序：

• 选择基准：在数组中选一个基准数（通常为数组第一个，黄圈圈标记了）；
• 初始化哨兵：设置两个指针 i 和 j，分别指向数组的开始和结束。
• 分区操作：通过移动i和j，将小于基准的元素移到左边，大于基准的元素移到右边。
• 递归排序：对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。

具体实现

快速排序需要两个哨兵，i 和 j，它们分别指向数组的头和尾。


接下来就要进行移动。

我们通常选择第 1 个元素作为基准数，去移动数组元素，使其达到这个基准数的左边都是小于它的，右边都是大于它的。

开始移动 i 和 j , i 和 j 是交互移动的，这里我们需要先移动 j，这是为什么呢？原因是先移动 j，等到这一行移动结束，i 的下一个就是 j 的时候，我们先移动 j，可以避免将数据移动错误，后面会有体会。

当移动 j 时，就开始比较 j 是否比基准数大，如果大于或者等于就 j–，否则再看 i，如果 i 小于等于 6，则 i++ 再与基准数进行比较,否则 i 就要与 j指向的值互换，我们拿上面那个看。

第一步：看 j 的值比 6 小，然后看 i，i 的值是 6，所以 i++，后面 i 继续++，4、3、5 都比6小，所以 i 就移动到了 7 下面。


到这里，j 所指向的值要与 i 所指向的值互换。


互换完成，后面在比较 j 所指向的位置是否比基准数大，如果大就 j–。这里 7、9 都比 6 大，所以 j–，进行两次，j 就到达了 4 的下面。


4 比 6 小，所以要再看 i，i 指向 0，所以 i 需要 i++，到 1，1 也小于 6，所以 i 还需要 ++，到这里 i 就和 j 指向同一个数 4。


然后 i = j 了，不能够满足条件，所以就要进行互换，将 i 指向的数，与基准数互换，这一轮比较就结束了。


到这里，基准数 6 的左边都比 6 小，右边都比 6 大。后面还是按照这个来分别再基准数 6 的左右开始比较。


后面就找这样来，在左右两边再各自将第一个元素作为基准数进行排序。

以此类推，就可以了，具体的C语言代码如下：

#include <stdio.h>

#define SIZE 6

//快速排序
void quick_sort(int num[], int low, int high )
{
    int i,j,temp;
    int tmp;

    i = low;
    j = high;
    tmp = num[low];   //任命为中间分界线，左边比他小，右边比他大，通常第一个元素是基准数

    if(i > j)  //如果下标i大于下标j，函数结束运行
    {
        return;
    }

    while(i != j)
    {
        while(num[j] >= tmp && j > i)  
        {
            j--;
        }

        while(num[i] <= tmp && j > i)
        {
            i++;
        }

        if(j > i)
        {
            temp = num[j];
            num[j] = num[i];
            num[i] = temp;
        }
    }

    num[low] = num[i];
    num[i] = tmp;

    quick_sort(num,low,i-1);
    quick_sort(num,i+1,high);
}

//主函数，用于测试快速排序
int main(int argc , char **argv)
{
    //创建一个数组
    int num[SIZE] ={0};
    int i;

    //输入数字
    for(i =0; i < SIZE; i++)
    {
        scanf("%d",&num[i]);
    }

    quick_sort(num, 0, SIZE-1);

    //输出排序后的数组
    for(i = 0; i < SIZE; i++)
    {
        printf(" %d ", num[i]);
    }

    return 0;
}

快速排序与其他排序算法的比较

• 与归并排序：快速排序在大多数情况下比归并排序更快，但最坏情况下的时间复杂度为 O(n^2)，而归并排序始终保持 O(n log n)。
• 与堆排序：快速排序的平均性能通常优于堆排序，但堆排序的最坏情况时间复杂度为 O(n log n)。

F&Q

Q：快速排序在什么情况下效率最低？
A：当输入数组已经有序或接近有序时，快速排序的效率会降低。

Q：如何避免快速排序的最坏情况？
A：通过随机选择基准或使用其他启发式方法来选择基准，可以避免最坏情况的发生。

声明：《C语言系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。