排序算法（二）快速排序（递归与非递归实现）

89 阅读 0 评论 59 点赞

我是靠谱客的博主大力鸭子，这篇文章主要介绍排序算法（二）快速排序（递归与非递归实现），现在分享给大家，希望可以做个参考。

快速排序算法描述：

快速排序的实现原理是在待排序的数据中取出一个数作为键值，比较序列数据与其的大小，大于该键值的数据放在该键值右边，小于的放在左边。完成后再对键值两边的序列递归上述操作，这样经过若干步后数据就排序好了。过程如下图：

这里写图片描述

如上描述的我们可以将快速排序分为如下几个步骤：
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
经过如上步骤尽可以使用快速排序将一组乱序的数据进行排序。那么现在我们就来分析一下快速排序的时间和空间复杂度。从名字我们就可以知道这种排序应该很快，不然怎么能叫快速排序呢，快排确实很快他的平均时间复杂度为O(nlogn)，他处理完全无序的的数据时是最高效的，但对于一个有序的序列来说他的时间复杂度就变成了O(n^2)；对于空间复杂度而言，由于快排使用了递归，所以他的空间复杂度不为O(1)，在这里他的空间复杂度与函数递归的次数有关。对于一个序列排序的时间复杂度为O(n)，则可知函数总共递归了logn次，因此，空间复杂度也为O(logn)。另外，快速排序是一种不稳定的排序算法，这是由于键值的选取而造成的。
代码实现：

void Quick(int *data, int low, int high)
{
int i = low;
int j = high;
int temp = data[low];
if(low < high)
{
while(i < j)
{
while(i < j && data[j] > temp)
{
j--;
}
data[i] = data[j];
while(i < j && data[i] < temp)
{
i++;
}
data[j] = data[i];
}
data[i] = temp;
//i == j
Quick(data, low, i - 1);
Quick(data, j + 1, high);
}
}
void QuickSort(int *data, int len)
{
if(data == NULL || len <= 0)
{
return;
}
Quick(data, 0, len - 1);
}

在C/C++中，递归与栈很相像，也可以理解为递归其实就是在使用栈的过程。所以我们也可以利用栈来实现快速排序的非递归版本。在C语言中我们要自己实现一个栈，并且栈的大小为logn，这里我们使用C++中的STL库中的栈来实现。
代码实现：

#include<iostream>
#include<stack>
#include<stdlib.h>
using namespace std;
int Partition(int *data, int low, int high)
{
int temp = data[low];
while(low < high)
{
while(data[j] > temp)
{
high--;
}
if(low < high)
{
data[low] = data[high];
}
while(data[i] < temp)
{
low++;
}
if(low < high)
{
data[j] = data[i];
}
}
data[low] = temp;
//low == high
return low;
}
void QuickSort(int *data, int len)
{
if(data == NULL || len <= 0)
{
return;
}
stack<int> st;
int low = 0;
int high = len -1;
st.push(low);
st.push(high);
while(!st.empty())
{
high = st.top();st.pop();
low = st.top();st.pop();
int par = Partition(data, low, high);
if(low < par - 1)
{
st.push(low);
st.push(par - 1);
}
if(high > par + 1)
{
st.push(par + 1);
st.push(high);
}
}
}

快排C/C++的非递归实现没有太大区别，唯一的区别在于C要自己实现一个栈来保存有关数据，而在C++中我们可以使用STL中的栈来帮助我们完成数据的保存，这就减少了实现栈的过程。除此之外，其余地方是基本没有区别的。
快排实现到这里只是简单的完成了快排的一般情况，在这里我们还可以对快排进行优化。这里我介绍的优化方式为三数取中，何谓三数取中呢？其实很简单，就是每次选取键值的时候不直接选取第一个数最为键值，而是在当前待排序的序列中通过0下标、n下标、n/2下标三个数种中取中间值最为比较的键值，这样在一定程度上就实现了对代码的优化。