荷兰旗帜问题

1.假设有若干红，白，蓝色三种球，要求以红色，白色，蓝色的顺序给这些球排序。给出你的算法
2.找出无序数组的重复元素。时间复杂度o
(nlogn).
空间复杂度o(1)

对于第一题，假设用0,1,2来表示红白蓝三种球。
思路2：sortByOneIndex（），storeIndex=0,遍历数组，找出比1小的所有元素，放在storeIndex的位置，storeIndex++.然后从storeIndex开始再遍历一次数组，找到等于1的所有元素，放到storeIndex的位置，storeIndex++.这样三种球即可按红白蓝三种颜色顺次摆放。

/**
 * @author jy
 * @date 2018年6月11日
 * <p>Description: </p> 
 */
package sort;

import java.util.Arrays;

/**
 * @author jy
 *
 */
public class MyCalc {
    public static void sort(int a[]) {
        int pivot = 1;
        int leftIndex = 0;
        int rightIndex = a.length - 1;
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > pivot) {
                count++;
            }

        }
        for (int i = 0; i < a.length - count; i++) {
            if (a[i] < pivot && i != leftIndex) {
                swap(a, i, leftIndex);
                leftIndex++;
            } else if (a[i] > pivot && i != rightIndex) {
                if (a[rightIndex] > pivot) {
                    rightIndex--;
                } else {
                    swap(a, i, rightIndex);
                    rightIndex--;
                }

            }
        }

    }

    public static void sortByOneIndex(int a[]) {
        int pivot = 1;
        int storeIndex = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < pivot && i != storeIndex) {
                swap(a, storeIndex, i);
                storeIndex++;
            }

        }
        for (int i = storeIndex; i < a.length; i++) {
            if (a[i] == pivot && i != storeIndex) {
                swap(a, storeIndex, i);
                storeIndex++;
            }

        }
    }

    /**
     * @param a
     * @param i
     * @param leftIndex
     *            <p>
     *            Description:
     *            </p>
     */
    private static void swap(int[] a, int i, int j) {

        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;

    }

    public static void main(String args[]) {
        MyCalc calc = new MyCalc();
        int a[] = new int[10];
        for (int i = 0; i < a.length; i++) {
            int rand = (int) (Math.random() * 3);
            a[i] = rand;

        }
        System.out.println(Arrays.toString(a));
        calc.sort(a);
        System.out.println(Arrays.toString(a));

        // calc.sortByOneIndex(a);
        // System.out.println(Arrays.toString(a));

    }
}

双指针：

  public static void sort(int a[]) {
      int pivot = 1;
      int leftIndex = 0;
      int rightIndex = a.length - 1;

      for (int i = 0; i <= rightIndex; i++) {//注意此处i<=rightIndex
          if (a[i] < pivot) {
              swap(a, i, leftIndex);
              leftIndex++;
          } else if (a[i] > pivot) {
              swap(a, i, rightIndex);
              rightIndex--;
              i--;//后面移过来的元素有可能还需要再移动
          }

      }

  }