java常用排序算法

public class Sort
{
    /**
     * @param args
     */
    public static void main(String[] args)
    {
        int a[] = {2,4,5,3,7,0,1,9,6};

        bubble(a);
        print(a);

        int b[] = {2,4,5,3,7,0,1,9,6};
        select(b);
        print(b);

        int d[] = {2,4,5,3,7,0,1,9,6};
        quick(d, 0, (d.length)-1);
        print(d);
        
        System.out.println(binarySearch(d,9));
        swap(d);
        print(d);

    }

    /**
     * 二分法查找,必须建立在排好序的基础上
     * @param a
     * @param num
     * @return
     */
    private static int binarySearch(int[] a, int num)
    {
        if (a.length<1) return -1;
        int startPos = 0;
        int endPos = a.length - 1;
        int m = (startPos + endPos) / 2;
        while (startPos <= endPos)
        {
            if ( num == a[m]) return m;
            if (num > a[m])
                startPos = m + 1;
            if (num < a[m])
                endPos = m - 1;
            m = (startPos + endPos) / 2;
                
        }
        return -1;
    }

    /**
     * 算法:排序開始時,它選擇列表的中間位置的值作為列表的分隔符v,
     * 於是排序把列表分成兩個列表,一個列表的值小於列表分隔符,
     * 另一個列表的值大於列表分隔符.然後排序在兩個列表中遞歸.
     * 排序每調用自身一次,它就把列表分成更小的列表,直到無法分解,序列就排好了.
     * @param arr
     * @param first
     * @param last
     */
    private static void quick(int[] arr, int first, int last)
    {
        int temp = 0;
        //左邊位置初始化為數組第一個元素
        int low = first;
        //右邊位置初始化為數組最後一個元素
        int high = last;
        int v;
        //System.out.println((first+last) / 2);
        v = arr[(first+last)/2];
        
        do
        {
            //前端元素小於分隔符值的就不需要交換,走到下一個
            while (low < last && arr[low] < v)
            {
                low++;
            }
            //后端元素大於分隔符值的就不需要交換,走到上一個
            while (high > first && arr[high] > v)
            {
                high--;
            }
            //跑出当前段了，结束本段的"互扔"过程
            if (low > high)
            {
                break;
            }
            //开始互换，但 low == high 的情况说明是同一个元素，不用交换
            if (low < high)
            {
                temp = arr[low];
                arr[low] = arr[high];
                arr[high] = temp;
            }
            //交換后往后走
            low++;            
            //交換后往前走
            high--;

        }
        while (true);
        if (first < high)
            //前半段遞歸
            quick(arr, first, high);
        if (low < last)
            //後半段遞歸
            quick(arr, low, last);
    }

    protected static void bubble(int a[])
    {
        int temp = 0;
        for (int i = 0; i < a.length; i++)
        {
            for (int j = 0; j < (a.length - i - 1); j++)
            {
                if (a[j + 1] < a[j])
                {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }

    static void select(int a[])
    {
        int temp = 0;
        int minIndex = 0;

        for (int i = 0; i < a.length; i++)
        {
            // 每次都假设i所在位置的元素是最小的
            minIndex = i;
            for (int j = i + 1; j < a.length; j++)
            {
                // 假设失败,那么最小元素就是i的下一个元素,也就是j
                if (a[minIndex] > a[j])
                {
                    minIndex = j;
                }
            }
            // 把当前最小元素和前面第i个元素交换：
            if (minIndex != i)
            {
                temp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = temp;
            }
        }
    }
    
    private static void swap(int a[])
    {
        int len = a.length;
        int temp =0;
        for (int i =0; i<len/2; i++)
        {
            temp = a[i];
            a[i] = a[len-i-1];
            a[len-i-1] = temp;
        }
    }

    private static void print(int a[])
    {
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}