快速排序算法解析 一、掌握快排的算法流程 1.算法思想如下： 通过一趟扫描将待排序的元素分割成独立的三个序列：第一个序列中所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置，因此需要再按此方法对第一个序列和第三个序列分别进行排序，整个排序过程可以递归进行，最终可使整个序列变成有序序列。 2.其中的基准元素选择不唯一，可以采取以下五种方法： 取第一个元素 取最后一个元素 取位于中间位置的元素 “三者取中的规则” 取位于low和high之间的随机数，用A[P]作为基准元素。即采用随机函数产生一个位于low和high之间的随机数P(low≤P≤high)，用A[P]作为基准，这相当于强迫R[low:high]中的元素是随机分布的 二、快排的代码实现与效果 C++源码： #include #include #include using namespace std; //快排,分两步骤：分区和递归 //初始化动态数组 void getArray(vector& 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(vectorv) { for(vector::iterator it=v.begin();it!=v.end();it++) { cout << *it << " " ; } cout << endl; } //快排第一步：分区 int divided(vector&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&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) { vectorv; 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循环的条件都要有lowhigh，这个条件什么时候会触发呢？上面以及提到了是子序列长度为零，所以我们每次调用递归 都要缩减序列的边界 。通过diveded函数来得到每次划分成两部分序列的下标，以此作为子序列的某一边界，这样随着程序的运行，子序列逐渐缩小，最终排序的结果就是我所想的。 3、初始化与打印函数 这里就是C++中vector容器的一些用法了： getArray函数里有srand作为随机数种子，利用push_back方法将产生的随机数循环插入到v容器中。 printArray 函数使用迭代器来遍历输出容器中的数据，这些知识我也有写博客，可以在我的《C++提高》专栏里学习。 四、时间复杂度分析 最坏的情况 如果说待排序列已经有序，那么快速排序分区的时候需要一个一个的比较、移动，根本不会发生多个子序列的情况，与冒泡无差别，时间复杂度为： 最好的情况 由于算法是不断在子序列上递归执行的，如果说每次待排元素都恰好处在中间位置，将原有序列分成两个等长的子序列，每次划分都是这样的情况，那么总共的划分次数就可以用O(log2n)表示，这样时间复杂度可以在O(n log2 n)。 平均情况 快速排序是基于关键字比较的内部排序算法中速度最快的，平均性能可达O(n l o g 2 nlog2nlog2 n)。 有关快速排序的算法解析到此结束了，期待你的关注和鼓励~