C语言实现数组快速排序算法

快速排序算法，顾名思义，是迄今为止发现的速度最快的排序算法。快速排序算法采用分治的思想，首先在要排序的序列{5,8,7,6,4,3,9}中选取一个基准数（一般选取序列的第一个，其实选取哪个是无关紧要的），将序列分成两部分，其中基准数的左边全是小于基准数的数，基准数右边是大于或者等于基准数的数。这样，基准数的位置在序列中的位置就固定了，然后将基准数两边的序列进行相同的处理，直到最后一个序列只有一个数字，这样算法就完成了。图解如下：

序列{5,8,7,6,4,3,9}，第一次选取基准数5进行一次划分，划分后的序列为：{3,4,5,6,8,7,9}，5左边的序列{3，4}进行相同的划分，选取这个序列的基准数为3，划分后的结果为{3,4}，此时3的左边已没有序列，而3右边的序列为{4}，因为这时序列中只有一个数字，显然这样的序列是已经排好序的；然后处理第一次基准数5右边的序列{6,8,7,9}，选取基准数为6，进行划分后序列为{6,8,7,9}，6左边已经没有序列，6右边的序列为{8,7,9},对这个序列选取基准数为8，进行划分得{7,8,9}，8左边和序列为{7}，右边的序列为{9}，此时，排序已经完成。动态图如下：

可见，快速排序的核心算法就是划分算法，在我们上面的讨论中，这种划分算法是由Glenn W. Rowe提出的，还有一种更早的划分算法是由C. A. R. Hoare提出的。这里只讨论和实现Glenn W. Rowe提出的划分算法。快速排序算法的运行过程如下：
开始——划分序列——得到划分序列的子序列——再次划分——得到划分序列的子序列……。
首先讨论Glenn W. Rowe划分算法：
假如Glenn W. Rowe划分算法选取数组第0位作为基准数，那么Glenn W. Rowe划分算法从数组第1位扫描到数组最后一位，遇到比基准数大的，就交换到右边，比基准数小的，交换到左边，其算法时间复杂度为O(n)
实现代码如下：