7.1 快速排序
[cpp]/*7.1 快速排序
*QUICK-SORT
*/
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<vector>
using namespace std;
typedef vector<int>::iterator ivecIte;
size_t chkivIte(ivecIte iteB, ivecIte iteE)
{
if(iteB > iteE) {
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;
}
void quickSort(vector<int> &ivec, ivecIte iteB, ivecIte iteE)
{
chkivIte(iteB,iteE);
if(1 < iteE-iteB) { //至少有两个元素时才比较
ivecIte iteP = partition(ivec, iteB, iteE);
quickSort(ivec, iteB, iteP);
quickSort(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);
quickSort(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;
补充:软件开发 , C++ ,