算法导论CLRS 7.3 随机版快速排序

本文主要是介绍算法导论CLRS 7.3 随机版快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*7.3 随机化快速排序*QUICK-SORT*/
#include<iostream>
#include<iomanip>
#include<vector>
#include<ctime>
using namespace std;
typedef vector<int>::iterator ivecIte;size_t chkivIte(ivecIte iteB, ivecIte iteE)
{if(iteE < iteB) {cout<<"wrong in iterator range!"<<endl;exit(0);}return iteE - iteB;
}
ivecIte partition(vector<int> &ivec, ivecIte iteB, ivecIte iteE)
{chkivIte(iteB, iteE);//ite1指向大于*(iteE-1)队列的最左边的元素ivecIte ite1 = iteB, ite2;for(ite2 = iteB; iteE-1 != ite2; ++ite2) {if( *ite2 < *(iteE-1)) {if( ite1!= ite2) {//ite1与ite2指向相同时不能使用^*ite1 = *ite1 ^ *ite2;*ite2 = *ite1 ^ *ite2;*ite1 = *ite1 ^ *ite2;}++ite1;}}//如果ite为iteE-1,说明iteE-1指向最大值,要将其排出//而且两者相等时不能用^if(ite1 != iteE-1){*ite1 = *ite1 ^ *(iteE - 1);*(iteE - 1) = *ite1 ^ *(iteE - 1);*ite1++ = *ite1 ^ *(iteE - 1);}return ite1;
}ivecIte rndPartition(vector<int> &ivec, ivecIte iteB, ivecIte iteE)
{srand((unsigned)time(NULL));ivecIte iteRnd = iteB + rand() % (iteE-iteB);if(iteRnd != iteE-1) {*iteRnd = *iteRnd ^ *(iteE - 1);*(iteE-1) = *iteRnd ^ *(iteE - 1);*iteRnd = *iteRnd ^ *(iteE - 1);}return partition(ivec, iteB, iteE);
}void rndQuickSort(vector<int> &ivec, ivecIte iteB, ivecIte iteE)
{if(1 < iteE-iteB) {ivecIte iteP = rndPartition(ivec, iteB, iteE);rndQuickSort(ivec, iteB, iteP);rndQuickSort(ivec, iteP, iteE);}
}int main() 
{vector<int> ivec;int inData;cout<<"input some integers with end-of-file!"<<endl;while(cin>>inData)ivec.push_back(inData);rndQuickSort(ivec, ivec.begin(), ivec.end());for(ivecIte ite = ivec.begin(); ivec.end() != ite; ++ite) cout<<setw(5)<<*ite;cout<<endl;system("PAUSE");return EXIT_SUCCESS;
}

这篇关于算法导论CLRS 7.3 随机版快速排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---