完整算法实现

1 /** 2  * 将数组中0全部后置 eg: [1,2,0,3] --> [1,2,3,0] 3  *  4  * @author kangye 5  */ 6 public class MoveZerosInArray { 7  8     /** 9      * 冒泡实现 O(N^2)10      */11     public void moveSorting(int[] array) {12         validateArray(array);13 14         boolean swap = true;15         while (swap) {16             swap = false;17             for (int i = 0; i < array.length - 1; i++) {18                 if ((array[i] < array[i + 1] && array[i + 1] > 0)) {19                     swap(array, i, i + 1);20                     swap = true;21                 }22             }23         }24     }25 26     /**27      * 优化， O(N)28      */29     public void moveUsingTwoPointers(int[] array) {30         validateArray(array);31 32         int left = 0;33         int right = array.length - 1;34         while (left < right) {35             if (array[left] == 0 && array[right] != 0) {36                 swap(array, left, right);37             }38             if (array[left] != 0) {39                 left++;40             }41             if (array[right] == 0) {42                 right--;43             }44         }45     }46 47     private void validateArray(int[] array) {48         if (array == null) {49             throw new IllegalArgumentException("You can't pass a null array as argument.");50         }51     }52 53     private void swap(int[] array, int a, int b) {54         int temp = array[a];55         array[a] = array[b];56         array[b] = temp;57     }58 }

补充一个单元测试,写法注意：

 1. 至于test目录下, 保持包名相同

 2. 类名和原测试类保持一致，增加Test后缀，方法名增加test

 3. 尽量使用junit原声断言，和异常申明（有时间补充一篇单元测试方法）

1 /**  2  * @author kangye  3  */  4 public class MoveZerosInArrayTest {  5   6     private MoveZerosInArray moveZeros;  7   8     @Before  9     public void setUp() { 10         moveZeros = new MoveZerosInArray(); 11     } 12  13     @Test(expected = IllegalArgumentException.class) 14     public void shouldNotAcceptNullArraysSorting() { 15         moveZeros.moveSorting(null); 16     } 17  18     @Test 19     public void shouldWorkWithAnEmptyArraySorting() { 20         int[] array = new int[0]; 21  22         moveZeros.moveSorting(array); 23  24         assertArrayEquals(new int[0], array); 25     } 26  27     @Test 28     public void shouldOrganizeAnArrayFullOfZerosSorting() { 29         int[] array = { 0, 0, 0, 0, 0 }; 30  31         moveZeros.moveUsingTwoPointers(array); 32  33         int[] expected = { 0, 0, 0, 0, 0 }; 34         assertArrayEquals(expected, array); 35     } 36  37     @Test 38     public void shouldOrganizeAnArrayFullOfNonZerosSorting() { 39         int[] array = { 1, 1, 1, 1, 1 }; 40  41         moveZeros.moveUsingTwoPointers(array); 42  43         int[] expected = { 1, 1, 1, 1, 1 }; 44         assertArrayEquals(expected, array); 45     } 46  47     @Test 48     public void shouldOrganizeAnArrayWithZerosAndNonPositiveIntegersSorting() { 49         int[] array = { 1, 0, 2, 3, 0 }; 50  51         moveZeros.moveUsingTwoPointers(array); 52  53         assertZerosAtRight(array); 54     } 55  56     @Test 57     public void shouldOrganizeAnArrayWithZerosPositiveAndNegativeIntegersSorting() { 58         int[] array = { 1, 0, 2, -3, 0, 0, 0, 0, -1 }; 59  60         moveZeros.moveUsingTwoPointers(array); 61  62         assertZerosAtRight(array); 63     } 64  65     @Test(expected = IllegalArgumentException.class) 66     public void shouldNotAcceptNullArraysWithTwoPointers() { 67         moveZeros.moveUsingTwoPointers(null); 68     } 69  70     @Test 71     public void shouldWorkWithAnEmptyArrayWithTwoPointers() { 72         int[] array = new int[0]; 73  74         moveZeros.moveUsingTwoPointers(array); 75  76         assertArrayEquals(new int[0], array); 77     } 78  79     @Test 80     public void shouldOrganizeAnArrayFullOfZerosWithTwoPointers() { 81         int[] array = { 0, 0, 0, 0, 0 }; 82  83         moveZeros.moveUsingTwoPointers(array); 84  85         int[] expected = { 0, 0, 0, 0, 0 }; 86         assertArrayEquals(expected, array); 87     } 88  89     @Test 90     public void shouldOrganizeAnArrayFullOfNonZerosWithTwoPointers() { 91         int[] array = { 1, 1, 1, 1, 1 }; 92  93         moveZeros.moveUsingTwoPointers(array); 94  95         int[] expected = { 1, 1, 1, 1, 1 }; 96         assertArrayEquals(expected, array); 97     } 98  99     @Test100     public void shouldOrganizeAnArrayWithZerosAndNonPositiveIntegersWithTwoPointers() {101         int[] array = { 1, 0, 2, 3, 0 };102 103         moveZeros.moveUsingTwoPointers(array);104 105         assertZerosAtRight(array);106     }107 108     @Test109     public void shouldOrganizeAnArrayWithZerosPositiveAndNegativeIntegersWithTwoPointers() {110         int[] array = { 1, 0, 2, -3, 0, 0, 0, 0, -1 };111 112         moveZeros.moveUsingTwoPointers(array);113 114         assertZerosAtRight(array);115     }116 117     private void assertZerosAtRight(int[] array) {118         boolean zeroFounded = false;119         for (int i : array) {120             if (zeroFounded) {121                 assertEquals(0, i);122             } else if (i == 0) {123                 zeroFounded = true;124             }125         }126     }127 }