Java如何實作簡單的排序

排序是資料處理中十分常見且核心的操作，雖然說實際專案開發中很小幾率會需要我們手動實現，畢竟每種語言的類別庫中都有n多種關於排序演算法的實作。但了解這些精妙的想法對我們還是大有裨益的。本文簡單溫習下最基礎的三類演算法：選擇，冒泡，插入。

先定義個交換數組元素的函數，供排序時調用

/**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }

簡單選擇排序

簡單選擇排序是最簡單直觀的一種演算法，基本思想為每趟從待排序的資料元素中選擇最小（或最大）的一個元素作為首元素，直到所有元素排完為止，簡單選擇排序是不穩定排序。

在演算法實現時，每一趟確定最小元素的時候會透過不斷地比較交換來使得首位置為當前最小，交換是個比較耗時的操作。其實我們很容易發現，在還未完全確定目前最小元素之前，這些交換都是無意義的。我們可以透過設定一個變數min，每一次比較僅儲存較小元素的陣列下標，當輪循環結束之後，那麼這個變數儲存的就是目前最小元素的下標，此時再執行交換操作即可。程式碼實作很簡單，一起來看下。

程式碼實作

/**
     * 简单选择排序
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;//每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //进行交换，如果min发生变化，则进行交换
            if (min != i) {
                swap(arr,min,i);
            }
        }
    }

簡單選擇排序經過上面優化之後，無論數組原始排列如何，比較次數是不變的；對於交換操作，在最好情況下也就是數組完全有序的時候，無需任何交換移動，在最差情況下，也就是數組倒序的時候，交換次數為n-1次。綜合下來，時間複雜度為O(n2)

冒泡排序

冒泡排序的基本思想是，對相鄰的元素進行兩兩比較，順序相反則進行交換，這樣，每一趟會將最小或最大的元素「浮」到頂端，最終達到完全有序

#程式碼實作

在冒泡排序的過程中，如果某一趟執行完畢，沒有做任何一次交換操作，例如數組[5,4,1,2,3]，執行了兩次冒泡，也就是兩次外循環之後，分別將5和4調整到最終位置[1,2,3,4,5]。此時，再執行第三次循環後，一次交換都沒有做，這就說明剩下的序列已經是有序的，排序操作也就可以完成了，來看下代碼

/**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;//设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已然完成。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

根據上面這種冒泡實現，若原數組本身就是有序的（這是最好情況），僅需n-1次比較就可完成；若是倒序，比較次數為n-1 n-2 ... 1= n(n-1)/2，交換次數和比較次數等值。所以，其時間複雜度依然為O(n2）。綜合來看，冒泡排序效能還是稍差於上面那種選擇排序的。

直接插入排序

直接插入排序基本思想是每一步將一個待排序的記錄，插入到前面已經排好序的有序序列中去，直到插完所有元素為止。

程式碼實作

/**
     * 插入排序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr,j,j-1);
                j--;
            }
        }
    }

簡單插入排序在最好情況下，需要比較n-1次，無需交換元素，時間複雜度為O( n);在最壞情況下，時間複雜度依然為O(n2)。但是在數組元素隨機排列的情況下，插入排序還是要優於上面兩種排序的。

以上是Java如何實作簡單的排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！