java 排序算法之選擇排序

更新時(shí)間：2021年09月01日 15:47:10 投稿：lan00zi

本文主要講解了java 排序算法之選擇排序，選擇排序是最簡單直觀的一種算法，想要了解相關(guān)知識的朋友快來看一看這篇文章吧

基本介紹

選擇排序（select sorting）也屬于內(nèi)部排序法，是從欲排序的數(shù)據(jù)中，按指定的規(guī)則選出來某個(gè)元素，再依規(guī)定交換位置后達(dá)到排序的目的。

它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

基本思想

選擇排序（select sorting）也是一種簡單直觀的排序方法。

基本思想為：

注：n 是數(shù)組大小

第一次從 arr[0]~arr[n-1] 中選取最小值，與 arr[0] 交換
第二次從 arr[1]~arr[n-1] 中選取最小值，與 arr[1] 交換
第 i 次從 arr[i-1]~arr[n-1] 中選取最小值，與 arr[i-1] 交換
依次類推，總共通過 n - 1 次，得到一個(gè)按排序碼從小到大排列的有序序列

思路分析

動圖：

說明：

1.選擇排序一共有數(shù)組大小 - 1 輪排序

2.每 1 輪排序，又是一個(gè)循環(huán)，循環(huán)的規(guī)則

①先假定當(dāng)前這輪循環(huán)的第一個(gè)數(shù)是最小數(shù)

②然后和后面每個(gè)數(shù)進(jìn)行比較，如果發(fā)現(xiàn)有比當(dāng)前數(shù)更小的數(shù)，則重新確定最小數(shù)，并得到下標(biāo)

③當(dāng)遍歷到數(shù)組的最后時(shí)，就得到本輪最小的數(shù)

④和當(dāng)前循環(huán)的第一個(gè)數(shù)進(jìn)行交換

代碼實(shí)現(xiàn)

要求：假設(shè)有一群牛，顏值分別是 101,34,119,1 ，請使用選中排序從低到高進(jìn)行排序

演變過程

使用逐步推導(dǎo)的方式，進(jìn)行講解排序，容易理解。

推導(dǎo)每一步的演變過程，便于理解。

這是一個(gè)很重要的思想：
一個(gè)算法：先簡單 --> 做復(fù)雜：
就是可以把一個(gè)復(fù)雜的算法，拆分成簡單的問題 -> 逐步解決

    @Test
    public void processDemo() {
        int arr[] = {101, 34, 119, 1};
        System.out.println("原始數(shù)組：" + Arrays.toString(arr));
        processSelectSort(arr);
    }

    public void processSelectSort(int[] arr) {
        // 第 1 輪：
        // 原始數(shù)組：101, 34, 119, 1
        // 排序后：  1, 34, 119, 101
        int min = arr[0]; // 先假定第一個(gè)數(shù)為最小值
        int minIndex = 0;
        for (int j = 0 + 1; j < arr.length; j++) {
            // 挨個(gè)與最小值對比，如果小于，則進(jìn)行交換
            if (min > arr[j]) {
                // 如果后面的值比當(dāng)前的 min 小，則重置min為這個(gè)數(shù)
                min = arr[j];
                minIndex = j;
            }
        }
        // 第 1 輪結(jié)束后，得到了最小值
        // 將這個(gè)最小值與 arr[0] 交換
        arr[minIndex] = arr[0];
        arr[0] = min;
        System.out.println("第 1 輪排序后：" + Arrays.toString(arr));

        // 第 2 輪
        // 當(dāng)前數(shù)組：1, 34, 119, 101
        // 排序后：  1, 34, 119, 101
        min = arr[1];
        minIndex = 1;
        // 第二輪，與第 3 個(gè)數(shù)開始比起
        for (int j = 0 + 2; j < arr.length; j++) {
            // 挨個(gè)與最小值對比，如果小于，則進(jìn)行交換
            if (min > arr[j]) {
                // 如果后面的值比當(dāng)前的 min 小，則重置min為這個(gè)數(shù)
                min = arr[j];
                minIndex = j;
            }
        }
        // 第 2 輪結(jié)束后，得到了最小值
        // 將這個(gè)最小值與 arr[1] 交換
        arr[minIndex] = arr[1];
        arr[1] = min;
        System.out.println("第 2 輪排序后：" + Arrays.toString(arr));

        // 第 3 輪
        // 當(dāng)前數(shù)組：1, 34, 119, 101
        // 排序后：  1, 34, 101, 119
        min = arr[2];
        minIndex = 2;
        // 第二輪，與第 4 個(gè)數(shù)開始比起
        for (int j = 0 + 3; j < arr.length; j++) {
            // 挨個(gè)與最小值對比，如果小于，則進(jìn)行交換
            if (min > arr[j]) {
                // 如果后面的值比當(dāng)前的 min 小，則重置min為這個(gè)數(shù)
                min = arr[j];
                minIndex = j;
            }
        }
        // 第 3 輪結(jié)束后，得到了最小值
        // 將這個(gè)最小值與 arr[2] 交換
        arr[minIndex] = arr[2];
        arr[2] = min;
        System.out.println("第 3 輪排序后：" + Arrays.toString(arr));
    }

測試輸出

原始數(shù)組：[101, 34, 119, 1]
第 1 輪排序后：[1, 34, 119, 101]
第 2 輪排序后：[1, 34, 119, 101]
第 3 輪排序后：[1, 34, 101, 119]

