首页 > 代码库 > 数组排序使得数组负数在正数左边且按照原来的顺序

数组排序使得数组负数在正数左边且按照原来的顺序

2024-07-05 08:40:41   222人阅读

假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数件和正数间元素相对位置不变。时空复杂度要求分别为：o(n),o(1)
例如   
  -3 4 2 -1 7 3 -5  
排序后  
  -3 -1 -5 4 2 7 3 

算法思想：从前往后遍历，记录第一个正数的位置，如果遇到负数就将负数插入到正数前面。

 1 #include "stdafx.h"
 2 #include <iostream>
 3 using namespace std;
 4 
 5 void SplitNumber(int* A, int size);
 6 void PrintArray(int* A, int size);
 7 
 8 int _tmain(int argc, _TCHAR* argv[])
 9 {
10     int A[] = { 0, 2, -2, 3, -3, 4, 5, 7, -10 };
11     int size = sizeof(A) / sizeof(int);
12     PrintArray(A, size);
13     SplitNumber(A, size);
14     PrintArray(A, size);
15 
16     return 0;
17 }
18 
19 
20 void PrintArray(int* A, int size)
21 {
22     for (size_t i = 0; i < size; i++)
23     {
24         cout << A[i] << " ";
25     }
26     cout << endl;
27 }
28 
29 void SplitNumber(int* A, int size)
30 {
31     int posIndex=-1, negIndex=-1;
32     for (size_t i = 0; i < size; i++)
33     {
34         if (negIndex==-1)
35         {
36             if (A[i]<0 && posIndex >= 0)
37             {
38                 negIndex = i;
39             }
40             if (A[i]>0 && posIndex < 0)
41             {
42                 posIndex = i;
43             }
44         }
45         if (negIndex>=0&&posIndex>=0)
46         {
47             int tmp = A[i];
48             for (size_t i = negIndex; i >posIndex; i--)
49             {
50                 A[i] = A[i - 1];
51             }
52             A[posIndex] = tmp;
53             posIndex++;
54             negIndex = -1;
55         }
56     }
57 }

 


联系
我们