# 算法-一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来的正负数之间相对顺序

### 评论（4）

2017-08-27 4 楼

/**
* 具体原理：
* 以栈的形势将负数存在最左边
*/
import java.util.*;
public class Test
{
public static void main(String args[])
{
int[]x={1,7,-5,-12,-13,99,-6,31,15};
int p=0;
for(int i=x.length-1;i>p;)
{
if(x[i]<0)
{
int j=i;
while(j!=0)
{
int t=x[j];
x[j]=x[j-1];
x[j-1]=t;//交换
j--;
}
p++;
}
else i--;
}
System.out.println(Arrays.toString(x));
}
}

2017-08-14 3 楼

PS：我对O(N),O(1)的概念理解不是很清楚，所以算法可能不符合要求吧，请多赐教

```#include <iostream>

using namespace std;

int input[] = {1,7,-5,9,-12,15};

template<typename T>
void sort_deposit(T* in, size_t len)
{
int deposit_count = 0;
T temp;
for(int i = 0; i < len; ++i)
{
if(in[i] > 0)
{
++deposit_count;
}
else
{
int count = deposit_count;
int base_index = i - count;
temp = in[i];
do {
in[base_index + count] = in[base_index + count - 1];
} while(--count);
in[base_index] = temp;
}
}
}

int main(int argc, char* argv[])
{
sort_deposit(input, sizeof(input)/sizeof(int));
for(int i = 0; i < sizeof(input)/sizeof(int); ++i)
{
cout << input[i] << "t";
}
cout << endl;
return 0;
}```

2017-03-25 2 楼

step1：定义int型变量start和end，分别指示数组开始和结束。
step2：while(start<end) step3;step4;step5;
step3: while(arr[start]<0)start++;
step4: while(arr[end]>0)end--;
step5: arr[end]<-->arr[start];

2017-01-10 1 楼

template<class _BidIt, class _Pr>
inline _BidIt stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
{ // partition preserving order of equivalents, using _Pred
return _First == _Last ? _First
: _Stable_partition(_First, _Last, _Pred, _Dist_type(_First), _Val_type(_First);
}

template<class _BidIt,
class _Pr,
class _Diff,
class _Ty> inline
_BidIt _Stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
_Diff _Count, _Temp_iterator<_Ty>& _Tempbuf)
{ // partition preserving order of equivalents, using _Pred
if (_Count == 0)
return (_First);
else if (_Count == 1)
return (_Pred(*_First) ? _Last : _First);
else if (_Count <= _Tempbuf._Maxlen())
{ // temp buffer big enough, copy right partition out and back
_BidIt _Next = _First;
for (_Tempbuf._Init(); _First != _Last; ++_First)
if (_Pred(*_First))
*_Next++ = _Move(*_First);
else
*_Tempbuf++ = _Move(*_First);

_Move(_Tempbuf._First(), _Tempbuf._Last(), _Next); // copy back
return (_Next);
}
else
{ // temp buffer not big enough, divide and conquer
_BidIt _Mid = _First;

_BidIt _Left = _Stable_partition(_First, _Mid, _Pred,
_Count / 2, _Tempbuf); // form L1R1 in left half
_BidIt _Right = _Stable_partition(_Mid, _Last, _Pred,
_Count - _Count / 2, _Tempbuf); // form L2R2 in right half

_Diff _Count1 = 0;
_Distance(_Left, _Mid, _Count1);
_Diff _Count2 = 0;
_Distance(_Mid, _Right, _Count2);

return (_Buffered_rotate(_Left, _Mid, _Right,
_Count1, _Count2, _Tempbuf)); // rotate L1R1L2R2 to L1L2R1R2
}
}

1915 主题
5625 回复
23501 人气