從上述的演變過程來看，發(fā)現(xiàn)了規(guī)律：循環(huán)體都是相同的，只是每一輪排序所假定的最小值的下標(biāo)在遞增。因此可以改寫成如下方式

	  @Test
    public void processDemo2() {
        int arr[] = {101, 34, 119, 1};
        System.out.println("原始數(shù)組：" + Arrays.toString(arr));
        processSelectSort2(arr);
    }

    public void processSelectSort2(int[] arr) {
        // 把之前假定當(dāng)前最小值的地方，使用變量 i 代替了
        // 由于需要 arr.length -1 輪，所以使用外層一個(gè)循環(huán)，就完美的解決了這個(gè)需求
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i]; // 先假定第一個(gè)數(shù)為最小值
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                // 挨個(gè)與最小值對比，如果小于，則進(jìn)行交換
                if (min > arr[j]) {
                    // 如果后面的值比當(dāng)前的 min 小，則重置min為這個(gè)數(shù)
                    min = arr[j];
                    minIndex = j;
                }
            }
            // 第 i 輪結(jié)束后，得到了最小值
            // 將這個(gè)最小值與 arr[i] 交換
            arr[minIndex] = arr[i];
            arr[i] = min;
            System.out.println("第 " + (i + 1) + " 輪排序后：" + Arrays.toString(arr));
        }
    }

測試輸出

原始數(shù)組：[101, 34, 119, 1]
第 1 輪排序后：[1, 34, 119, 101]
第 2 輪排序后：[1, 34, 119, 101]
第 3 輪排序后：[1, 34, 101, 119]

由此可以得到，選擇排序的時(shí)間復(fù)雜度是 o(n²)，因?yàn)槭且粋€(gè)嵌套 for 循環(huán)

結(jié)果是一樣的，但是你會發(fā)現(xiàn)，在第 1 輪和第 2 輪的序列是一樣的，但是代碼中目前也進(jìn)行了交換，可以優(yōu)化掉這一個(gè)點(diǎn)

優(yōu)化

    public void processSelectSort2(int[] arr) {
        // 把之前假定當(dāng)前最小值的地方，使用變量 i 代替了
        // 由于需要 arr.length -1 輪，所以使用外層一個(gè)循環(huán)，就完美的解決了這個(gè)需求
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i]; // 先假定第一個(gè)數(shù)為最小值
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                // 挨個(gè)與最小值對比，如果小于，則進(jìn)行交換
                if (min > arr[j]) {
                    // 如果后面的值比當(dāng)前的 min 小，則重置min為這個(gè)數(shù)
                    min = arr[j];
                    minIndex = j;
                }
            }
            // 第 i 輪結(jié)束后，得到了最小值
            // 將這個(gè)最小值與 arr[i] 交換
            //但如果minIndex沒有改變，也就是最小值未發(fā)生改變，則不需要執(zhí)行后面的交換了
            if (minIndex != i) {
                arr[minIndex] = arr[i];
            	arr[i] = min;
            }
            System.out.println("第 " + (i + 1) + " 輪排序后：" + Arrays.toString(arr));
        }
    }

測試輸出

原始數(shù)組：[101, 34, 119, 1]
第 1 輪排序后：[1, 34, 119, 101]
第 3 輪排序后：[1, 34, 101, 119]

則可以看到，第二輪就跳過了交換這一個(gè)步驟，從而優(yōu)化了這個(gè)算法所要花費(fèi)的時(shí)間。

算法函數(shù)封裝

@Test
public void selectSortTest() {
    int arr[] = {101, 34, 119, 1};
    System.out.println("升序");
    System.out.println("原始數(shù)組：" + Arrays.toString(arr));
    selectSort(arr, true);
    System.out.println("排序后：" + Arrays.toString(arr));
    System.out.println("降序");
    System.out.println("原始數(shù)組：" + Arrays.toString(arr));
    selectSort(arr, false);
    System.out.println("排序后：" + Arrays.toString(arr));
}

/**
 * 選擇排序算法封裝
 *
 * @param arr 要排序的數(shù)組
 * @param asc 升序排列，否則降序
 */
public void selectSort(int[] arr, boolean asc) {

    // 把之前假定當(dāng)前最小值的地方，使用變量 i 代替了
    // 由于需要 arr.length -1 輪，所以使用外層一個(gè)循環(huán)，就完美的解決了這個(gè)需求
    for (int i = 0; i < arr.length - 1; i++) {
        int current = arr[i]; // 先假定第一個(gè)數(shù)為最小值
        int currentIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            // 挨個(gè)與最小值對比，如果小于，則進(jìn)行交換
            if (asc) {
                if (current > arr[j]) {
                    // 如果后面的值比當(dāng)前的 min 小，則重置min為這個(gè)數(shù)
                    current = arr[j];
                    currentIndex = j;
                }
            } else {
                if (current < arr[j]) {
                    // 如果后面的值比當(dāng)前的 min 大，則重置為這個(gè)數(shù)
                    current = arr[j];
                    currentIndex = j;
                }
            }
        }
        // 第 i 輪結(jié)束后，得到了最小/大值
        // 將這個(gè)值與 arr[i] 交換
        //但如果minIndex沒有改變，也就是最小值未發(fā)生改變，則不需要執(zhí)行后面的交換了
        if (currentIndex == i) {
            arr[currentIndex] = arr[i];
        	arr[i] = current;
        }
    }
}

測試輸出

升序
原始數(shù)組：[101, 34, 119, 1]
排序后：[1, 34, 101, 119]
降序
原始數(shù)組：[1, 34, 101, 119]
排序后：[119, 101, 34, 1]

大量數(shù)據(jù)耗時(shí)測試

排序隨機(jī)生成的 8 萬個(gè)數(shù)據(jù)

 @Test
    public void bulkDataSort() {
        int max = 80_000;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = (int) (Math.random() * 80_000);
        }

        Instant startTime = Instant.now();
        selectSort(arr, true);
//        System.out.println(Arrays.toString(arr));
        Instant endTime = Instant.now();
        System.out.println("共耗時(shí)：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }

多次運(yùn)行測試輸出