python– 簡單的排序

1. 冒泡排序
--> 兩兩比較,交換位置
--> 屬交換排序
-->  n個數從左至右，編號從0開始到n-1，索引0和1的值比較，如果索引0的值大，則交換兩者位置，如
果索引1大，則不交換。繼續比較索引1和2的值，將大值放在右側。直至n-2和n-1比較完，第
一輪比較完成。第二輪從索引0比較到n-2，因為最右側n-1位置上已經是最大值了。依次類推，
每一輪都會減少最右側的不參與比較，直至剩下最后2個數比較 
 
冒泡排序方法(一)
lst = [1,9,4,8,3,7,5,2,6,10]
length = len(lst)
for i in range(length):
    for j in range(length-1-i):   
        if lst[j] > lst[j+1]:
            lst[j], lst[j+1] = lst[j+1], lst[j]
print(lst)
第四行, length-1-i,為什么要減i呢? 
    因為每次比較過程,都可以確定出當前這輪的極值(極大),并且放置在最右端,形成一個有序區域. 
    不減i也不會影響最終比較結果,只是做了一些無用的比較
如果列表內是字符串,上面代碼依然適用.因為'>' '<' 可用于同類型比較,(不同類型的比較,需要設定key的類型)
上面代碼的時間復雜度為O(n**2),優化點,如果某一輪比較過程中并沒有交換發生,意味著序列已經排好

冒泡排序方法(二)
lst = [1,9,4,8,3,7,5,2,6,10]
length = len(lst)
for i in range(length):
    flag = False
    for j in range(length-1-i):
        if lst[j] > lst[j+1]:
            lst[j], lst[j+1] = lst[j+1], lst[j]
            flag = True
    if not flag:
        break
print(lst)

紅色部分為方法一二的區別,用標記輔助排序,記錄此輪比較是否有交換發生, 如果沒有發生交換,排序結束

總結

冒泡法需要數據一輪輪比較

最好的情況是,初始順序是最終的期望,遍歷n-1次

最差的情況是,初始順序與期望相反,遍歷n(n-1)/2

用標記記錄此輪是否有交換發生,如果沒有發生交換,排序結束

時間復雜度為O(n**2)

2. 簡單選擇排序

–> 兩兩比較,找極值

–> n個數從左至右，索引從0開始到n-1，兩兩依次比較，記錄大值索引，此輪所有數比較完畢，將
大數和索引0數交換，如果大數就是索引1，不交換。第二輪，從1開始比較，找到最大值，將它
和索引1位置交換，如果它就在索引1位置則不交換。依次類推，每次左邊都會固定下一個大數(降序排列)。

簡單排序實現(一)

lst = [1,9,4,8,3,7,5,2,6,10]
length = len(lst)
for i in range(length):
    maxindex = i                 # 默認迭代值i對應的值為最大值
    for j in range(i+1,length):
        if lst[maxindex] < lst[j]:
            maxindex = j
    if i != maxindex:           # 避免兩數相等的情況(相鄰數字大小相等,不交換位置)
        lst[i], lst[maxindex] = lst[maxindex], lst[i]
print(lst)

總結
-> 需要數據一輪輪比較，并在每一輪中發現極值
-> 沒有辦法知道當前輪是否已經達到排序要求，但是可以知道極值是否在目標索引位置上
-> 遍歷次數n(n-1)/2
-> 時間復雜度O(n2)


3. 插入排序
-> 在前端增加哨兵位置,構建有序區域,迭代無序區數據和有序區的數據做比較運算

->?增加一個哨兵位,每輪放入待比較數
哨兵依次和待比較的前一個數據比較,大數靠右移動,找到哨兵 (中的值的位置) 位置插入
每一輪結束后,得到一個從開始到待比較數位置的一個有序序列

插入排序實現(一)
lst = [1,9,8,5,6,7,4,3,10]
num1 = [0] + lst               # 列表前補0,做哨兵位
length = len(num1)
for i in range(2,length):      # 索引0為哨兵,1位有序區
    num1[0] = num1[i]
    j = i - 1                  # j為有序區邊界(極大)值索引
    if num1[j] > num1[0]:      # 大數右移,找到可插入位置(當前哨兵值)
        while num1[j] > num1[0]:
            num1[j+1] = num1[j] # 依次右移
            j -= 1
        num1[j+1] = num1[0]    # 將哨兵插入, 注意插入在右側要 +1
print(num1)
print(num1[1:])

~~~~~~~~~~~~~~~~~以下為函數輸出~~~~~~~~~~~
[10, 1, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 3, 4, 5, 6, 7, 8, 9, 10]

問題1, 為什么需要執行 num1[j+1] = num1[0].
觸發該行操作的條件是, 待比較數小于哨兵,那么就在該數的下一個索引位置插入哨兵
問題2, 輸出num1列表為什么會多出數字10.
10在原列表中索引為-1,最后一次比較中,10不大于哨兵10,循環結束,初始哨兵位的0已被10覆蓋,所以列表num1第一個元素為10


選擇排序還需要繼續啃,還是有優化點值得學習的.