Java數(shù)據(jù)結(jié)構(gòu)之選擇排序算法的實現(xiàn)與優(yōu)化

更新時間：2023年01月21日 09:55:14 作者：從未止步..

選擇排序：（Selection?sort）是一種簡單直觀的排序算法，也是一種不穩(wěn)定的排序方法。本文主要為大家介紹一下選擇排序的實現(xiàn)與優(yōu)化，希望對大家有所幫助

初識選擇排序

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

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

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

…

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

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

文字描述[以升序為例]

將數(shù)組分為兩個子集，排序的和未排序的，每一輪從未排序的子集中選出最小的元素，放入排序子集，重復上述步驟，直至整個數(shù)組有序

算法實現(xiàn)

代碼如下：

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)+"輪選擇排序的結(jié)果"+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輪選擇排序的結(jié)果[1, 5, 7, 3, 2, 9, 8, 4]
第2輪選擇排序的結(jié)果[1, 2, 7, 5, 3, 9, 8, 4]
第3輪選擇排序的結(jié)果[1, 2, 3, 7, 5, 9, 8, 4]
第4輪選擇排序的結(jié)果[1, 2, 3, 4, 7, 9, 8, 5]
第5輪選擇排序的結(jié)果[1, 2, 3, 4, 5, 9, 8, 7]
第6輪選擇排序的結(jié)果[1, 2, 3, 4, 5, 7, 9, 8]
第7輪選擇排序的結(jié)果[1, 2, 3, 4, 5, 7, 8, 9]

優(yōu)化后的算法實現(xiàn)

優(yōu)化思路

減少交換次數(shù)，每一輪可以先找到最小的索引，再每輪最后再交換元素

代碼如下：

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++) {
                //[這里是升序]，前者大于后者，則將更小數(shù)的索引值賦值給s,因為變量s本身代表的含義為最小元素的索引
                if (a[s] > a[j]) {
                    s = j;
                }
            }
            if (s != i) {//若不是同一個數(shù)，則進行交換
                swap(a, s, i);
            }
            System.out.println("第"+(i+1)+"輪選擇排序的結(jié)果"+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輪選擇排序的結(jié)果[1, 3, 7, 2, 5, 9, 8, 4]
第2輪選擇排序的結(jié)果[1, 2, 7, 3, 5, 9, 8, 4]
第3輪選擇排序的結(jié)果[1, 2, 3, 7, 5, 9, 8, 4]
第4輪選擇排序的結(jié)果[1, 2, 3, 4, 5, 9, 8, 7]
第5輪選擇排序的結(jié)果[1, 2, 3, 4, 5, 9, 8, 7]
第6輪選擇排序的結(jié)果[1, 2, 3, 4, 5, 7, 8, 9]
第7輪選擇排序的結(jié)果[1, 2, 3, 4, 5, 7, 8, 9]

未進行優(yōu)化的算法輸出：