Lintcode463 Sort Integers soluti

【题目描述】

Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n2) algorithm.

给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。

【题目链接】

www.lintcode.com/en/problem/sort-integers/

【题目解析】

根据题目提示，可以设想利用另一个stack作为临时储存空间，设定的规则是：

从origin stack中不断pop() element

对于helper stack，如果helper stack peek() < element，则将helper stack中的元素全部转移到origin stack

再将element push()到helper stack中

不断重复上述步骤，直到origin stack isEmpty

最后，所有的元素已经按照descending order排序好（smallest on top），只需将其转移到origin stack，则origin stack即为所需排序

时间复杂度为O(n^2)，空间复杂度为O(n)

【参考答案】

www.jiuzhang.com/solutions/sort-integers/