排序算法之快速排序

/*
 * quickSort.cpp
 *
 *  Created on: 2017年6月4日
 *      Author: MrZhang
 */

#include <iostream>
using namespace std;

template <typename T >
int partition( T arr[], int iLeft, int iRight )
{
    T pivot = arr[iLeft];
    int L = iLeft, R = iRight;  //初始化时，L指向第一个坑。

    while( L < R )
    {
        while( arr[R] >= pivot && R > L )  //直到由此留由一个坑，才能进行下面的循环
        {
            R--;
        }
        arr[L] = arr[R];

        while( arr[L] <= pivot && L < R )
        {
            L++;
        }
        arr[R] = arr[L];
    }
    arr[L] = pivot;
    return L;
}

template < typename T >
void __quickSort( T arr[], int iLeft, int iRight )
{
    if( iLeft >= iRight )
    {
        return;
    }
    int p = partition(arr, iLeft, iRight );
    __quickSort( arr, iLeft, p - 1 );
    __quickSort( arr, p + 1, iRight );
}

template < typename T >
void quickSort( T arr[], int iMaxNum )
{
    __quickSort( arr, 0, iMaxNum -1 );
}

int main( )
{
    //setbuf(stdout,NULL);
    unsigned int pucBuff[10] = {3,4,1,7,3,7,8,9,4,0};
    cout << "排序前\n" << endl;
    for( unsigned int i = 0; i < sizeof(pucBuff)/sizeof(int); i++ )
    {
        cout << pucBuff[i] << " " ;
    }
    cout << endl;

    quickSort( pucBuff, sizeof(pucBuff)/4 );
    cout << "排序后\n" << endl;
    for( unsigned int i = 0; i < sizeof(pucBuff)/4; i++ )
    {
        cout<< pucBuff[i]<< " ";
    }
    cout<<endl;
    return 1;
}