本文共 3143 字，大约阅读时间需要 10 分钟。

Give you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed. eg. -1 1 3 -2 2 ans: -1 -2 1 3 2. o(n)time complexity and o(1) space complexity is perfect.

---------------------------------------------------------

Method 1:

If the array is stored in a list, o(n)

Method 2:

If the array is stored in an array, at least o(nlogn), the following the o(n^2) solution:

public class PosiNegSort {	/**	 * @param args	 */	public static void main(String[] args) {		int [] nums = {-1, 2, 4, -8, 10, 9, 100, -3, 2};		for(int i : posiNegSort(nums))			System.out.print(i + " ");	}	public static int[] posiNegSort(int [] nums){		int p = 0; 		int q = 0;		while ( q < nums.length){			while (nums[p] < 0)				p++;			q = p;			while(q < nums.length && nums[q] > 0 )				q++;			if (q == nums.length)				break;			for(int i = q; i > p; i--){				int t =nums[i-1];				nums[i-1] = nums[i];				nums[i] = t;							}		}		return nums;	}}

Method 3:

This can be done in O(nlogn) using divide and conquer scheme. Before starting the algorithm, please see the following observation: 

Observation: given an array A, say [1, -2, ..., 4], with n elements, we can get the inverse of A, denoted as A’ (4, …, -2, 1), in \theta(n) time with O(1) space complexity. 

The basic idea of the algorithm is as follows: 
1. We recursively ‘sort’ two smaller arrays of size n/2 (here ‘sort’ is defined in the question) 
2. Then we spend \theta(n) time merging the two sorted smaller arrays with O(1) space complexity. 
How to merge? 
Suppose the two sorted smaller array is A and B. A1 denotes the negative part of A, and A2 denotes positive part of A. Similarly, B1 denotes the negative part of B, and B2 denotes positive part of B. 
2.1. Compute the inverse of A2 (i.e., A2’) in \theta(|A2|) time; compute the inverse of B1 (i.e., B1’) in \theta(|B1|) time. [See observation; the total time is \theta(n) and space is O(1)] 
Thus the array AB (i.e., A1A2B1B2) becomes A1A2’B1’B2. 
2.2. Compute the inverse of A2’B1’ (i.e., B1A2) in \theta(|A2|) time. [See observation; the total time is \theta(n) and space is O(1)] 
Thus the array A1A2’B1’B2 becomes A1B1A2B2. We are done. 

Time complexity analysis: 
T(n) = 2T(n/2) + \theta(n) = O(nlogn)

#include
   
    #include
    
     #include
     
      using namespace std;void ReverseSort(vector
      
       & arr, int a, int b, int c) {  reverse(arr.begin()+a, arr.begin()+b);  reverse(arr.begin()+b, arr.begin()+c);  reverse(arr.begin()+a, arr.begin()+c);}void SpecialSort(vector
       
        & arr) {  int n = arr.size(), i, cnt = 0, a, b, c;  do {    for (i = 0; i < n && arr[i] < 0; ++i);    a = i;    cnt = 0;    while (i < n) {      for (; i < n && arr[i] > 0; ++i);      if (i != n)        ++cnt;      b = i;      for (; i < n && arr[i] < 0; ++i);      c = i;      ReverseSort(arr, a, b, c);      a = i;    }  }  while (cnt > 0);}int main() {  int arr[] = {1,-1,2,-2,3,-3};  vector
        
          a(arr, arr+6); SpecialSort(a); return 0;}
        
       
      
     
    
   

转载地址：http://vrfoi.baihongyu.com/