问题说明

Gold King的快排使用已经有一段时间了，于是在想快排有没有精简的优化。
功夫不负有心人，Gold King还真找到了些有用的东西，譬如：1、排序算法在稳定性上，快排是属于不稳定排序的，但是如果在判断的时候加上等号相等时，不参与交换操作，这样可以让快排进行稳定排序。2、采用取序列最右边的数作为枢纽元的方法。3、快排要从左右两边各找一个不符合从小到大要求的数（通过两个循环查找，用i表示先从左向右，用j表示从右向左，每个循环查找结束后，对当前找到的数赋值到数组上，再在这个下标做自身加减操作）。4、左右下标相等时，那个位置放上步骤2中的中间数。
试着按除步骤1之外的步骤执行之后每趟中间数排好序之后的数据输出。

输入格式

输入一个正整数n，表示有n个整数，接下来输入这个n个数，每个数在int范围之内。

输出格式

输出按除步骤1之外的步骤执行之后每趟中间数排好序之后的数据。

10
45 76 23 87 32 98 12 67 34 94

45 76 23 87 32 34 12 67 94 98
45 12 23 34 32 67 87 76 94 98
23 12 32 34 45 67 87 76 94 98
12 23 32 34 45 67 87 76 94 98
12 23 32 34 45 67 87 76 94 98
12 23 32 34 45 67 76 87 94 98

提示

1<=n<=10000

来源/分类

算法培训-05-分治（归并、快排等）