package com.swift;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.List;

public class QuickSort {

    /*

     * 快速排序

     */

    public static void main(String[] args) {

        int[] strVoid = new int[] { 11, 66, 22, 0, 55, 2, 0, 11 };

        QuickSort sort = new QuickSort();

        sort.quickSort(strVoid, 0, strVoid.length - 1);

        for (int i = 0; i < strVoid.length; i++) {

            System.out.println(strVoid[i] + " ");

        }

        // 用比较器排序

        List<Integer> list = new ArrayList<Integer>();

        for (Integer i : strVoid) {

            list.add(i);

        }

        Collections.sort(list, new Comparator<Integer>() {

            @Override

            public int compare(Integer arg0, Integer arg1) {

                int num = arg1 - arg0;

                return num;

            }

        });

        for (Integer i : list) {

            System.out.print(i + " | ");

        }

    }

    void quickSort(int[] strDate, int left, int right) {

        int i, j, t, key;

        if (left > right)

            return;

        key = strDate[left]; // temp中存的就是基准数

        i = left;

        j = right;

        while (i != j) {

            // 从后找比key小的或者等的放在key的左边

            while (strDate[j] > key && i < j)

                j--;

            // 从前找比key大的放在key的右边

            while (strDate[i] <= key && i < j)

                i++;

            // 小于就交换位置，等于就停止

            if (i < j) {

                t = strDate[i];

                strDate[i] = strDate[j];

                strDate[j] = t;

            }

        }

        // 两指针相等后，将第一个位置的值与相等处位置的值互换，完成第一轮排序

        strDate[left] = strDate[i];

        strDate[i] = key;

        quickSort(strDate, left, i - 1);// 继续处理左边的，这里是一个递归的过程

        quickSort(strDate, i + 1, right);// 继续处理右边的 ，这里是一个递归的过程

    }

}