Chinaunix首页 | 论坛 | 博客
  • 博客访问: 8939
  • 博文数量: 9
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 45
  • 用 户 组: 普通用户
  • 注册时间: 2011-08-23 20:55
文章分类

全部博文(9)

文章存档

2016年(9)

我的朋友

分类: C/C++

2016-12-24 17:38:18


转帖:http://www.cnblogs.com/qingliangtea/p/3892352.html
public static void txsort(int[] array)
    {
        int negCount = 0;
        int length = array.length;
        int negIndex =0;
        for(int i=0;i         {
            if(array[i]<0)
                negCount++;
        }
        if(negCount==0)
            return;
        


        for(int i=0;i         {    
            int posIndex = (i-negIndex)%(negCount-negIndex) + negIndex;
            int newIndex = i+negCount - negIndex;
            if(array[posIndex]<0)
            {
                newIndex = negIndex;
                negIndex++;
            }
            
            int temp = array[posIndex];
            array[posIndex] = array[newIndex];
            array[newIndex] = temp;
            
            if(negIndex==negCount)
                break;
        }
        
    }


p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 13.0px Verdana; -webkit-text-stroke: #000000} p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 13.0px Verdana; color: #0433ff; -webkit-text-stroke: #0433ff} span.s1 {font-kerning: none} span.s2 {font-kerning: none; color: #000000; -webkit-text-stroke: 0px #000000} span.s3 {font-kerning: none; -webkit-text-stroke: 0px #000000} table.t1 {border-style: solid; border-width: 1.0px 1.0px 1.0px 1.0px; border-color: #c0c0c0 #c0c0c0 #c0c0c0 #c0c0c0; border-collapse: collapse} td.td1 {width: 321.0px; border-style: solid; border-width: 1.0px 1.0px 1.0px 1.0px; border-color: #c0c0c0 #c0c0c0 #c0c0c0 #c0c0c0; padding: 3.0px 3.0px 3.0px 3.0px} td.td2 {width: 349.0px; border-style: solid; border-width: 1.0px 1.0px 1.0px 1.0px; border-color: #c0c0c0 #c0c0c0 #c0c0c0 #c0c0c0; padding: 3.0px 3.0px 3.0px 3.0px} td.td3 {width: 20.0px; border-style: solid; border-width: 1.0px 1.0px 1.0px 1.0px; border-color: #c0c0c0 #c0c0c0 #c0c0c0 #c0c0c0; padding: 3.0px 3.0px 3.0px 3.0px} td.td4 {width: 13.0px; border-style: solid; border-width: 1.0px 1.0px 1.0px 1.0px; border-color: #c0c0c0 #c0c0c0 #c0c0c0 #c0c0c0; padding: 3.0px 3.0px 3.0px 3.0px} td.td5 {width: 30.0px; border-style: solid; border-width: 1.0px 1.0px 1.0px 1.0px; border-color: #c0c0c0 #c0c0c0 #c0c0c0 #c0c0c0; padding: 3.0px 3.0px 3.0px 3.0px} td.td6 {width: 24.0px; border-style: solid; border-width: 1.0px 1.0px 1.0px 1.0px; border-color: #c0c0c0 #c0c0c0 #c0c0c0 #c0c0c0; padding: 3.0px 3.0px 3.0px 3.0px}

题目要求空间O(1)in-place,时间O(n),且是必须是稳定的。初一看像排序,排序算法中快排的时间复杂度是nlogn。在看一次题目, 只是把正负数分开,不涉及到从大到小。审题很重要。。。。

1 先找出负数的个数N

2 从前到后把元素向后移 负数个位子N, 把后面位置上的数先暂存到前面为负数留的位置上。 当移动 第N+I时,此时N+I 其实是原数组的I, 而N+1 的真实值存在前面的I位置上,所以这里移动的是I 到 N+ I+ N去。

3 遇到负数就往前插 后面的数往后移动 N -1。

4 直到负数全到前面为止

难点: 因为不能开辟新的空间,否则不满足空间复杂度O(1),只能在数组内移动,所以就比较饶。下面把移动演示一下:

0(index)

1

2

3

4

5

1

7

-5

9

-12

15

 

7

1

9

-12

15

-5(1 和 -5 交换 暂存-5 到该位置)

 

 

 

 

 

 

 

1

7

-12

15

-5

9(7和9交换 9暂存到改位置)

 

 

 

 

-5(-5原始index 是2,

这里是把原始位置上的-5插入到第0个位置)

 

1

7

-12

15

 

9

 

 

 

 

-5

 

1

7

9

15

 

-12

(把index 3上的9 往后移动

2(负数的总数) - 1(已经存好的负数个数))

就是把index3 移到index4上

 

 

 

 

-5

-12

1

7

9

15

 

 

要注意int posIndex = (i-negIndex)%(negCount-negIndex) + negIndex; 中的i-negIndex. 去掉已移动。


阅读(253) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册