快速排序算法总结

排序算法有很多，选择，冒泡，插入......其中，快速排序算法效率算是比较高的一种了，不像选择，冒泡，快速排序进行的是在选定一个基准值(在序列中)的情况下左右同时的交替扫描的一种高效率算法。

快速排序的基本思想是选定一个基准值，通过扫描对比实现序列中比基准值大的都在基准值的右侧，同理，比基准值小的都在基准值的左侧。

并且，选定的基准值需要暂存起来放在一个变量中，这样即使后来执行扫描符合条件的数对其进行覆盖时也不会造成数据丢失。那么，这样就可以理解为天然的有一个“空位”，并且只有也只有一个"空位"。执行左右交替扫描的过程也就可以看成是不断改变“空位”的位置和填补“空位”的过程。

下面就以一个无序序列为例分析其具体过程

3 2 7 16 0 8 1

首先，方便起见，选第一个元素作为基准值，并存放至变量key中，然后进行左右交替扫描。

step one:从右往左扫描，发现1比3小，可以将1存放至3的位置上，因为3已经被暂存，不用担心覆盖的问题，可以理解为3的位置上是一个"空位"，并且1存放至3的位置上后，1的位置就变为“空位”

step two:(交替)从左往右扫描，发现2不比3大，继续往右移动一位，发现7比3大，将7放到1的位置上

step three(交替)从右往左扫描，发现8不比3小，移动到0，发现0比3小，将0放到7的位置

......

直到左扫描遇到右扫描，这时就将基准值存入到 扫描终止的那个位置上即可

最后，基准值左侧都比基准值小，基准值右侧都比基准值大，到此，以基准值所在为分界，左右便时规模较小的子问题罢了，可以进行递归求解。

如果亲们能耐下心看完并理解以上的分析

我相信以下的代码便不难理解：

 #include<iostream>
 using namespace std;
 ?
 int quickSort(int *a,int left,int right)
 {
     int key = a[left];
     int L=left;
     int R=right;
     while(L<R)
     {
         while(L<R&&key<a[R])
         {
             R--;
         }
         if(L<R)
         {
             a[L]=a[R];//填空位
         }
         while(L<R&&key>a[L])
         {
             L++;
         }
         if(L<R)
         {
             a[R]=a[L];//填空位
         }
     }
     a[L] = key;
     return L;//基准值最终的存放位置，并返回
 }
 ?
 void quickSortHelper(int *a,int left,int right)
 {
     if(left<right)
     {
         int temp = quickSort(a,left,right);
         quickSortHelper(a,left,temp);
         quickSortHelper(a,temp+1,right);    
     } 
 }
 int main()
 {
     int a[]={3,9,7,43,2,6,233,743,234};
     int len = sizeof(a)/sizeof(a[0]);
     quickSortHelper(a,0,len-1);
     for(int i=0;i<len;i++)
     {
         cout<<a[i]<<" ";
     }
     return 0;
 }

快速排序算法细致总结！！！

原文：https://www.cnblogs.com/yuanshixiao/p/13642155.html