Java資料結構之選擇排序演演算法的實現與優化

2023-01-22 14:00:20

初識選擇排序

演演算法思想[以升序為例]：

第一趟選擇排序時，從第一個記錄開始，通過n-1次關鍵字的比較，從第n個記錄中選出關鍵字最小的記錄，並和第一個記錄進行交換

第二趟選擇排序時，從第二個記錄開始，通過n-2次關鍵字的比較，從第n-1個記錄中選出關鍵字最小的記錄，並和第二個記錄進行交換

…

第i趟選擇排序時，從第i個記錄開始，通過n-i次關鍵字的比較，從n-i+1個記錄中選擇出關鍵字最小的記錄，並和第i個記錄進行交換

反覆進行上述步驟，經過n-1趟選擇排序，將把n-1個記錄排到位，最後剩下的那個元素同樣已經就位，所以共需進行n-1趟選擇排序

文字描述[以升序為例]

將陣列分為兩個子集，排序的和未排序的，每一輪從未排序的子集中選出最小的元素，放入排序子集，重複上述步驟，直至整個陣列有序

演演算法實現

程式碼如下：

package bin_find;
import java.util.Arrays;

public class selectionSort {
    public static void main(String[] args) {
        int[] a={5,3,7,2,1,9,8,4};
        selection(a);
    }

    private static void selection(int[] a){
        for(int i=0;i<a.length-1;i++) {//n個元素參與排序，需要進行n-1次
            for (int j = i + 1; j < a.length; j++) {//每輪i+1---a.length個元素之間相比較
                if (a[i] > a[j]) {//前者大於後者，則進行交換
                    swap(a, i, j);
                }
            }
            System.out.println("第"+(i+1)+"輪選擇排序的結果"+Arrays.toString(a));
        }
    }
    public static void swap(int arr[],int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }
}

輸出如下：

第1輪選擇排序的結果[1, 5, 7, 3, 2, 9, 8, 4]
第2輪選擇排序的結果[1, 2, 7, 5, 3, 9, 8, 4]
第3輪選擇排序的結果[1, 2, 3, 7, 5, 9, 8, 4]
第4輪選擇排序的結果[1, 2, 3, 4, 7, 9, 8, 5]
第5輪選擇排序的結果[1, 2, 3, 4, 5, 9, 8, 7]
第6輪選擇排序的結果[1, 2, 3, 4, 5, 7, 9, 8]
第7輪選擇排序的結果[1, 2, 3, 4, 5, 7, 8, 9]

優化後的演演算法實現

優化思路

減少交換次數，每一輪可以先找到最小的索引，再每輪最後再交換元素

程式碼如下：

package bin_find;
import java.util.Arrays;

public class selectionSort {
    public static void main(String[] args) {
        int[] a={5,3,7,2,1,9,8,4};
        selection(a);
    }

    private static void selection(int[] a){
        //代表每輪選擇最小元素要交換到的目標索引
        for(int i=0;i<a.length-1;i++) {

            int s = i;//代表最小元素的索引[這裡是升序]---第一次最小元素的索引為1，第二次最小元素的索引為2.....

            //從當前最小元素的下一位元素開始直到最後一個元素---完成一次選擇排序
            for (int j = s + 1; j < a.length; j++) {
                //[這裡是升序]，前者大於後者，則將更小數的索引值賦值給s,因為變數s本身代表的含義為最小元素的索引
                if (a[s] > a[j]) {
                    s = j;
                }
            }
            if (s != i) {//若不是同一個數，則進行交換
                swap(a, s, i);
            }
            System.out.println("第"+(i+1)+"輪選擇排序的結果"+Arrays.toString(a));
        }
    }
    public static void swap(int arr[],int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }
}

輸出：

第1輪選擇排序的結果[1, 3, 7, 2, 5, 9, 8, 4]
第2輪選擇排序的結果[1, 2, 7, 3, 5, 9, 8, 4]
第3輪選擇排序的結果[1, 2, 3, 7, 5, 9, 8, 4]
第4輪選擇排序的結果[1, 2, 3, 4, 5, 9, 8, 7]
第5輪選擇排序的結果[1, 2, 3, 4, 5, 9, 8, 7]
第6輪選擇排序的結果[1, 2, 3, 4, 5, 7, 8, 9]
第7輪選擇排序的結果[1, 2, 3, 4, 5, 7, 8, 9]

未進行優化的演演算法輸出：