#include<stdio.h>
typedef int elemtype;
void Part(elemtype r[], int low, int high, int *pivotloc);
void QuickSort(elemtype r[], int low, int high);
int main()
{
    int i, m;
    elemtype r[1000];
    while (1)
    {
        scanf("%d", &m);
        for (i = 0; i < m; i++)
        {
            scanf("%d", &r[i]);
        }
        QuickSort(r, 0, m - 1);
        printf("\n排序结果-------------------------\n");
        for (i = 0; i < m; i++)
        {
            printf("%d ", r[i]);
        }
    }
    system("pause");
    return 0;
}
void Part(elemtype r[], int low, int high, int *pivotloc)
{
    int j, l = low, h = high;
    elemtype pivotkey = r[low];//确定比较基数 
    while (high != low)
    {
        while (low < high && pivotkey <= r[high])//查找r[low]右边小于pivotkey的元素r[high] 
        {
            high--;
        }
        if (low < high)
        {
            r[low] = r[high];
            low++;
        }
        while (low < high && r[low] <= pivotkey)//查找r[high]左边大于pivotkey的元素r[low] 
        {
            low++;
        }
        if (low < high)
        {
            r[high] = r[low];
            high--;
        }
    }
    r[high] = pivotkey;//将比较基数pivotkey赋给分界点 
    *pivotloc = high;//标记分界点 
    for (j = l; j <= h; j++)
    {
        if (j == low)
        {
            printf("<%d> ", r[j]);//打印分界点的值; r[l]到r[low-1]的所有元素都小于分界点, r[low+1]到r[h]得所有元素都大于分界点 
        }
        else
        {
            printf("%d ", r[j]);
        }
    }
    printf("\n");
}
void QuickSort(elemtype r[], int low, int high)
{
    int i, j;
    if (low < high)
    {
        Part(r, low, high, &i);
        //因为Part函数，使r[low]到r[i-1]的所有元素都小于r[i], r[i+1]到r[high]得所有元素都大于r[i]，所以不需要在将r[i]参与排序 
        QuickSort(r, low, i - 1);    
        QuickSort(r, i + 1, high);
    }
}
/*
10
9 11 4 5 21 17 15 13 11 4
*/