当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,