【第三轮】6.30-7.6 CareerCup 3.6

【解题思路】sort the first N element, pop them into the additional stack, while pushing them back, insert the N+1 element.
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist】https://gist.github.com/nealhu/4cb80acdcfd5a95f18cb

【解题思路】两个stack倒来倒去（详见注释），针对重复的元素，曾加了一个记录个数的变量，遇到当前最小值有多个重复时，一口气push进去
                  循环变量要主意及时更新。
【时间复杂度】 O(n^2)
【空间复杂度】O(n)
【gist link】 https://gist.github.com/xun-gong/38b5bf84b0fd034c9172
           
【test case】: 加入重复元素

【解题思路】Insertion sort.
【时间复杂度】O(N^2)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/873e2027bab8ec7c718f

【解题思路】
1.pop the stack1(original) to a temp
2.if temp less than stack2.peek, pop the stack2 to stack1 until the temp greater than or equal to stack2.peek,
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/weazord/eff06a1bd7bba96781de

【解题思路】
when moving one element to another stack, find its position by moving elements bigger than it back to the original stack


【时间复杂度】
O(n^2)

【空间复杂度】
O(n)

【gist link】
https://gist.github.com/happyWinner/0930e886d563977b5831

【解题思路】
Similar to insertion sort. Use additional stack to do the insertion.

【时间复杂度】
O(n^2)
【空间复杂度】
O(n)

【gist link】
https://gist.github.com/Noahsark/6c66816d39a46930804e