python數(shù)據(jù)結(jié)構(gòu)與算法之排序

排序算法的穩(wěn)定性：

假設(shè)有一串?dāng)?shù)據(jù)：（4，1）（3，1）（3，7）（5，6）；要求按照第一個(gè)數(shù)排序，結(jié)果如下：

第一種：（3，1）（3，7）（4，1）（5，6）（3相同，維持原來(lái)的次序）

第二種：（3，7）（3，1）（4，1）（5，6）（3相同，次序被改變）

第一種是穩(wěn)定的。

冒泡排序(以從小到大排為例)：

每次走一遍把最大的元素冒泡，排到最后。

'''
冒泡排序：它也可以用于之前講的鏈表什么的,只是交換部分稍微煩一點(diǎn)，思想一樣。這里簡(jiǎn)單一點(diǎn) ，以數(shù)字為例
'''
def bubble_sort(alist):
    '''冒泡排序，參數(shù)為列表'''
    n = len(alist)-1
    for j in range(n):
        for i in range(n-j):
            if alist[i]>alist[i 1]:
                # 前一個(gè)大于后一個(gè)，交換
                alist[i], alist[i 1] = alist[i 1], alist[i]    # 這樣寫(xiě)在python這種動(dòng)態(tài)語(yǔ)言中可以

if __name__ == '__main__':
    a = [2,0,5,1,10]
    bubble_sort(a)
    print(a)

冒泡排序的時(shí)間復(fù)雜度為：最壞可以認(rèn)為是O（n^2）,穩(wěn)定的

改進(jìn)：假如傳入的序列就是有序的，比如[1,2,3,4,5,6]。此時(shí)按照上面代碼還是要一步步比較，復(fù)雜度是一樣的。改進(jìn)之后，最優(yōu)時(shí)間復(fù)雜度為O(n)，最壞時(shí)間復(fù)雜度不變。

def bubble_sort(alist):
    '''冒泡排序，參數(shù)為列表'''
    n = len(alist)-1
    for j in range(n):
        count = 0
        for i in range(n-j):
            if alist[i]>alist[i 1]:
                # 前一個(gè)大于后一個(gè)，交換
                alist[i], alist[i 1] = alist[i 1], alist[i]    # 這樣寫(xiě)在python這種動(dòng)態(tài)語(yǔ)言中可以
                count  = 1
        if count == 0:
            return 

選擇排序：

思想解釋?zhuān)好看握业阶钚〉闹担c無(wú)序數(shù)中的一個(gè)數(shù)交換，比如：

a = [52，100，23，43，55，20，17，108]

找到最小值是17，將17與52交換，得：

a = [17，100，23，43，55，20，52，108]

看除了第一個(gè)數(shù)17外，其他最小的為20，與“第一個(gè)數(shù)”100交換：

a = [17，20，23，43，55，100，52，108]

此時(shí)，前面兩個(gè)數(shù)已經(jīng)有序，以此往下。

def select_sort(alist):
    """選擇排序，既然是研究數(shù)據(jù)結(jié)構(gòu)與算法，這里不用min()函數(shù)"""
    n = len(alist)
    for j in range(n-1):
        # 記錄最小值的位置，這里首次默認(rèn)是無(wú)序中的第一個(gè)
        min_index = j
        for i in range(j 1,n):
            if alist[i]<alist[min_index]:
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j]

選擇排序的時(shí)間復(fù)雜度：O(n^2)，不穩(wěn)定

插入算法：

思想理解，與上面選擇排序有點(diǎn)雷士，其實(shí)還是將序列無(wú)形的分為兩部分。比如序列[52，100，23，43，55，20，17，108]。

將序列分為[52，                      100，23，43，55，20，17，108]，第一部分是有序的。

然后將無(wú)序中的第一個(gè)100與有序中52比較，放在正確的位置[52，100，                      23，43，55，20，17，108]，

同理接著比較23與[52，100]，將其插入正確的位置[23，52，100，                            43，55，20，17，108]