1、基本思想

冒泡排序中有一個(gè)缺點(diǎn)，比如，我們比較第一個(gè)數(shù)a1與第二個(gè)數(shù)a2的時(shí)候，只要a1比a2大就會(huì)交換位置，但是我們并不能確定a2是最小的元素，假如后面還有比它更小的，該元素還會(huì)與a2再次進(jìn)行交換，而且這種交換有可能發(fā)生多次才能確定a2的最終位置。

選擇排序可以避免這種耗費(fèi)時(shí)間的交換操作，從第一個(gè)元素開(kāi)始，掃描整個(gè)待排數(shù)組，找到最小的元素放之后再與第一個(gè)元素交換位置，然后再?gòu)牡诙€(gè)元素開(kāi)始，繼續(xù)尋找最小的元素與第二個(gè)元素交換位置，依次類(lèi)推。

1.png

2、實(shí)例

    public void selectionSort() {
        int minPoint; // 存儲(chǔ)最小元素的小標(biāo)
        int len = array.length;
        int temp;
        int counter = 1;

        for (int i = 0; i < len - 1; i++) {

            minPoint = i;
            for (int j = i + 1; j <= len - 1; j++) { // 每完成一輪排序，就確定了一個(gè)相對(duì)最小元素，下一輪排序只對(duì)后面的元素排序
                if (array[j] < array[minPoint]) { // 如果待排數(shù)組中的某個(gè)元素比當(dāng)前元素小，minPoint指向該元素的下標(biāo)
                    minPoint = j;
                }
            }

            if (minPoint != i) { // 如果發(fā)現(xiàn)了更小的元素，交換位置
                temp = array[i];
                array[i] = array[minPoint];
                array[minPoint] = temp;
            }

            System.out.print("第" + counter + "輪排序結(jié)果：");
            display();
            counter++;
        }
    }

3、算法分析

選擇排序與冒泡排序一樣，需要進(jìn)行N*(N-1)/2次比較，但是只需要N次交換，當(dāng)N很大時(shí)，交換次數(shù)的時(shí)間影響力更大，所以選擇排序的時(shí)間復(fù)雜度為O(N2)。

雖然選擇排序與冒泡排序在時(shí)間復(fù)雜度屬于同一量級(jí)，但是毫無(wú)疑問(wèn)選擇排序的效率更高，因?yàn)樗慕粨Q操作次數(shù)更少，而且在交換操作比比較操作的時(shí)間級(jí)大得多時(shí)，選擇排序的速度是相當(dāng)快的。

4、選擇排序的改進(jìn)

傳統(tǒng)的選擇排序每次只確定最小值，根據(jù)改進(jìn)冒泡算法的經(jīng)驗(yàn)，我們可以對(duì)排序算法進(jìn)行如下改進(jìn)：每趟排序確定兩個(gè)最值——最大值與最小值，這樣就可以將排序趟數(shù)縮減一半。

改進(jìn)后的代碼如下：

    public void selectionSort_improvement() {
        int minPoint; // 存儲(chǔ)最小元素的小標(biāo)
        int maxPoint; // 存儲(chǔ)最大元素的小標(biāo)
        int len = array.length;
        int temp;
        int counter = 1;

        for (int i = 0; i < len / 2; i++) {

            minPoint = i;
            maxPoint = i;
            for (int j = i + 1; j <= len - 1 - i; j++) { // 每完成一輪排序，就確定了兩個(gè)最值，下一輪排序時(shí)比較范圍減少兩個(gè)元素
                if (array[j] < array[minPoint]) { // 如果待排數(shù)組中的某個(gè)元素比當(dāng)前元素小，minPoint指向該元素的下標(biāo)
                    minPoint = j;
                    continue;
                } else if (array[j] > array[maxPoint]) { // 如果待排數(shù)組中的某個(gè)元素比當(dāng)前元素大，maxPoint指向該元素的下標(biāo)
                    maxPoint = j;
                }
            }

            if (minPoint != i) { // 如果發(fā)現(xiàn)了更小的元素，與第一個(gè)元素交換位置
                temp = array[i];
                array[i] = array[minPoint];
                array[minPoint] = temp;

                // 原來(lái)的第一個(gè)元素已經(jīng)與下標(biāo)為minPoint的元素交換了位置
                // 如果之前maxPoint指向的是第一個(gè)元素，那么需要將maxPoint重新指向array[minPoint]
                // 因?yàn)楝F(xiàn)在array[minPoint]存放的才是之前第一個(gè)元素中的數(shù)據(jù)
                if (maxPoint == i) {
                    maxPoint = minPoint;
                }

            }

            if (maxPoint != len - 1 - i) { // 如果發(fā)現(xiàn)了更大的元素，與最后一個(gè)元素交換位置
                temp = array[len - 1 - i];
                array[len - 1 - i] = array[maxPoint];
                array[maxPoint] = temp;
            }

            System.out.print("第" + counter + "輪排序結(jié)果：");
            display();
            counter++;
        }
    }