快速排序算法（C语言实现）

C语言快速排序法的基本思想：先从数列中取出一个数作为key 值；将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；对左右两个小数列重复上一步，直至各区间只有 1 个数。

通过一趟快速排序算法把所需要排序的序列的元素分割成两大块。其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法，排序实现的整个过程可以是递归调用，最终实现将所需排序的无序序列元素变为一个有序的序列。

假设要排序的数组是 a[0]……a[N-1]，首先 a[0] 作为基准元素，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一次快速排序。

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

• 设置两个变量 i、j，排序开始时 i=0、j=N-1。
• 以第一个数组元素 a[0]（即a[i]）作为基准元素。
• 从 j 开始从后往前搜索 (j--)，找到第一个小于 a[i] 的数 a[j]，将 a[j] 和 a[i] 互换位置，此时基准元素的位置在数组的第 j 个位置。
• 从 i 开始从前向后搜索 (i++)，找到第一个大于 a[j] 的 a[i]，将 a[i] 和 a[j] 互换位置，此时基准元素的位置在数组的第 i 个位置。
• 重复 3、4，直到 i=j，此时循环结束。

快速排序算法应用示例（C语言）

对 5 个数 [10，2，3，21，5] 进行从小到大的排序。C语言编程代码如下：

#include<stdio.h>
void sort(int a[],int left ,int right)
{
    int i,j,temp;
    i=left;
    j=right;
    temp=a[left];
    if(left>right) return;
    while(i!=j)                       /*i不等于j时，循环进行*/
    {
        while(a[j]>=temp&&j>i)
            j--;
        if(j>i)
            a[i++]=a[j];
        while(a[i]<=temp&&j>i)
            i++;
        if(j>i)
            a[j--]=a[i];
    }
    a[i]=temp;
    sort(a,left,i-1);                   /*对小于基准元素的部分进行快速排序*/
    sort(a,i+1,right);                 /*对大于基准元素的部分进行快速排序*/
}
int main()
{
    int m[5]={10,2,3,21,5};
    int i=0; 
    sort(m,0,4);
    printf("从小到大排序后：\n");                      
    for(i=0;i<5;i++)
        printf("%d",m[i]);              /*输出排序结果 */
    printf("\n");  
}

运行结果：

从小到大排序后：
2351021

本例使用快速排序法实现排序过程，需要注意：

• 当 i=j 时，循环停止，并不代表排序结束，只是代表一次快速排列完成，若想实现最终的排列顺序，可能要经过几次快速排列才能完成；
• 在一次快速排列过程中，基准元素是不变的；
• 完成整个过程的快速排列，采用了递归算法。

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