97在线观看免费视频,av色女日

選擇排序算法維護(hù)一個待排序集合和一個已排序集合，每輪迭代，從待排序集合中選擇一個最?。ㄗ畲螅┰?，添加到已排序集合中，通過多次迭代，最終完成排序。

選擇排序與上一章的冒泡排序很相似，兩者都維護(hù)了待排序集合和已排序集合，每次迭代結(jié)束都會產(chǎn)生一個已排序元素。不同之處在于冒泡排序的極值元素是通過不斷的比較和交換位置產(chǎn)生的，選擇排序則是不斷比較和一次交換位置產(chǎn)生，所以相對冒泡排序，性能上具有優(yōu)勢。

算法過程

以遞增排序為例，初始集合即為待排序集合，已排序集合初始為空

聲明變量 $index$ 并指定初始值為待排序集合第一個元素的下標(biāo)，通過遍歷待排序集合，比較并更新 $index$ ，若 $index$ 指向不為待排序集合最后一個元素，則交換 $index$ 指向的值和待排序集合最后一個元素；
標(biāo)記待排序集合最后一個元素為已排序；
重復(fù)步驟 1,2，直到待排序集合只有一個元素

演示示例

初始狀態(tài)：0 次排序
待排序集合：[6,3,4,0,2,1,8,5,9,7]
已排序集合：[]

初始狀態(tài)為：

根據(jù)算法過程：

步驟一， $index$ 初始值設(shè)為 0，指向元素 6，從下標(biāo)為 1 的元素開始，比較 $index$ 指向的值和 3，比較大小后，選擇下一個元素，比較 $index$ 指向的值和 4，比較大小，直到選擇 8，比較大小并更新 $index$ 值為 6，即元素 8 的下標(biāo)，依次遍歷比較待排序集合后，若 $index$ 值不為待排序集合的尾元素下標(biāo)，則交換 $index$ 指向的值和待排序集合的尾元素；
步驟二，標(biāo)記待排序集合中的最后一個元素為已排序，從待排序集合中移除該元素

1 次排序后
待排序集合：[6, 3, 4, 0, 2, 1, 8, 5, 7]
已排序集合：[9]

根據(jù)算法過程步驟三，待排序集合中不止一個元素，所以重復(fù)執(zhí)行步驟一、二：

步驟一， $index$ 初始值設(shè)為 0，指向元素 6，從下標(biāo)為 1 的元素開始，比較 $index$ 指向的值和 3，比較大小后，選擇下一個元素，比較 $index$ 指向的值和 4，比較大小，直到選擇 8，比較大小并更新 $index$ 值為 6，即元素 8 的下標(biāo)，依次遍歷比較待排序集合后，若 $index$ 值不為待排序集合的尾元素下標(biāo)，則交換 $index$ 指向的值和待排序集合的尾元素；
步驟二，標(biāo)記待排序集合中的最后一個元素為已排序，從待排序集合中移除該元素

2 次排序后
待排序集合：[6, 3, 4, 0, 2, 1, 7, 5]
已排序集合：[8, 9]

...
...
...

9 次排序后
待排序集合：[0]
已排序集合：[1, 2, 3, 4, 5, 6, 7, 8, 9]

觀察以上過程可知，每次排序后會有一個元素變?yōu)橐雅判?，即有一個元素處于正確的位置上。所以 $N$ 個元素的序列，經(jīng)過 $N-1$ 次排序后，則有 $N?1$ 個元素處于已排序狀態(tài)，則剩下的一個元素不再需要進(jìn)行排序。

算法示例

def selectionSort(arr):
    for i in range(1, len(arr)):  # 迭代次數(shù)
        index = 0
        for j in range(1, len(arr) - i + 1):  # 遍歷比較待排序集合中的元素
            if arr[index] < arr[j]:
                index = j
        if not index == j:
            arr[index],arr[j] = arr[j],arr[index]

代碼分析：

以上代碼中，第一層循環(huán)為需要進(jìn)行的迭代次數(shù)，元素個數(shù)為 $N$ 的集合，最多需要 $N-1$ 次迭代即可確定 $N-1$ 個元素的位置，即完成排序；
第二層循環(huán)為比較元素值更新 $index$ 指向位置的操作，隨著迭代次數(shù)的增加，待排序元素個數(shù)減少；
每一次循環(huán)后，判斷 $index$ 指向的是否為待排序集合最后一個元素，若不是則交換元素值。

算法分析

在每一輪排序過程中，選擇出極值后，是通過直接交換元素位置的方式生成已排序元素的，所以選擇排序是一種非穩(wěn)定排序。對于 $N$ 個元素的序列，需要進(jìn)行 $N-1$ 次迭代才能完成排序，每一次都需要遍歷比較待排序集中所有元素來確定極值位置，即第 $i$ 次迭代，遍歷的元素個數(shù)為 $N-i$ 。所以算法的比較復(fù)雜度為 $O(n^2)$ ，交換復(fù)雜度為 $O(n)$ 。