[数据结构与算法]（C语言）快速排序法

自从笔者开始刷算法题，笔者就发现呐，这个冒泡排序和选择排序是真的很消耗时间，经常会因为超过时间限制而无法ac，于是经过笔者数天的学习，了解到快速排序法是十分高效的，当然相反的，由于快速排序法是通过递归实现，占用的内存会较多.

那么，作为一种排序方法，快速排序法是如何实现的呢？

快速排序法是一种基于分治思想实现的一种排序方法，通过随机定义一个值作为中值，以这个中值为界限划分两个区域，一个是左区域，一个是右区域，比中值大的全部放入右区域 ，比中值小的全部放入左区域，然后继续调用，在左右区域各自在做一次相同的操作，直到排序完成！

哈哈哈，基于文字的学习有时是难以理解滴！所以下面我们来一点实例：

我给定一串数字，希望能逆序排序.

6 7 8 1 4 3 5 2 9

6 7 8 1 4 3 5 2 9

我将6作为我的中值，从最后面逆序开始寻找一个比6小的数，我发现9并不满足我的要求，于是向前一位，因此我就找到了2，将他们两个进行替换.

2 7 8 1 4 3 5 6 9

其实你会发现，此时9作为一个大于6的数已经位于右区域了.

然后我们已经放置了一个数字2进入左区域，此时，我们再从前面顺序找一个比6大的数（这样我就能将6替换回去，进行下一轮的比较），注意，此时我们是从第二位开始找齐，因为数字2已经位于左区域，不必要再次进行比较，然后我们一下子就找到了7（有可能不会一下子找到，小于6的数就会默认直接放入左区域），此时再将7与6进行替换。

2 6 8 1 4 3 5 7 9

然后就再次重复操作（记住，每一次操作的对象是上一次操作对象的前一位（或后一位）.

进行最后一轮比较，会出现这种情况

2 5 6 1 4 3 8 7 9

?当我将6与3交换完毕后：

2 5 3 1 4 6 8 7 9

?数字6无法再进行下轮比较，所以这时就停止比较（假设交换前数字3的位置为k，数字6的位置为m，交换完后，数字6的位置变为k，然后进行比较，此时位于m+1，m+2位置（已经强调过，上一次操作的下一个位置进行比较）都比数字6小，于是会最后变成数字6与数字6比较，这时就可以写一个判断语句判断此时位置m+i（跳过的位置数）是否>=k，就可以实现函数终止了。

当这一次函数调用完毕后，我需要将6前面的左区域和后面的右区域分别再进行一次如上操作，即调用函数本身（递归），然后左区域（右区域）排列完毕后，再调用.....直到排序结束，就实现了快速排序了.

以下是实操代码：

void Rapidsort( int s[], int low, int high )
{
    int i = low;    //将第一项定义为low，最后一项定义为high
    int j = high;
    int key = s[low]; //将第一项作为中值
    if (low >= high)  //判断是否处于m+i>=k的位置
    {
        exit(0) ;
    }
    
    while (low < high)   //比较交换
    {
        while (low < high && key <= s[high])
        {
            high++; 
        }
        if (key > s[high])
        { 
            Swap(&s[low], &s[high]);
            low++;
        }
        while (low < high && key >= s[low])
        {
            low++;
        }
        if (key < s[low])
        {
            Swap(&s[low], &s[high]);
            high++;
        }
    }
    Rapidsort(s, i, low-1); 
    Rapidsort(s, low+1, j); //再次调用，左右区域再次排序
}

如果有不对的地方请各位指点出来~~笔者会及时修改~~

swap是交换函数哦~