/*快速排序算法实现
 * key的值在一次递归中是保持不变的，递归函数体就是把整个数
 * 组小于key的值放置在key的左边，大于key的放置在key的
 * 右边，接着改变数组长度，递归
 * */
package com;
public class Test1{
    private int a[] = new int[]{49,38,65,97,76,13,27};
    private final int LEFT = 1;
    private final int RIGHT = 2;
    private int flag = LEFT;
    public void fast_sort(int index,int n)
    {
        int key = a[index];
        int i = index;
        int j = n;
        while(i < j)
        {
            if(flag == LEFT)
            {
                if(key > a[j])
                {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    //key = a[j];
                    flag = RIGHT;    
                    i++;
                }
                else
                {
                    j--;
                }
            }
            else
            {
                if(key < a[i])
                {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    //key = a[i];
                    flag = LEFT;    
                    j--;
                }
                else
                {
                    i++;
                }
            }
        }
        if(index < i-1)
        {
            fast_sort(index,i-1);
        }
        if(i+1 < n)
        {
            fast_sort(i+1,n);
        }
    }
    public void swap(int a,int b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
    public void print()
    {
        for(int i = 0; i < 7; i++)
        {
            System.out.print(a[i]+" ");
        }
    }
    public static void main(String[] args)
    {
        Test1 t1 = new Test1();
        t1.fast_sort(0,6);
        t1.print();
    }
}