首頁 > 軟體

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]

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

進行優化的演演算法輸出:

通過比較二者的輸出結果,我們能夠很明顯的感覺到,經過優化後的演演算法在實現的過程中,資料之間的交換次數明顯減少

選擇排序 VS 氣泡排序

1:二者的平均複雜度都是O(n^2),但是當有序陣列使用氣泡排序時,其時間複雜度為O(n)

2:選擇排序一般要快於氣泡排序,因為其交換的次數少

3:但如果集合有序度高,那麼氣泡排序優先於選擇排序

例:在上篇文章的氣泡排序優化演演算法中,我們通過設定變數,去判斷當前的陣列元素是否發生交換,如果未發生交換,則證明當前陣列已經有序,不再進行排序

4:氣泡排序屬於穩定排序演演算法,而選擇屬於不穩定排序

穩定 VS 不穩定:即為兩個大小相等的數,在參與排序之前具有先後關係,若排序完成,這兩個數的先後順序並未發生改變,那麼即為穩定排序,否則為不穩定排序

舉例:

(3,3,2)

對於上述陣列:

參與氣泡排序:

第一輪:3和3相等,無需交換位置,3和2交換位置

第二輪:3和2交換位置

排序結束,排序後的結果為(2,3,3)

參與選擇排序:

第一輪:將3取出,與3比較,3不滿足大於3,再與2進行比較,滿足大於2,交換位置

第二輪:將3取出,與3進行比較,不滿足大於3

排序結束,排序成功,排序後的結果為(2,3,3)

通過兩種方法的排序結果,我們不難看出通過氣泡排序演演算法,兩個大小相等的數的先後關係並沒有發生改變,即為穩定的排序,而通過選擇排序演演算法,兩個大小相等的數的先後關係發生了改變,即為不穩定的排序

到此這篇關於Java資料結構之選擇排序演演算法的實現與優化的文章就介紹到這了,更多相關Java選擇排序演演算法內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com