微软intern面经，求答案

以前写的太乱了, 更新一个

1. 
   
2. void swapRange(int a[], int nLft, int nRgt)
   
3. {
   
4.         assert(a);
   
5.         while (nLft < nRgt)
   
6.                 swap(a[nLft++], a[nRgt--]);
   
7. }
   
8. 
   
9. void ReArrange(int a[], int n)
   
10. {
    
11.         assert(a);
    
12. 
    
13.         if (n <= 1) return;
    
14. 
    
15.         ReArrange(a, n/2);
    
16.         ReArrange(a + n/2, n - n/2);
    
17. 
    
18.         int nLft = 0;
    
19.         int nRgt = n-1;
    
20.         while (a[nLft] < 0) nLft++;
    
21.         while (a[nRgt] >= 0) nRgt--;
    
22. 
    
23.         if (nLft > nRgt) return;
    
24. 
    
25.         swapRange(a, nLft, nRgt);
    
26. 
    
27.         int nMid = nLft;
    
28.         while (nMid < n && a[nMid] < 0) nMid++;
    
29.         swapRange(a, nLft, nMid-1);
    
30.         swapRange(a, nMid, nRgt);
    
31. }
    

复制代码

回复 27# jintian1_84

传送门
http://www.1point3acres.com/bbs/thread-10164-1-1.html

程序写起来逻辑不想清楚也会卡住
if (nLft > nRgt) return; 这段逻辑要是不退出放在后面一起处理麻烦死了会....

回复 32# tsy3602

谢谢

回复 31# wwwyhx

这个看起来简洁很多，好好学习学习

Mark!
“一般递归log(n)的栈空间不算进去”

不知道 STL 的 stable_partition 时空是多少

会是乱序吗？
用两个指针，依次向前遍历，第一个指针专门找正数，每次遇到正数就停止，第二个指针专门找负数，当他们找到的时候，依次交换两个指针指向的内容，然后继续向前找，不就可以了吗？这样的复杂度是n，空间是1.

回复 38# bingjie

会 如 -1 3 -2 1 -5 =>3 1 -2 -1 -5

不就是快排的其中一个步骤么