C语言实现快速排序

前述

快速排序算法是一种高效的排序算法。
在平均情况下，排序n个项目要O(nlogn)次比较。
在最坏状态下需要O(n^2)次比较，相当于冒泡排序，但这种情况并不常见。
快速排序使用分治法（Divide and conquer）策略来把一个串行分为两个串行。
特点：

1. List item

   其两个子表的形成都是采用从两头向中间交替式逼近法。

2. List item
   每趟中对子表的 *** 作都相似，可以采用递归算法

算法步骤

1.从数列中挑出一个元素，称为“基准”（pivot）;
2.重新排列数列，把比基准小的元素放在基准前面，比基准大的元素放在基准后面（相同的数可以放到任意一边，看个人的算法怎么安排）。这次调整之后，基值左侧的数都比其小，基值右侧的数都比其大；
3.递归实现，基准左右两侧的数列分别进行排序，直到每个子数列只剩一个数据元素时退出递归，向上返回信息

动画演示

在编码实现时可以采用这样的策略：
将数组第一个元素看作“基准”，首先先定义一个pivot对其值进行保存；
从右往左遍历，出现值比基准值小的情况，将其赋值给基准值所在位置，否则右指针左移继续比较；

while(low < high && num[high]>=pivot)      high--;
         num[low] = num[high];

当发生右值左移时开始从左往右遍历，当出现比基准值大的情况，将其放在刚刚发生向左移动的右值的那个位置，否则左指针右移；

while(low < high && num[low]<pivot)       low++;
          num[high] = num[low];

如此循环直到满足“基值”左侧都比其小，基值右侧都比其大。而此时基值应该放在最后一次将值赋出去的位置，在该程序中是左指针low的位置

 while(low < high)
        {
                while(low < high && num[high]>pivot)      high--;
                num[low] = num[high];
                while(low < high && num[low]pivot)       low++;
                num[high] = num[low];
        }
        num[low] = key;

最后采用分治策略将其递归。
完整快排代码实现如下

void quickSort(int *num,int l,int r)
{
        if(l==r)      
        	return ;//当子数列长度减小到一个元素时返回
        int low = l;
        int high = r-1;
        int pivot = num[l];		//将左值定为基准值
        while(low < high)
        {
                while(low < high && num[high]>pivot)      high--;//循环从右向左比较
                num[low] = num[high];		//出现比基准值小的右值时左移	
                while(low < high && num[low]<pivot)       low++;//循环从左向右比较
                num[high] = num[low];			//出现比基准值大的左值时右移
        }
        num[low] = pivot;			//在上一个周期中，完成了基值左侧全比其小，基值右侧全比其大，而最后将左侧的值赋给了右侧（即第二个while循环后的num[high] = num[low]），则应该将基值放在将值赋出去的位置
        quickSort(num,l,low);//递归实现基值左侧排序
        quickSort(num,low+1,r);//递归实现基值右侧排序
}