快速排序算法（一）

1. 快速排序算法简介　　

　　快速排序方法是对冒泡排序的一种改进，基本思想是将待排序序列分成两部分，使其中一部分的记录都比另一部分的小，随后分别对这两部分再进行重复划分，最终使得整个序列有序。

　　该方法的基本思想是：（分治策略）

1. 先从数列中取出一个数作为基准数；
2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边；
3. 再对左右区间重复第二步，直到各区间只有一个数。

　　设置low，high两个指针，分别指向序列的第一个记录和最后一个记录。此时low指向了序列的第一个记录，也就是枢轴的位置。

　　以序列{49,38,65,97,76,13,27,49,55,04}为例，第一趟排序过程如下图所示。图中黑线圈代表指针low，虚线圈代表指针high。

第一趟排序的过程

第二趟排序的过程

第三趟排序的过程

　　经过三趟排序之后，整个序列就已经排序完成。

　　在CSDN的一篇博客中，作者将快速排序算法总结为：挖坑填数+分治法。（http://blog.csdn.net/morewindows/article/details/6684558）

　　挖坑填数：

1. i =L; j = R; 将基准数挖出形成第一个坑a[i]；
2. j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中；
3. i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中；
4. 再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

2. 相关代码

//快速排序  
//arr:数组首地址；l:low指针位置；r:high指针位置
void quicksort(int *arr, int l, int r)
{
    if (l < r)
    {
        int i = l, j = r, x = arr[l];
        while (i < j)
        {
            while (i < j && arr[j] >= x) // 从右向左找第一个小于x的数  
                j--;
            if (i < j)
                arr[i++] = arr[j];

            while (i < j && arr[i] < x) // 从左向右找第一个大于等于x的数  
                i++;
            if (i < j)
                arr[j--] = arr[i];
        }
        arr[i] = x;
        quicksort(arr, l, i - 1); // 递归调用   
        quicksort(arr, i + 1, r);
    }
}