算法-QuickSort

 #include <stdlib.h>

 #include <iostream>

 #include <vector>

 using namespace std;

 template <class T>

 void print_array(const vector<T> &array)

 {

     for ( unsigned int i = ; i < array.size() + ; ++i )

     {

         cout<<array[i-]<<" ";

         if ( array[i - ] <  )

             cout<<" ";

         if ( i %  ==  )

             cout<<endl;

     }

 }

 template <class T>

 void shuffling(vector<T> &array)

 {

     int n = array.size();

     for ( int i = ; i < n; ++ i )

     {

         int r = i ==  ?  : rand() % i;

         T temp = array[i];

         array[i] = array[r];

         array[r] = temp;

     }

     return;

 }

 template <class T>

 unsigned int partition(vector<T> &array, unsigned int lo, int unsigned hi)

 {

     if ( lo == hi ) return lo;

     unsigned int i = lo;

     unsigned int j = hi;

     T partition_val = array[lo];

     while ( i < j )

     {

         while ( array[i] <= partition_val )

         {

             if ( i < hi ) ++i;

             else break;

         }

         while ( array[j] > partition_val )

         {

             if ( j > lo ) --j;

             else break;

         }

         if ( i < j )

         {

             T temp = array[i];

             array[i] = array[j];

             array[j] = temp;

         }

     }

     array[lo] = array[j];

     array[j] = partition_val;

     return j;

 }

 template <class T>

 void quick_sort(vector<T> &array, unsigned int  lo, unsigned int  hi)

 {

     if ( lo >= hi ) return;

     int partition_pos = partition(array, lo, hi);

     quick_sort(array, lo, partition_pos);

     quick_sort(array, partition_pos + , hi);

     return;

 }

 int main()

 {

     vector<int> array;

     for ( int i = ; i < ; ++i )

         array.push_back(i);

     cout<<"shuffling the array..."<<endl;

     shuffling(array);

     cout<<"the shuffled array: "<<endl;

     print_array(array);

     cout<<"quick sort the array: "<<endl;

     quick_sort(array, , array.size() - );

     cout<<"array after quick sorted: "<<endl;

     print_array(array);

     return ;

 }

输出结果：