快速排序算法解析

一、掌握快排的算法流程

算法思想如下：

通过一趟扫描将待排序的元素分割成独立的三个序列：第一个序列中所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置，因此需要再按此方法对第一个序列和第三个序列分别进行排序，整个排序过程可以递归进行，最终可使整个序列变成有序序列。

其中的基准元素选择不唯一，可以采取以下五种方法：

取第一个元素

取最后一个元素

取位于中间位置的元素

“三者取中的规则”

取位于low和high之间的随机数，用A[P]作为基准元素。即采用随机函数产生一个位于low和high之间的随机数P(low≤P≤high)，用A[P]作为基准，这相当于强迫R[low:high]中的元素是随机分布的

二、快排的代码实现与效果

C++源码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//快排,分两步骤：分区和递归
//初始化动态数组
void getArray(vector<int>& v)
{
  srand((unsigned int)time(NULL));
  int n = 0;
  cout << "请出入数组的大小为："; cin >> n;
  for (int i = 0; i < n; i++) {
  v.push_back(rand() % 100 + 1);
  }
  cout << endl;
}
//使用迭代器打印数组元素
void printArray(vector<int>v) {
  for(vector<int>::iterator it=v.begin();it!=v.end();it++)
  {
  cout << *it << " " ;
  }
  cout << endl;
}
//快排第一步：分区
int divided(vector<int>&v,int low,int high)
{
  int p = v[low];
  while (low < high)
  {
  while (low < high && p <= v[high])
    high--;
  v[low] = v[high];
  while (low < high && p >= v[low])
    low++;
  v[high] = v[low];
  }
  v[low] = p;
  return low;
}
//快排第二部，递归
void repeact(vector<int>&v,int low,int high)
{
  if (low > high) return;
  int flag = divided(v, low, high);
  repeact(v,low,flag-1);
  repeact(v,flag+1,high);
}
int main(void)
{
  vector<int>v;
  getArray(v);
  //sort(v.begin(),v.end());
  printArray(v);
  repeact(v, 0, v.size() - 1);
  printArray(v);
  return 0;
}

运行效果：

三、具体代码分析

快速排序的代码相信网上有很多一样的，所以博主分享一个特别的：用动态数组vector容器实现快速排序。下面就是代码解析：

1、分区函数 divided

这里选择数组中左边界作为基准元素 p，外层while循环以及内层while循环的条件都要有low<high，这样做的目的是为了退出循环时让low和high相等。

对于内层while循环，由于我选的是左边界作为基准元素，那么我们就应该从数组右端往前依次与基准元素标记：如果基准元素小，右端元素向前移动，high递减；如果基准元素大，直接将右边小的元素扔到数组下标low的位置，不用担心左边界被覆盖，因为我们用基准元素记录了。然后用左端元素与基准元素比较，如果基准元素大，左端向右移动，low递增；如果基准元素小，将左端元素大的值扔到数组下标high的位置。直到low==high，循环结束，此时数组被分为两部分：low左边的值都要小于或者等于low右边的值。最后将基准元素赋到下标low的位置并返回该下标即可。

2、递归 repeact

使用递归来对数组的子序列进行划分，同样的子序列也会调用递归来对其子序列划分，直到子序列长度为零，这时候整个数组就是一个有序的序列了

首先给出递归结束的条件：low>high，这个条件什么时候会触发呢？上面以及提到了是子序列长度为零，所以我们每次调用递归 都要缩减序列的边界 。通过diveded函数来得到每次划分成两部分序列的下标，以此作为子序列的某一边界，这样随着程序的运行，子序列逐渐缩小，最终排序的结果就是我所想的。

3、初始化与打印函数

这里就是C++中vector容器的一些用法了：

getArray函数里有srand作为随机数种子，利用push_back方法将产生的随机数循环插入到v容器中。

printArray 函数使用迭代器来遍历输出容器中的数据，这些知识我也有写博客，可以在我的《C++提高》专栏里学习。

四、时间复杂度分析

最坏的情况

如果说待排序列已经有序，那么快速排序分区的时候需要一个一个的比较、移动，根本不会发生多个子序列的情况，与冒泡无差别，时间复杂度为：O(n 2 n^2n

2

)

最好的情况

由于算法是不断在子序列上递归执行的，如果说每次待排元素都恰好处在中间位置，将原有序列分成两个等长的子序列，每次划分都是这样的情况，那么总共的划分次数就可以用O(log2n)表示，这样时间复杂度可以在O(n log2 n)。

平均情况

快速排序是基于关键字比较的内部排序算法中速度最快的，平均性能可达O(n l o g 2 nlog2nlog2 n)。