排序 - 天天看點

冒泡排序：

package cn.edu.hdu.chenpi.plib;

import java.util.Arrays;

public class App {

    public static void main(String[] args) {
        Integer[] arr = { 49, 38, 65, 97, 76, 13, 27, 49 };

        for (int i = 0; i < arr.length - 1; i++) {
            //用于提前結束判斷
            boolean changeFlag = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    changeFlag = true;
                }
            }
            if (changeFlag == false)
                break;
            System.out.println("第" + (i + 1) + "次:" + Arrays.asList(arr));
        }
        System.out.println(Arrays.asList(arr));
        ;
    }
}

快速排序：

package cn.edu.hdu.chenpi.plib;

public class App {

    public static void main(String[] args) {
        int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49 };
        App.quickSort(arr, 0, arr.length - 1);
        for (int t : arr) {
            System.out.println(t);
        }
    }

    public static int trip(int[] arr, int begin, int end) {
        int c = arr[begin];
        int i = begin, j = end;
        //最後一個空位
        int index = 0;
        while (i < j) {
            //從後往前找
            while (i < j && arr[j] >= c) {
                j--;
            }
            arr[i] = arr[j];
            index = j;
            i++;

            if (i >= j) break;
            
            //從前往後找
            while (i < j && arr[i] <= c) {
                i++;
            }
            arr[j] = arr[i];
            index = i;
            j--;

        }

        arr[index] = c;

        //列印一趟排序後的結果
        for (int t : arr) {
            System.out.print(t + " ");
        }
        System.out.println(index);
        return index;
    }

    public static void quickSort(int[] arr, int begin, int end) {
        if (begin < end) {
            int middle = App.trip(arr, begin, end);

            App.quickSort(arr, begin, middle - 1);
            App.quickSort(arr, middle + 1, end);
        }
    }
}

選擇排序：在要排序的一組數中，選出最小的一個數與第一個位置的數交換；然後在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最後一個數比較為止。

插入排序：已排序+未排序兩部分，從已排序後面找一個值，插入到已排序，依次下去。。。

希爾排序：

歸并排序：歸并（Merge）排序法是将兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若幹個子序列，每個子序列是有序的。然後再把有序子序列合并為整體有序序列。

堆排序：

　　n個元素的序列{k1，k2，…,kn}當且僅當滿足下列關系之一時，稱之為堆。

　　情形1：ki <= k2i 且ki <= k2i+1 （最小化堆或小頂堆）

　　情形2：ki >= k2i 且ki >= k2i+1 （最大化堆或大頂堆）

若在輸出堆頂的最小值之後，使得剩餘n-1個元素的序列重又建成一個堆，則得到n個元素的次小值。如此反複執行，便能得到一個有序序列，這個過程稱之為堆排序。

@Author 風一樣的碼農

@HomePageUrl http://www.cnblogs.com/chenpi/