package com.interview.sort;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class QuickSort2 {        //输入是List<Integer>

    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        List<Integer> list = new ArrayList<Integer>();
        list.add(-1);
        list.add(3);
        list.add(-0);
        list.add(-2);
        list.add(-7);
        list.add(-5);
        QuickSort2 qs = new QuickSort2();
        qs.quickSort(list);
        Iterator<Integer> i = list.iterator();
        while (i.hasNext()) {
            int num = (Integer) i.next();
            System.out.println(num);
        }

    }

    public void quickSort(List<Integer> list) {
        if (list.size() > 1) {
            List<Integer> smaller = new ArrayList<Integer>();
            List<Integer> same = new ArrayList<Integer>();
            List<Integer> larger = new ArrayList<Integer>();
            Integer mid = list.get(list.size() >> 1);
            for (Integer i : list) {
                if (i < mid) {
                    smaller.add(i);
                } else if (i > mid) {
                    larger.add(i);
                } else {
                    same.add(i);
                }
            }
            quickSort(smaller);
            quickSort(larger);
            list.clear();
            list.addAll(smaller);
            list.addAll(same);
            list.addAll(larger);
        }
    }

}

import java.util.Arrays;

class Arrays_Quick{
	private int[] arrays;
	private int curNum;

	public Arrays_Quick(int max) {			//建立一个max长度的空数组
		super();
		arrays = new int[max];
		curNum = 0;
	}
	
	public void insert(int value){					//往空的数组里面增加元素
		arrays[curNum] = value;
		curNum++;
	}
	
	public void display(){									//显示数组
		System.out.println(Arrays.toString(arrays));
	}
	
	public void QuickSort(){
		int i=0;
		int j=arrays.length-1;
		
		recQuickSort(i, j);
	}
	
	public void recQuickSort(int i,int j){
		// 结束条件
        if(i == j )
        	return;
         
        int key = arrays[i];
        int stepi = i; 			// 记录开始位置
        int stepj = j; 			// 记录结束位置
         
        while(j > i){
            // j <<-------------- 向前查找
            if(arrays[j] >= key){
                j--;
            }else{
                arrays[i] = arrays[j];
                //i++ ------------>>向后查找
                while(j > ++i){
                    if(arrays[i] > key){
                        arrays[j] = arrays[i];
                        break;
                    }
                }
            }
        }
         
        // 如果第一个取出的 key 是最小的数
        if(stepi == i){
        	recQuickSort(++i, stepj);
            return;
        }
         
        // 最后一个空位留给 key
        arrays[i] = key;
         
        // 递归
        recQuickSort(stepi, i);
        recQuickSort(j, stepj);
    }
}

public class QuickSort {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int maxSize = 5;
		Arrays_Quick arrays_demo = new Arrays_Quick(maxSize);
		arrays_demo.insert(4);
		arrays_demo.insert(5);
		arrays_demo.insert(3);
		arrays_demo.insert(1);
		arrays_demo.insert(2);
		arrays_demo.display();
		arrays_demo.QuickSort();
		arrays_demo.display();
	}

}