排序算法篇_選擇排序法

image

??選擇排序（Selection Sort）也是比較簡單的排序算法型型，思路也比較直觀。選擇排序算法在每一步中選取最小值來重新排列，從而達到排序的目的厕妖。

選擇排序算法

選擇排序算法通過選擇和交換來實現(xiàn)排序第美，其排序流程如下：

首先從原始數(shù)組中選擇最小的一個數(shù)據(jù)蝶锋，將其和位于第一個位置的數(shù)據(jù)進行交換。
接著從剩下的 n-1 個數(shù)據(jù)中選擇次小的一個元素什往，將其和第二個位置的數(shù)據(jù)交換扳缕。
然后，這樣不斷重復，直到最后連個數(shù)據(jù)完成交換躯舔。至此驴剔，便完成對原始數(shù)組的從小到大的排序。

??為了更清晰地理解選擇排序的算法執(zhí)行過程粥庄，這里我們舉一個實際數(shù)據(jù)的例子來一步步的執(zhí)行選擇排序算法丧失。對于5個整型數(shù)據(jù) 118、101惜互、105布讹、127、112训堆，這是一組無序的數(shù)據(jù)描验。對其執(zhí)行的選擇排序過程，如下圖所示蔫慧，選擇排序算法的執(zhí)行步驟如下：

05.png

第一次排序挠乳，從原始數(shù)組中選擇最小的數(shù)據(jù)，這個數(shù)據(jù)便是101姑躲，將其與第一個數(shù)據(jù)118進行交換睡扬。此時排序后的數(shù)據(jù)為 101、118黍析、105卖怜、127、112阐枣。
第二次排序马靠，從剩余的數(shù)組中選擇最小的數(shù)據(jù)，這個數(shù)據(jù)是105蔼两，將其與第二個數(shù)據(jù)118進行交換甩鳄。此時排序后的數(shù)據(jù)為101、105额划、118妙啃、127、112俊戳。
第三次排序揖赴，將剩余的數(shù)據(jù)中選擇最小的數(shù)據(jù)，這個數(shù)據(jù)是112抑胎，將其與第三個數(shù)據(jù)118進行交換燥滑。此時排序后的數(shù)據(jù)為101、105阿逃、112铭拧、127赃蛛、118。
第四次排序搀菩，將剩余的數(shù)組中選擇最小的數(shù)據(jù)焊虏，這個數(shù)據(jù)為118，將其與第四次數(shù)據(jù)127進行交換秕磷。此時排序后的數(shù)據(jù)為101诵闭、105、112澎嚣、118疏尿、127。

??從上面的例子易桃，可以非常直觀的了解到選擇排序算法的執(zhí)行過程褥琐。選擇排序算法在對N個數(shù)據(jù)進行排序時，無論原始數(shù)據(jù)有無順序晤郑，都需要進行 N-1 步的中間排序敌呈。這種排序方法思路很簡單直觀，但是缺點就是執(zhí)行的步驟有點長造寝，效率也不是很高磕洪。


void selectSort(int[] datas) {
        int index;
        int temp;
        for (int i = 0; i < datas.length; i++) {
            index = i;

            for (int j = i + 1; j < datas.length; j++) {
                if (datas[j] > datas[index]) {
                    index = j;
                }
            }
            // 交換兩個數(shù)
            if (index != i) {
                temp = datas[i];
                datas[i] = datas[index];
                datas[index] = temp;
            }

            System.out.print("第" + i + "步排序結果：");
            for (int k = 0; k < datas.length; k++) {
                System.out.print(" " + datas[k]);
            }
            System.out.print("\n");
        }
    }

??在這里，輸入?yún)?shù)datas一般為一個數(shù)組的首地址诫龙。待排序的原數(shù)據(jù)便保存在數(shù)組datas中析显，程序中通過兩層循環(huán)來對數(shù)據(jù)進行選擇排序。為了更清楚的看到算法執(zhí)行過程签赃，在排序的每一步輸出了當前排序結果谷异。

選擇排序算法實例

??有了前面的選擇排序算法的基本思想和算法之后。這里通過一個完整的例子來說明選擇排序法在整型數(shù)組排序中的應用锦聊，程序示例如下：


public class SelectionSort {

    static final int SIZE = 10;

    public static void selectSort(int[] datas) {
        int index, temp;
        for (int i = 0; i < datas.length; i++) {
            index = i;

            for (int j = i + 1; j < datas.length; j++) {
                if (datas[j] < datas[index]) {
                    index = j;
                }
            }
            // 交換兩個數(shù)
            if (index != i) {
                temp = datas[i];
                datas[i] = datas[index];
                datas[index] = temp;
            }

            System.out.print("第" + i + "步排序結果：");
            for (int k = 0; k < datas.length; k++) {
                System.out.print(" " + datas[k]);
            }
            System.out.print("\n");
        }
    }

    public static void main(String[] args) {
        int[] datas = new int[SIZE];
        int i;
        for (i = 0; i < SIZE; i++) {
            datas[i] = (int) (100 + Math.random() * (100 + 1));
        }
        System.out.print("排序前的數(shù)組為：\n");
        for (i = 0; i < SIZE; i++) {
            System.out.print(datas[i] + " ");
        }
        System.out.print("\n");
        selectSort(datas);
        System.out.print("排序后的數(shù)組為：\n");
        for (i = 0; i < SIZE; i++) {
            System.out.print(datas[i] + " ");
        }
    }
}

??在這里歹嘹，程序定義符號常亮SIZE，用于表示需要排序的整型數(shù)組的大小孔庭。在主方法中尺上，首先定義一個整型數(shù)組，對數(shù)組進行隨機初始化史飞，并輸出數(shù)組內(nèi)容尖昏。接著調用選擇排序算法的方法對數(shù)組排序仰税。最后构资，輸出排序后的數(shù)組。

??該程序執(zhí)行的結果如下陨簇。

04.png