#include <iostream>
#include <stdlib.h>
using namespace std;

#define MAX_LENGTH_INSERT_SORT 7

#define MAXSIZE 10

void ISort( int k[], int n )
{
    int i, j,temp;
    
    for( i=1; i < n;i++ )
    {
        if( k[i] < k[i-1] )
        {
            temp = k[i];
            
            for( j=i-1; k[j] > temp;j-- ) //找位置并且向后推移 
            {
                k[j+1] = k[j];
            }
            
            k[j+1] = temp;
        }
    }
}

void InserSort(int k[], int low,int high)
{
    ISort(k+low, high-low+1);
}


void swap(int k[], int low,int high)
{
    int temp;
    
    temp = k[low];
    k[low] = k[high];
    k[high] = temp;
}

int Partition(int k[], int low, int high)
{
    int point;
    
    int m = low + (high - low)/2;
    
    if(k[low] > k[high])
    {
        swap(k, low ,high);
    } 
    if(k[m] > k[high])
    {
        swap(k, m ,high);
    }
    if(k[m] > k[low]) // 使得low存放中间的值 
    {
        swap(k, m, low);
    }
    
    point = k[low];
    
    while(low < high)
    {
        while( low < high && k[high] >= point ) //过滤掉比low大的 
        {
            high--;
        }//出了循环说明要进行移动 
        k[low] = k[high]; 
        
        while( low < high && k[low] <= point ) 
        {
            low++;
        } //出了循环说明左边大于右边 要进行移动 
        k[high] = k[low]; 
        
    }
    
    k[low] = point;
    
    return low; 
}


void QSort(int k[], int low, int high)
{
    int point;
    
    if( high - low > MAX_LENGTH_INSERT_SORT )
    {
        point = Partition(k , low , high);
        
        QSort(k, low,point-1); //左边 
        
        QSort(k, point+1, high); // 右边 
         
    }
    else
    {
        InserSort(k, low, high);
    }
}

void QuickSort( int k[], int n )
{
    QSort( k, 0, n-1 );
}

int main()
{
    int i ,a[10] = {5,2,6,0,3,9,1,7,4,8};
    
    QuickSort(a,10);
    
    for( i=0; i < 10 ;i++ )
    {
        cout << a[i];
    }
    
    cout << endl;
    
    return 0;
}