如何使用python實(shí)現(xiàn)選擇排序

這篇文章主要介紹如何使用python實(shí)現(xiàn)選擇排序，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

def selection_sort(alist):    '''選擇排序'''        last = len(alist)    first = 1        while first < last:        print(first)  # 可以理解為第幾次遍歷        for i in range(first,last):            if alist[i] < alist[first-1]: # 從小到大排列                alist[first-1],alist[i] = alist[i],alist[first-1]        print(alist)   # 每次遍歷完的結(jié)果                first += 1
    return alist

if __name__ == '__main__':    alist = [2,4,7,1,6,5,3]    print(selection_sort(alist))

        代碼流程：首先獲取數(shù)組長(zhǎng)度last，初始遍歷時(shí)，默認(rèn)0索引位置的元素最小，因此令first為1，first代表的意思是第一個(gè)與默認(rèn)最小值進(jìn)行比較的元素的索引（比如在進(jìn)行第一輪遍歷時(shí)，肯定是索引為1的元素與索引為0的元素比較，后面每輪的遍歷類(lèi)似推理即可）；接著進(jìn)入while循環(huán)，這里以開(kāi)始比較的元素的索引與數(shù)組長(zhǎng)度作條件判斷，小于則進(jìn)入遍歷，否則終止循環(huán)（此內(nèi)容下文針對(duì)示例結(jié)果具體講解）；對(duì)于內(nèi)部的for循環(huán)，注意其范圍：后者小于前者交換位置，否則不交換，這里可以看出后者元素的索引減1即為前者元素的索引，還是拿首次遍歷來(lái)說(shuō)，當(dāng)first為1時(shí)，其減1則為0，因此實(shí)現(xiàn)了第一個(gè)元素與默認(rèn)為最小的0位置的元素的比較，到了第二次遍歷時(shí)，first為2，其減1為1，可實(shí)現(xiàn)2位置的與1位置的比較大?。ù藭r(shí)的1為第二次遍歷時(shí)的數(shù)組的首個(gè)元素的索引 ‘0’）。。。。依次類(lèi)推實(shí)現(xiàn)排序，在每次遍歷完后可通過(guò)打印數(shù)組來(lái)查看每次的結(jié)果。first加1，就是由于每遍歷一次，待排序的數(shù)組長(zhǎng)度減1。下面結(jié)合示例結(jié)果說(shuō)說(shuō)：

1   # first值[1, 4, 7, 2, 6, 5, 3]  # 第一次遍歷結(jié)果2   # first值[1, 2, 7, 4, 6, 5, 3]  # 第二次遍歷結(jié)果3   # first值[1, 2, 3, 7, 6, 5, 4]  # 第三次遍歷結(jié)果4   # first值[1, 2, 3, 4, 7, 6, 5]  # 第四次遍歷結(jié)果5   # first值[1, 2, 3, 4, 5, 7, 6]  # 第五次遍歷結(jié)果6   # first值[1, 2, 3, 4, 5, 6, 7]  # 第六次遍歷結(jié)果
[1, 2, 3, 4, 5, 6, 7]  # 最終結(jié)果

        結(jié)果分析：待排序數(shù)組長(zhǎng)度為7，則只需遍歷6次，前6次確定6個(gè)元素，則最后一個(gè)元素?zé)o需比較。當(dāng)first為6時(shí)，6<7，進(jìn)入循環(huán)，比較的是上一輪第五次結(jié)果

[1, 2, 3, 4, 5, 7, 6]中的list[6]與list[6-1]的大小，也就是數(shù)值7和6交換位置，此時(shí)已經(jīng)卻確定好前6個(gè)數(shù)的位置，剩下最后一個(gè)位置的數(shù)，接著打印出第六次結(jié)果，然后first加1，此時(shí)7<7不成立，終止循環(huán)，此時(shí)的最后一個(gè)位置的數(shù)不進(jìn)行比較也是最大的了，返回排序好的數(shù)組，結(jié)束。

        復(fù)雜度：選擇排序的平均復(fù)雜度仍為n**2；最優(yōu)時(shí)間復(fù)雜度為n，即原數(shù)組為有序數(shù)組，遍歷第一次時(shí)如果未發(fā)生交換即可跳出循環(huán)，可設(shè)定一個(gè)變量來(lái)記錄交換次數(shù)詳情可參考排序之冒泡排序該文章中的相關(guān)做法。

以上是“如何使用python實(shí)現(xiàn)選擇排序”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！