快速排序

#include <iostream>

#include <stdlib.h>

#include <algorithm>

#include <set>

#define LEN 20

// Quick sort

int Partition(int *array, int s, int e)
{
     int stand = array[e - 1];
     int idx = s;
     for(int i = s; i < e; ++i)
     {
         if (array[i] < stand)
             std::swap(array[i], array[idx++]);
     }
     std::swap(array[idx], array[e - 1]);
     return idx;
}

void sort_quick(int *array, int s, int e)
{
     if (s < e )
     {
         int q = Partition(array, s, e);
         sort_quick(array, s, q);
         sort_quick(array, q + 1, e);
     }
}

void sort_quick2(int *array, int n)
{
     std::set<std::pair<int, int> > range;
     range.insert(std::make_pair(0, n));
     do
     {
         std::pair<int, int> tmp = *range.begin();
         range.erase(range.begin());
         int pT = Partition(array, tmp.first, tmp.second);
         if (pT - tmp.first > 1)
             range.insert(std::make_pair(tmp.first, pT));
         if (tmp.second - pT > 1)
             range.insert(std::make_pair(pT + 1, tmp.second));
     }while(range.size() != 0);
}

int main()
{
     int array[LEN];
     for(int i = 0; i < LEN; ++i)
         array[i] = rand() % LEN;
     std::cout << "Before sort:\t";
     for(int i = 0; i < LEN; ++i)
         std::cout << array[i] << " ";
     std::cout << "\n";
     //sort_quick(array, 0, LEN);

     sort_quick2(array, LEN);
     std::cout << "After sort:\t";
     for(int i = 0; i < LEN; ++i)
         std::cout << array[i] << " ";
     std::cout << "\n";
}