C语言编程实例：8、快速排序算法

用快速排序法对一组数据由小到大进行排序，数据分别为 99、45、12、36、69、22、62、 796、4、696。

算法描述：

快速排序算法的基本原理为通过一次排序将要排序的数据分割成独立的两部分，将序列分为两部分的中间数作为基准(par)，基准左边的数都要比基准右边的数要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法执行过程分析：

例如：8，15，26，18，7，66，44
分析：依靠基准将序列分割为两部分，那么基准如何找到呢？？？？？？
方法有三种：

固定位置选取基准法
随机选取基准法
三分取中法
具体步骤：
一次取基准(par)过程：设置一个临时变量temp，并以第一个数作为temp的值，设置两个指针low和high。low指向序列的起始位置，high指向序列的最后一个元素。首先我们用high指向的元素和temp进行比较，如果大于，指针回退，直到high指向的元素值小于temp，然后让low指向的值赋值为high的值。这时让low指向的元素和temp比较，如果low指向的元素小于temp，指针前进，直到low指向的元素值大于temp。这时让high指向的值赋值为low指向的值，接下来对high重复上述操作，直到high和low相遇。此时的位置就是基准的位置par，最后此位置赋值temp。（具体可依据下图进行分析）

说明：

下图每一步为指针的循环操作，直至不符合条件，并且进行赋值变换后的结果。
上述一次取基准的过程采用了固定位置选取基准法。（另外两种方法后面将进行介绍）

然后对左右两部分子序列继续进行此步骤。（如果子序列为单个数时，说明自身有序，不进行此过程）

实现过程：
(1) 自定义一个函数，实现直接插入排序，在本实例中，我们自定义该函数为 insort()。

(2) main() 函数为程序的入口函数。程序代码如下：

#include <stdio.h>

int qusort(int s[], int start, int end) {    //自定义函数 qusort()
    int i, j;    //定义变量为基本整型
    i = start;    //将每组首个元素赋给i
    j = end;    //将每组末尾元素赋给j
    s[0] = s[start];    //设置基准值
    while (i < j) {
        while (i < j && s[0] < s[j])
            j--;    //位置左移
        if (i < j) {
            s[i] = s[j];    //将s[j]放到s[i]的位置上
            i++;    //位置右移
        }
        while (i < j && s[i] <= s[0])
            i++;    //位置左移
        if (i < j) {
            s[j] = s[i];    //将大于基准值的s[j]放到s[i]位置
            j--;    //位置左移
        }
    }
    s[i] = s[0];    //将基准值放入指定位置
    if (start < i)
        qusort(s, start, j - 1);    //对分割出的部分递归调用qusort()函数
    if (i < end)
        qusort(s, j + 1, end);
    return 0;
}

int main(void) {
       int a[10], i;
    printf("请输入10个数：\n");
    for (i = 0; i < 10; ++i) {
        scanf("%d", &a[i]);//从键盘中输入10个数
    }
    QuickSort(a, 0, 9);    //调用qusort()函数进行排序
    printf("排序后的顺序是：\n");
    for (i = 0; i < 10; ++i) {
        printf("%5d", a[i]);    //将排序后的顺序输出
    }

    return 0;
}

输出结果：

请输入10个数：
99 45 12 36 69 22 62 796 4 696
排序后的顺序是：
    4   12   22   36   45   62   69   99  696  796

快速排序原理：

从序列“2,3,5,7,9,6,4,1,0,8”两端开始
（1）首先将2作为基准数，应用2个变量i和j分别指向序列左端和右端；
（2）首先从j左往右寻找一个小于2的数，i从右往左寻找一个大于2的数；
（3）找到了0和3进行第一次交换，继续搜索；
（4）1和5进行第二次交换；
（5）当i和j都到1数值1时，表明第一轮交换结束，将基准数2和1进行交换，以基准数2为分界点，2的左边都小于等于2,2的右边都大于等于2；
（6）2的左边序列为“1,0”，2的右边序列为“7,9,6,4,5,3,8”；
（7）最后调用递归分别处理左边序列和右边序列即可。

#include <stdio.h>

void QuickSort(int a[], int left, int right) {
    int i, j, temp, tp;
    temp = a[left];                 //暂存基准数
    i = left;                       //最左位置
    j = right;                      //最右位置

    if (left > right)                //递归结束条件
        return;
    while (i != j)                  //当i和j不重合时
    {
        while (a[j] >= temp && i < j) //从右往左寻找小于基准数的值
            j--;
        while (a[i] <= temp && i < j) //从左往右寻找大于基准数的值
            i++;
        //找到了且i<j则交换数值
        if (i < j) {
            tp = a[i];
            a[i] = a[j];
            a[j] = tp;
        }
    }

    //将基准数和i、j的相遇数值进行交换
    a[left] = a[i];
    a[i] = temp;

    //应用递归对此时基准数的左边进行快速排序
    QuickSort(a, left, i - 1);
    //应用递归对此时基准数的右边进行快速排序
    QuickSort(a, i + 1, right);
}

int main(void) {
    int b[10], j;
    printf("请输入10个数：\n");
    for (j = 0; j < 10; j++)
        scanf("%d", &b[j]);
    QuickSort(b, 0, 9);         //调用快速排序函数
    printf("排序后的顺序是：\n");
    for (j = 0; j < 10; j++)
        printf("%-4d",b[j]);
    printf("\n");

    return 0;
}

输出结果：

请输入10个数：
99 45 12 36 69 22 62 796 4 696
排序后的顺序是：
    4   12   22   36   45   62   69   99  696  796

技术要点：

快速排序是冒泡排序的一种改进，主要的算法思想是在待排序的 n 个数据中取第一个数据作为基准值，将所有记录分为 3 组，使第一组中各数据值均小于或等于基准值，第二组做基准值的数琚，第三组中各数据值均大于或等于基准值。这便实现了第一趟分割，然后再对第二组和第兰组分别重复上述方法，依次类推，直到每组中只有一个记录为止。

Crazer的自留地