文章目錄

• Java基礎算法(1)——選擇排序
• • • 1.建立排序基類
    • 2.正題:選擇排序思路簡介
    • 3.完整代碼實作與詳細注釋
    • 4.運作效果

Java基礎算法(1)——選擇排序

1.建立排序基類

為了友善以後專心寫排序的邏輯，于是将一些經常重複使用的方法抽離出來，此處參考《算法》第四版一書。

方法簡介：

• sort(Comparable[] a) 排序傳入的數組
• less(Comparable v,Comparable w) 比較v,w的值，若v<w 傳回boolean類型
• exch(Comparable[] a,int i,int j) 交換數組a中下标為i，j兩者的值
• show(Comparable[] a) 控制台輸出此數組
• isSorted(Comparable[] a) 判斷數組是否已經排序完成 傳回boolean類型

package Algorithm.Sort;

/**
 * 排序算法類的模闆2
 * 為了友善測試，具體排序類繼承此類即可
 *
 * 方法簡介：
 * sort(Comparable[] a) 排序傳入的數組
 * less(Comparable v,Comparable w) 比較v,w的值，若v<w 傳回boolean類型
 * exch(Comparable[] a,int i,int j) 交換數組a中下标為i，j兩者的值
 * show(Comparable[] a) 控制台輸出此數組
 * isSorted(Comparable[] a) 判斷數組是否已經排序完成 傳回boolean類型
 */
public class Template {

    public static void sort(Comparable[] a){

    }

    /**
     * 比較v,w的值，若v<=w 傳回true，否則傳回false
     * @param v
     * @param w
     * @return
     */
    public static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<=0;
    }

    /**
     * 交換數組a中下标為i，j兩者的值
     * @param a
     * @param i
     * @param j
     */
    public static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

    /**
     * 輸出此數組
     * @param a
     */
    public static void show(Comparable[] a){
        //單行列印數組
        for (int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();//換行
    }

    /**
     * 判斷數組是否已經排序完成
     * @param a
     * @return
     */
    public static boolean isSorted(Comparable[] a){
        //用于測試數組是否排序
        for (int i=1;i<a.length;i++){
            if(less(a[i],a[i-1])){
                return false;
            }
        }
        return true;
    }
}

           

2.正題:選擇排序思路簡介

選擇剩餘元素之中的最小值，并與目前剩餘元素的首元素交換位置

例如：3 8 4 1 2

第一次1和3交換——>1 8 4 3 2

第二次2和8交換——>1 2 4 3 8

第三次3和4交換——>1 2 3 4 8

… ——>1 2 3 4 8

… ——>1 2 3 4 8

第四次第五次應為都是剩餘元素裡面本身是最小，便和自己交換

更多實作細節在代碼中有詳細的注釋！

3.完整代碼實作與詳細注釋

package Algorithm.Sort;
/**
 * 排序(1)
 * 選擇排序
 * 找到數組中最小的元素，與第一個元素交換元素
 * 剩下的元素中再找最小的元素，與第二個交換位置，以此類推
 * （不斷選擇剩餘元素中的最小值）
 * 假設數組元素數量為：N
 * 交換總次數固定為N
 * 是以時間效率取決于元素之間比較次數
 */
public class SelectionSort extends Template {

    //升序
    public static void sort(Comparable[] a) {
        int N = a.length;
        System.out.println("排序過程:");
        for (int i = 0; i < N; i++) {
            //min為目前這次周遊中應該交換的下标（本次周遊最小元素的下标，預設為本次周遊的首元素下标）
            int min = i;
            //從目前預設最小值的下标的下一下标開始比較大小，後者小則更換min下标值
            for (int j = i + 1; j < N; j++) {
                if (less(a[j], a[min]))
                    min = j;
            }
            //本次周遊比較完所有元素後，交換下标為i和下标為min的值，使得min每次都位于剩餘元素首部
            exch(a, i, min);
            //輸出每次周遊的結果，檢視排序過程
            show(a);
        }
    }

    public static void main(String[] args) {
        String[] a = {"c", "s", "d", "n", "x", "i", "n", "g", "w", "e", "i"};
        
        System.out.println("選擇排序前");
        show(a);

        //執行選擇排序邏輯
        sort(a);

        assert isSorted(a);
        
        System.out.println("選擇排序後");
        show(a);
    }

}

           

4.運作效果