首先简单谈下快速排序的特点，时间复杂度O(nLog n)，最差时间复杂度O(n^2)，平均时间O(nLog n).因为用到了函数栈，空间复杂度为O(lg n),最差为O(n).是一种不稳定的排序方法。基本思想是分治法，这位大大的http://blog.csdn.net/morewindows/article/details/6684558 讲的非常清楚了，分治法+挖坑法，我就不多说了。就是以某个数为参照，使得左边的都小于他，右边的数都大于他。然后对他的左右两个区间采取同样的方法进行递归。

就其整体实现而言，有两大种思路，一是双边扫描，二是单边扫描。下面分别来上程序:

一、双边扫描

双边扫描是谭浩强书中的方法，个人觉得比下面的单边扫描更好理解，也是博文里采用的方法。下面看程序:

 

**[cpp]** [view plain](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[copy](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[print](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[?](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[![在CODE上查看代码片](https://code.csdn.net/assets/CODE_ico.png)](https://code.csdn.net/snippets/412329)[![派生到我的代码片](https://code.csdn.net/assets/ico_fork.svg)](https://code.csdn.net/snippets/412329/fork)
  <div>
  </div>
</div>

- <span style="color: black;"><span style=<span class="string" style="color: red;">&#8220;font-family:Comic Sans MS;font-size:18px;&#8221;</span>><span class="keyword" style="font-weight: bold; color: blue;">void</span> quickSort1(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span>* x, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> l, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> r){  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">if</span>(l < r){  </span>

- <span style="color: black;">        <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> i = l, j = r, key = x[l];  </span>

- <span style="color: black;">        <span class="keyword" style="font-weight: bold; color: blue;">while</span>(i < j){  </span>

- <span style="color: black;">            <span class="keyword" style="font-weight: bold; color: blue;">while</span>( i < j && x[j] >= key){  </span>

- <span style="color: black;">                j&#8211;;  </span>

- <span style="color: black;">            }  </span>

- <span style="color: black;">            <span class="keyword" style="font-weight: bold; color: blue;">if</span>(i < j){  </span>

- <span style="color: black;">                x[i++] = x[j];  </span>

- <span style="color: black;">            }  </span>

- <span style="color: black;">            <span class="keyword" style="font-weight: bold; color: blue;">while</span>(i < j && x[i] <= key){  </span>

- <span style="color: black;">                i++;  </span>

- <span style="color: black;">            }  </span>

- <span style="color: black;">            <span class="keyword" style="font-weight: bold; color: blue;">if</span>(i < j){  </span>

- <span style="color: black;">                x[j&#8211;] = x[i];  </span>

- <span style="color: black;">            }  </span>

- <span style="color: black;">        }  </span>

- <span style="color: black;">        cout<<<span class="string" style="color: red;">&#8220;i = &#8220;</span> <<i<<<span class="string" style="color: red;">&#8221; j = &#8220;</span><<j<<endl;  </span>

- <span style="color: black;">        x[i] = key;  </span>

- <span style="color: black;">        quickSort1(x, l, i-1);  </span>

- <span style="color: black;">        quickSort1(x, i+1, r);  </span>

- <span style="color: black;">    }  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">}</span>  </span>

双边扫描非常直观，首先进到程序里判断是否l<r,当满足条件才进去。这也是用递归的一个必要条件，一定要让函数有尽头，有边界。然后进入大while循环，接着进入小while循环，先从右边找，只要满足数字大于key就一直让j往左移。直到第一个不满足条件的，就是第一个小于key的数跳出while循环，将它放在左边挖的“坑”上。同时让坑的索引+1，接着从左边开始扫描，找到第一个大于key的数，再将它填到右边的坑上。右边的坑索引-1，接着再从右边扫描。直到最后跳出大while循环，此时i = j。也就是完成了一次快速排序的扫描。之后将最初的key放到x[i]，其实放到x[j]也是一样的。因为i等于j么，此时！然后进行递归，对区间[l, i – 1], [i+1, r]进行同样的操作。

 

双边排序的要点: 1、最初的if一定要有，这是最后递归出来的标志位。2，为了找到一个数使它的左边都大于它，右边都小于它，要多次循环，这个循环就是大while循环。3、双边排序不需要swap，即无需交换。

 

二、单边扫描

上面的双边排序，出来一次大while循环，要从两边进行多次。单边扫描，则只需从左走到右就能完成一次 快排。

 

**[cpp]** [view plain](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[copy](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[print](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[?](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[![在CODE上查看代码片](https://code.csdn.net/assets/CODE_ico.png)](https://code.csdn.net/snippets/412329)[![派生到我的代码片](https://code.csdn.net/assets/ico_fork.svg)](https://code.csdn.net/snippets/412329/fork)
  <div>
  </div>
</div>

- <span style="color: black;"><span style=<span class="string" style="color: red;">&#8220;font-family:Comic Sans MS;font-size:18px;&#8221;</span>><span class="keyword" style="font-weight: bold; color: blue;">void</span> quickSort2(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> x[], <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> l, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> r){  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">if</span>(l >= r)  </span>

- <span style="color: black;">        <span class="keyword" style="font-weight: bold; color: blue;">return</span>;  </span>

- <span style="color: black;">    <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> m = l;  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">for</span>(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> i = l + l; i <= r; i++ ){  </span>

- <span style="color: black;">        <span class="keyword" style="font-weight: bold; color: blue;">if</span>(x[i] < x[l]){  </span>

- <span style="color: black;">            swap2(x[++m], x[i]);  </span>

- <span style="color: black;">        }  </span>

- <span style="color: black;">    }  </span>

- <span style="color: black;">    swap2(x[l], x[m]);  </span>

- <span style="color: black;">    quickSort2(x, l, m &#8211; 1);  </span>

- <span style="color: black;">    quickSort2(x, m + 1, r);  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">}  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> swap2(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> &a,<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> &b){  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">if</span>(a==b) <span class="keyword" style="font-weight: bold; color: blue;">return</span>;<span class="comment" style="color: #008200;">//对同一地址的数据交换，会使其结果为0</span>  </span>

- <span style="color: black;">    a=a^b;  </span>

- <span style="color: black;">    b=a^b;  </span>

- <span style="color: black;">    a=a^b;  </span>

- <span style="color: black;">}</span>  </span>

代码是不是更简单了？程序先进行判断，如果l>=r直接return，这点跟双边扫描的if一个意思，都是为递归创造结束的标志。然后用m记录最左边的那个的索引，这里默认的是第一个，即x[l]的索引。[注，m的初始值不一定指向key！，仅仅是指向最左边的。]然后进入扫描，直接从l + 1开始，如果右边的小于key，就让x[++m]和x[i]交换。如果右边的大于key，则不进行任何操作。这里有个特例，如果l = 0， 则m = 0.如果x[1]小于x[0]，则让x[1] 和x[1]进行交换，也就等于没交换。如果数组是5 4 3 2 1，则这里的交换就失效了。 再往后看，直到for循环结束，走出循环，让最后m指的位置的数和最初的key进行交换。如上面 5 4 3 2 1,则第一次快排的结果是 1 4 3 2 5，只有for出来后的那次swap才起作用。这里的m有个特殊含义，即指向小于key的最右边的那个数。所以出来后才用它(x[m])和key(即x[l])进行交换。

 

单边扫描的特点:

1、程序需要交换；

2、更有冒泡法的色彩；冒泡的目的不是让最大的数沉到最右边，而是让小于key的都左移，找到分界索引m。使之和key进行交换。

3、此版本的的单边扫描属于最基础的，还可以优化。

本想测出两个算法的时间 消耗差异，遗憾的是c++获得程序运行时间太费劲了，弄半天没弄成。下面附上完整程序:

 

**[cpp]** [view plain](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[copy](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[print](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[?](http://blog.csdn.net/yanzi1225627/article/details/36045001#)[![在CODE上查看代码片](https://code.csdn.net/assets/CODE_ico.png)](https://code.csdn.net/snippets/412329)[![派生到我的代码片](https://code.csdn.net/assets/ico_fork.svg)](https://code.csdn.net/snippets/412329/fork)
  <div>
  </div>
</div>

- <span style="color: black;"><span style=<span class="string" style="color: red;">&#8220;font-family:Comic Sans MS;font-size:18px;&#8221;</span>><span class="comment" style="color: #008200;">//============================================================================</span>  </span>

- <span style="color: black;"><span class="comment" style="color: #008200;">// Name        : QuikSort.cpp</span>  </span>

- <span style="color: black;"><span class="comment" style="color: #008200;">// Author      : YanZi</span>  </span>

- <span style="color: black;"><span class="comment" style="color: #008200;">// Version     :</span>  </span>

- <span style="color: black;"><span class="comment" style="color: #008200;">// Copyright   : Your copyright notice</span>  </span>

- <span style="color: black;"><span class="comment" style="color: #008200;">// Description : Hello World in C++, Ansi-style</span>  </span>

- <span style="color: black;"><span class="comment" style="color: #008200;">//============================================================================</span>  </span>

- <span style="color: black;">  </span>

- <span style="color: black;"><span class="preprocessor" style="color: gray;">#include <iostream></span>  </span>

- <span style="color: black;"><span class="preprocessor" style="color: gray;">#include <malloc.h></span>  </span>

- <span style="color: black;">  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">using</span> <span class="keyword" style="font-weight: bold; color: blue;">namespace</span> std;  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> swap1(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> a, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> b);  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> printArray(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span>* in, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> n);  </span>

- <span style="color: black;">  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> quickSort1(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span>* x, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> l, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> r);<span class="comment" style="color: #008200;">//双边扫描，快速排序</span>  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> quickSort2(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> x[], <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> l, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> r);<span class="comment" style="color: #008200;">//单边扫描，快速排序</span>  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> swap2(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> &a,<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> &b); <span class="comment" style="color: #008200;">//交换，在MinGW上必须采用此方法，swap1无效</span>  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">  </span>

- <span style="color: black;"><span class="preprocessor" style="color: gray;">#define N 8 //数组的长度</span>  </span>

- <span style="color: black;">  </span>

- <span style="color: black;"><span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> main() {  </span>

- <span style="color: black;">    <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span>* input = NULL;  </span>

- <span style="color: black;">    input = (<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span>*)malloc(N * <span class="keyword" style="font-weight: bold; color: blue;">sizeof</span>(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span>));  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">if</span>(input == NULL){  </span>

- <span style="color: black;">        cout<<<span class="string" style="color: red;">&#8220;内存溢出&#8221;</span><<endl;  </span>

- <span style="color: black;">    }  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">for</span>(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> i = 0; i < N; i++){  </span>

- <span style="color: black;">        input[i] = rand();  </span>

- <span style="color: black;">    }  </span>

- <span style="color: black;">    <span class="comment" style="color: #008200;">//  int input[] = {55, 41, 59, 26, 53, 58, 97, 93};</span>  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">    cout<<<span class="string" style="color: red;">&#8220;原始数据:&#8221;</span><<endl;  </span>

- <span style="color: black;">    printArray(input, N);  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">    quickSort2(input, 0, N-1);  </span>

- <span style="color: black;">    printArray(input, N);  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">return</span> 0;  </span>

- <span style="color: black;">}  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> swap1(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> a, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> b){  </span>

- <span style="color: black;">    <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> temp = a;  </span>

- <span style="color: black;">    a = b;  </span>

- <span style="color: black;">    b = temp;  </span>

- <span style="color: black;">}  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> printArray(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> * in, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> n){  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">if</span>(in == NULL){  </span>

- <span style="color: black;">        <span class="keyword" style="font-weight: bold; color: blue;">return</span>;  </span>

- <span style="color: black;">    }  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">for</span>(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> i = 0; i<n; i++){  </span>

- <span style="color: black;">        cout<<<span class="string" style="color: red;">&#8221; &#8220;</span><<in[i];  </span>

- <span style="color: black;">    }  </span>

- <span style="color: black;">    cout<<endl;  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">}  </span>

- <span style="color: black;">  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> quickSort1(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span>* x, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> l, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> r){  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">if</span>(l < r){  </span>

- <span style="color: black;">        <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> i = l, j = r, key = x[l];  </span>

- <span style="color: black;">        <span class="keyword" style="font-weight: bold; color: blue;">while</span>(i < j){  </span>

- <span style="color: black;">            <span class="keyword" style="font-weight: bold; color: blue;">while</span>( i < j && x[j] >= key){  </span>

- <span style="color: black;">                j&#8211;;  </span>

- <span style="color: black;">            }  </span>

- <span style="color: black;">            <span class="keyword" style="font-weight: bold; color: blue;">if</span>(i < j){  </span>

- <span style="color: black;">                x[i++] = x[j];  </span>

- <span style="color: black;">            }  </span>

- <span style="color: black;">            <span class="keyword" style="font-weight: bold; color: blue;">while</span>(i < j && x[i] <= key){  </span>

- <span style="color: black;">                i++;  </span>

- <span style="color: black;">            }  </span>

- <span style="color: black;">            <span class="keyword" style="font-weight: bold; color: blue;">if</span>(i < j){  </span>

- <span style="color: black;">                x[j&#8211;] = x[i];  </span>

- <span style="color: black;">            }  </span>

- <span style="color: black;">        }  </span>

- <span style="color: black;">        cout<<<span class="string" style="color: red;">&#8220;i = &#8220;</span> <<i<<<span class="string" style="color: red;">&#8221; j = &#8220;</span><<j<<endl;  </span>

- <span style="color: black;">        x[i] = key;  </span>

- <span style="color: black;">        quickSort1(x, l, i-1);  </span>

- <span style="color: black;">        quickSort1(x, i+1, r);  </span>

- <span style="color: black;">    }  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">}  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> quickSort2(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> x[], <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> l, <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> r){  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">if</span>(l >= r)  </span>

- <span style="color: black;">        <span class="keyword" style="font-weight: bold; color: blue;">return</span>;  </span>

- <span style="color: black;">    <span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> m = l;  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">for</span>(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> i = l + l; i <= r; i++ ){  </span>

- <span style="color: black;">        <span class="keyword" style="font-weight: bold; color: blue;">if</span>(x[i] < x[l]){  </span>

- <span style="color: black;">            swap2(x[++m], x[i]);  </span>

- <span style="color: black;">        }  </span>

- <span style="color: black;">    }  </span>

- <span style="color: black;">    swap2(x[l], x[m]);  </span>

- <span style="color: black;">    quickSort2(x, l, m &#8211; 1);  </span>

- <span style="color: black;">    quickSort2(x, m + 1, r);  </span>

- <span style="color: black;">  </span>

- <span style="color: black;">}  </span>

- <span style="color: black;"><span class="keyword" style="font-weight: bold; color: blue;">void</span> swap2(<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> &a,<span class="datatypes" style="font-weight: bold; color: #2e8b57;">int</span> &b){  </span>

- <span style="color: black;">    <span class="keyword" style="font-weight: bold; color: blue;">if</span>(a==b) <span class="keyword" style="font-weight: bold; color: blue;">return</span>;<span class="comment" style="color: #008200;">//对同一地址的数据交换，会使其结果为0</span>  </span>

- <span style="color: black;">    a=a^b;  </span>

- <span style="color: black;">    b=a^b;  </span>

- <span style="color: black;">    a=a^b;  </span>

- <span style="color: black;">}</span>  </span>

-

💬 评论