前言：把一堆整数负数排在左边非负数排在右边

思想：

从两端同时扫描待排序列，左边的关键字为负数的时候则扫描下一个关键字；直到第一个非负数，同理扫描右端的关键字；

把两端的关键字进行相应的交换的操作，直到左右扫描的索引碰头

代码：

1 /** 2  把负数放到左边非负数放到右边 3  4  @param R 待排数组 5  @param len 数组中关键字的个数 6  */ 7 void negative0Positive0(int R[],int len); 8 void negative0Positive0(int R[],int len){ 9     10     int i = 0;11     int j = len-1;12     int temp;13     14     for(;i
      
       = 0) {23             --j;24         }25         26         R[i] = R[j];27         R[j] = temp;28         29  30     }31     32 }
      

测试内容：

1         int R[] = {
    1,2,-2,3,4,-3,0};2         negative0Positive0(R, sizeof(R)/sizeof(int));3         for (int i = 0; i < sizeof(R)/sizeof(int); i ++) {4             printf("%d\t",R[i]);5         }

测试结果

-3 -2 2 3 4 1 0 Program ended with exit code: 0

思考：

上边的算法的时间复杂度为O(n),空间复杂度为O(1)

但是并不能保证原来的正负数的相对顺序保持不变。

如果是要求保证原来的相对顺序不变的情况下，在空间件复杂度为O(n)的情况下；

在创建一个数组来放置关键字，然后从左边遍历的依次按照是为负数时放到目标数组；

然后，与此同时也从右边遍历源关键字记录，为非负数时放到目标数组的右边(从右向左放)。

这样应该能够保证关键字的相对顺序不变，这个内容以后再测试

见有的网址说，和快速排序把枢轴选到第一个关键字有关系，这个问题也在以后作补充吧。

 

参考资料：

严蔚敏版数据结构

数据结构高分笔记

 

 

OS交流群欢迎你的加入！

群二维码：

先写到这么多

如有问题，敬请指正；

如需转载，请注明出处，谢谢!