Java 快速排序法

1.快速排序的原理：

選擇一個關鍵值作為基準值。比基準值小的都在左邊序列（一般是無序的），比基準值大的都在右邊（一般是無序的）。

從後往前比較，用基準值和最後一個值比較，如果比基準值小的交換位置，如果沒有繼續比較下一個，直到找到第一個比基準值小的值才交換。找到這個值之後，又從前往後開始比較，如果有比基準值大的，交換位置，如果沒有繼續比較下一個，直到找到第一個比基準值大的值才交換。直到從前往後的比較索引>從後往前比較的索引，結束第一次迴圈，此時，對於基準值來說，左右兩邊就是有序的了。

接著分別比較左右兩邊的序列，重覆上述的迴圈。

代碼實例：

public class FastSort {

    public static void main(String[] args) {
        System.out.println("快速排序法測試");
        int[] a = { 121,  16,12,222,3333,212, 15, 1, 30,23, 9,33,56,66,543,65,665 };
        int start = 0;
        int end = a.length - 1;
        sort(a, start, end);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }

    public static void sort(int[] a, int low, int high) {
        int start = low;
        int end = high;
        int key = a[low];

        while (end > start) {
            // 從後往前比較
            while (end > start && a[end] >= key)
                // 如果沒有比關鍵值小的，比較下一個，直到有比關鍵值小的交換位置
                //然後又從前往後比較
                end--;
            if (a[end] <= key) {
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            // 從前往後比較
            while (end > start && a[start] <= key)
                // 如果沒有比關鍵值大的，比較下一個，直到有比關鍵值大的交換位置
                start++;
            if (a[start] >= key) {
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
           // 此時第一次迴圈比較結束，關鍵值的位置已經確定了。
           // 左邊的值都比關鍵值小，右邊的值都比關鍵值大
           // 但是兩邊的順序還有可能是不一樣的，進行下麵的遞歸調用
        }
        // 遞歸
        if (start > low)
            sort(a, low, start - 1);// 左邊序列。第一個索引位置到關鍵值索引-1
        if (end < high)
            sort(a, end + 1, high);// 右邊序列。從關鍵值索引+1到最後一個
    }

}

2.冒泡排序法

//冒泡排序
class MaoPao {

    public void sort(int[] arr) {
        int temp = 0;
        // 外層迴圈，它決定一共走幾趟
        for (int i = 0; i < arr.length - 1; i++) {
            // 內層迴圈開始逐個比較，如果發現前一個比後一個大則交換
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

3.選擇排序法

//選擇排序
class Select {
    public void sort(int arr[]) {
        // 我認為第一個數就是最小
        int temp = 0;
        for (int j = 0; j < arr.length - 1; j++) {
            int min = arr[j];
            // 記錄最小數的下標
            int minIndex = j;
            for (int k = j + 1; k < arr.length; k++) {
                if (min > arr[k]) {
                    // 修改最小
                    min = arr[k];
                    minIndex = k;
                }
            }
            // 當退出for就找到這次最小
            temp = arr[j];
            arr[j] = arr[minIndex];
            arr[minIndex] = temp;
            ;

        }
    }
}

4.插入排序法

//插入排序
class InsertSort {
    
    public void sort(int arr[]) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            // insertVal準備和前一個數進行比較
            int index = i - 1;
            while (index >= 0 && insertVal < arr[index]) {
                // 把arr[index]向後移動
                arr[index + 1] = arr[index];
                // 讓index向前移動
                index--;
            }
            // 將inserVal插入到適當位置
            arr[index + 1] = insertVal;

        }
    }
}

測試類：

public class PaiXu {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] t = { 33, 32, 12, 122, 1132, -22, 1237, 89, 222, 44, 55, 22, 24,
                9776, -54, 0, 4432, 753, 56, 3, 37, 67 };
        
        //驗證冒泡
        // MaoPao mao = new MaoPao();
        // mao.sort(t);

        //驗證選擇
        // Select s=new Select();
        // s.sort(t);
 
        //驗證插入
        InsertSort ins = new InsertSort();
        ins.sort(t);

        // 輸出結果
        for (int i = 0; i < t.length; i++) {
            System.out.print(t[i] + " ");
        }
    }

}