【题目描述】
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)
【参考答案】
网友评论