C++数据结构--快速排序

布满荆棘的人生 2021-11-12 00:16 346阅读 0赞

**1.对向量数组v\{800,150,300,650,550,500,400,350,450,900\}进行快速排序,索引\[first,last)=\[0,10)  
\*将v的元素划分为两个子表s1和S2,子表S1的元素都<=中心值，子表S2的元素都>=中心值  
step1:取pivot=v\[mid\]=v\[5\]=500,作为中心值，并与v\[first\]交换，其中mid=(first+last)/2  
整数指针scnUP从first+1开始往右扫描，scanDown从last-1开始往左扫描  
![20130809181537046][]  
  
step2:当scanUp,scanDown都找到不符合条件的元素时，交换它们，再继续扫描  
![20130809181607875][]  
  
step3:继续step2的步骤  
![20130809181646218][]  
  
step4:当scanUp>=scanDown时，停止划分子表,scanDown指向的就是俩个子表的分界点，同时也是存放v\[0\]的中心值的最终位置。  
![20130809181900671][]  
  
  
step5:对子表s1,s2重复step1-step4  
![20130809181944937][]  
  
step6:对子表s1  
![20130809182003515][]  
  
step7:当子表为空或只有一个元素时，停止递归  
![20130809182118609][]  
  
step8:对子表s2  
![20130809183418453][]  
  
  
step9:继续对更小的子表进行划分  
![20130809183455109][]  
  
step10:处理更小的子表  
![20130809183515171][]  
最终结果：  
![20130809183533843][]  
  
  
  
  
实现代码：  
\#include<iostream>  
\#include<vector>  
using namespace std;  
  
  
template<typename T>  
//交换两个元素   
void mySwap(T &v1,T &v2)  
\{  
T temp;  
temp=v1;  
v1=v2;  
v2=temp;  
\}  
  
  
  
  
template<typename T>  
/\*返回向量数组分界点的下标  
\*在\[first,last)范围内，把比v\[(first+last)/2\]  
\*小的元素放左边，比v\[(first+last)/2\]大的元素  
\*放右边,  
\*/  
int pivotIndex(vector<T> &v,int first,int last)  
\{  
int mid=(first+last)/2; //中间元素下标索引  
T pivot=v\[mid\];//记录中间元素的值   
mySwap(v\[first\],v\[mid\]);//把中间元素和第一个元素交换位置   
  
int scanUp=first+1; //向右扫描的索引   
int scanDown=last-1; //向左扫描的索引  
while(true)  
\{   
while(scanUp<=scanDown&&v\[scanUp\]<=pivot)  
 scanUp++;  
while(scanUp<=scanDown&&v\[scanDown\]>=pivot)  
 scanDown--;  
if(scanUp>=scanDown)//到达分界点，跳出循环   
 break;  
mySwap(v\[scanUp++\],v\[scanDown--\]);  
\}   
  
 mySwap(v\[first\],v\[scanDown\]); //交换第一个元素（保存中间元素的值）和临界点索引处的元素   
  
return scanDown;  
\}  
  
  
  
  
  
  
  
  
template<typename T>  
//在向量数组\[first,last)范围内进行快速排序   
void quickSort(vector<T> &v,int first,int last)  
\{   
if(last-1<=first) //当子表为空或只有一个元素时,停止递归  
 return;  
if(first==last-2) //当只有两个元素时，判断是否需要交换，以提高效率  
\{   
if(v\[first\]>v\[last-1\])  
 \{   
mySwap(v\[first\],v\[last-1\]);  
 \}  
return;  
\}  
else  
\{   
int mid=pivotIndex(v,first,last);  
quickSort(v,first,mid); //对左子表递归   
quickSort(v,mid+1,last); //对右子表递归   
\}  
  
\}   
  
  
  
  
测试代码  
int main ()  
\{  
vector<int> vec\{800,150,300,650,550,500,400,350,450,900\};  
quickSort(vec,0,vec.size());  
for(int x:vec)  
cout<<x<<ends;  
  
return 0;  
\}  
  
  
  
  
运行结果：**

**![Center][]**

**以上的划分找中值和递归感觉比较繁琐，个人认为另一种划分方法更为简便，详见**

### [C++数据结构--快速排序][C_--] ###

[20130809181537046]: /images/20211109/e5ca5eda82b846a9a8a52b80b18921de.png
[20130809181607875]: /images/20211109/1fbdef324def4c049819a111e2bb01f6.png
[20130809181646218]: /images/20211109/5a57167edfda446d90c9ef3886510dc1.png
[20130809181900671]: /images/20211109/614388293b2a4b6a8877c2b708dad9c0.png
[20130809181944937]: /images/20211109/ed97504ddd2245159c27579bf633639a.png
[20130809182003515]: /images/20211109/a3c79783ef5e4a0fa38e62db89d2781a.png
[20130809182118609]: /images/20211109/71aaff8d329545f2a8b73c3052c98784.png
[20130809183418453]: /images/20211109/87cc7f67b6864d11834d8ec9e57d4177.png
[20130809183455109]: /images/20211109/245f9a2c04b64cef89174f38e258d588.png
[20130809183515171]: /images/20211109/a70b2916ad194c93b94aa92e785ff88f.png
[20130809183533843]: /images/20211109/67c75253781244a489a577c87bdf34a5.png
[Center]: /images/20211109/7f0cc04bac42426aae5ae482fbb5d801.png
[C_--]: http://blog.csdn.net/piniheaven/article/details/9080119