重排数组负数在前非负在后

设计一个算法：要求在O(n)的时间内重排数组a[0...n-1],将所有取负值的关键码排在所有取非负关键码的前面

实现思路

根本上就是快排partition一趟的过程。我们只需要在快排上稍作改动即可。
可与快排代码比较（在另外一篇博客中）

实现代码

public class Partition {

    public static int[] sort(int[] a, int key) {
        if (a == null && a.length <= 1) {
            return a;
        }
        int high = a.length - 1;
        int low = 0;
        while(low < high) {
            while (low < high && a[high] >= key) high--;
            if(low < high) {
                //直接等于的话会丢失第一个元素
                swap(a,low,high);
                low++;
            }
            while (low < high && a[low] < key) low++;
            if(low < high) {
                swap(a,low,high);
                high--;
            }
        }
        return a;
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

测试代码

public class Test {
    public static void main(String[] args) {
        int[] b = {1, 2, -3, -2, 3, -2, -4, 22, 3, 4, -2};
        int[] result = Partition.sort(b,0);
        System.out.println(Arrays.toString(result));
    }
}
输出结果：[-2, -4, -3, -2, -2, 1, 3, 22, 3, 4, 2]