题目：两组数，左边为已升序排列称为S,右边的未排序称为R，在空间复杂度为O（1）的情况下将所有数排序

思路：两组数为两个栈，S是可以为空的。循环以下基本操作，直到R为空：

　　   弹出R的栈顶，用变量T保存，由于S为升序排列，所以栈顶为最大，那么只要S的

　　   栈顶比T大就将S的栈顶弹出并推进R，直到S的栈顶比T小，此时将T推入S

代码（JS版）：

1 function stackInsertSort(R) { 2     var S = []; 3     while(R.length){ 4         var T = R.pop(); 5         while(S.length && S[S.length-1] > T){ 6             R.push(S.pop()) 7         } 8         S.push(T); 9     }10     return S11 }12 13 var n = 1000;14 var R = [];15 for (var i = 0; i < n; i++) {16     R.push(Math.floor(Math.random()*10000))17 }18 19 console.log(R)20 var t1 = Date.now()21 var s = stackInsertSort(R)22 console.log("time:----------")23 console.log(Date.now() - t1)24 console.log("----------")25 console.log(s)

 

延伸： 直方图最大面积问题