package com.ethan.sort.java;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class QuickSort {
  public static <E extends Comparable<? super E>> List<E> quickSort(List<E> arr) {
    if(arr.size()<=1) {
      return arr;
    }
    E pivot = arr.get(0);
    //每次遞歸都會初始化，每次list都不一樣
    List<E> less = new LinkedList<E>();
    //樞軸,這個集合只有一個元素，每次都初始化，都不一樣
    List<E> pivotList = new LinkedList<E>();
    List<E> more = new LinkedList<E>();
    for(E i:arr){
      if(i.compareTo(pivot)<0) {
        less.add(i);
      } else if(i.compareTo(pivot)>0) {
        more.add(i);
      } else {
        pivotList.add(i);
        //System.out.println("p---->"+i);
      }
    }
    //遞歸
    less = quickSort(less);//比pivot小的
    //又進行quicksort,對more,再分成兩部分
    more = quickSort(more);
    //拼接 less pivot more
    less.addAll(pivotList);
    //pv-------->[23],到最后只有一個元素了
    System.out.println("pv-------->"+pivotList);
    less.addAll(more);
    return less;
  }
  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Integer[] arr = {23,2,8,43,22,32,4,5,34};
    List l = quickSort(Arrays.asList(arr));
    Iterator i = l.iterator();
    while(i.hasNext()) {
      System.out.println(i.next());
    }
  }
}