Task 03： 數(shù)組排序

第5天打卡脑奠，附上學(xué)習(xí)鏈接

1 學(xué)習(xí)內(nèi)容

1.1 希爾排序（Shell Sort）

將整個(gè)序列按照一定的間隔取值劃分為若干個(gè)子序列最欠，每個(gè)子序列分別進(jìn)行插入排序抹估，然后逐漸縮小間隔進(jìn)行下一輪劃分子序列和插入排序政冻，直至最后一輪排序間隔為1的止，對(duì)整個(gè)序列進(jìn)行插入排序座云。

算法步驟：

• （1）首先確定一個(gè)元素間隔數(shù)gap发侵，然后將參與排序的序列按此間隔數(shù)從第1個(gè)元素開(kāi)始一次劃分成若干個(gè)子序列，即分別將所有位置相隔為gap的元素視為一個(gè)子序列枫浙，在各個(gè)子序列中采用某種排序方法進(jìn)行插入排序刨肃；

• （2）然后減少間隔數(shù)古拴，并重新將整個(gè)序列按新的間隔數(shù)劃分為若干個(gè)子序列，再分別對(duì)各個(gè)子序列進(jìn)行排序真友，如此下去黄痪，直到間隔數(shù)gap=1。

算法分析：

• 希爾排序方法的速度是一系列間隔數(shù)gap_i的函數(shù)盔然；

• 不穩(wěn)定排序算法

• 因?yàn)槊看味汲?桅打，向下取整的方式縮小間隔數(shù)，對(duì)有n個(gè)元素的序列愈案，若gap₁=floor(n/2)挺尾，則經(jīng)過(guò)log₂n趟排序后就有g(shù)ap_p=1，所以謝爾排序方法的排序總趟數(shù)為floor(log2n)刻帚；

• 最外層的while循環(huán)為log2n數(shù)量級(jí)潦嘶，中間層do-while循環(huán)為n數(shù)量級(jí)。當(dāng)子序列分的越多崇众，子序列中的元素越少，最內(nèi)層的for循環(huán)的次數(shù)也就越少航厚；反之當(dāng)分的越少顷歌，子序列的元素也隨之增多，但整個(gè)序列也逐步有序幔睬，而循環(huán)次數(shù)卻不會(huì)隨之增加眯漩。因此，希爾排序算法的時(shí)間復(fù)雜度在O(nlog2n)與O(n²)之間麻顶。

代碼實(shí)現(xiàn)：

def shellSort(arr):
 size = len(arr)
 gap = size // 2

 while gap > 0:
 for i in range(gap, size):
 temp = arr[i]
 j = i
 while j >= gap and arr[j-gap] > temp:
 arr[j] = arr[j-gap]
 j -= gap
 arr[j] = temp
 gap = gap // 2
 return arr

1.2 歸并排序（Merge Sort）

采用經(jīng)典的分治策略赦抖，先遞歸地將當(dāng)前序列平均分為兩半，然后將有序序列兩兩合并辅肾，最終合并成一個(gè)有序序列队萤。

算法步驟：

• （1）初始時(shí)，將待排序的序列中的n個(gè)記錄看成n個(gè)有序子序列矫钓，每個(gè)子序列的長(zhǎng)度均為1要尔；

• （2）把當(dāng)前序列組中有序子序列兩兩歸并，完成一遍之后序列組里的排序序列個(gè)數(shù)減半新娜，每個(gè)子序列的長(zhǎng)度加倍赵辕；

• （3）對(duì)長(zhǎng)度加倍的有序子序列重復(fù)以上操作，最終得到一個(gè)長(zhǎng)度為n的有序序列概龄。

算法分析：

• 歸并排序算法的時(shí)間復(fù)雜度等于歸并趟數(shù)與每一趟歸并的時(shí)間復(fù)雜度成績(jī)还惠。子算法merge(left_arr, right_arr):時(shí)間復(fù)雜度為O(n)，因此歸并排序算法總的時(shí)間復(fù)雜度為O(nlog₂n)私杜；

• 歸并排序方法需要用到與參加排序的序列同樣大小的輔助空間蚕键，所以空間復(fù)雜度為O(n)互拾；

• 因?yàn)樵趦蓚€(gè)有序子序列的歸并過(guò)程中，如果兩個(gè)有序序列中出現(xiàn)相同元素嚎幸，merge(left_arr, right_arr):算法能夠使前一個(gè)序列中那個(gè)相同元素先被復(fù)制颜矿，從而確保這兩個(gè)元素的相對(duì)次序不發(fā)生改變，所以是穩(wěn)定排序算法嫉晶。

代碼實(shí)現(xiàn)：

def merge(left_arr, right_arr):
    arr = []
    while left_arr and right_arr:
        if left_arr[0] <= right_arr[0]:
            arr.append(left_arr.pop(0))
        else:
            arr.append(right_arr.pop(0))
            
    while left_arr:
        arr.append(left_arr.pop(0))
    while right_arr:
        arr.append(right_arr.pop(0))
    return arr

def mergeSort(arr):
    size = len(arr)
    if size < 2:
        return arr
    mid = len(arr) // 2
    left_arr, right_arr = arr[0:mid], arr[mid:]
    return merge(mergeSort(left_arr), mergeSort(right_arr))

2 練習(xí)題目

2.1 0506 相對(duì)名次 *

題目描述：給出N名運(yùn)動(dòng)員的成績(jī)骑疆，找出他們的相對(duì)名次并授予前三名對(duì)應(yīng)的獎(jiǎng)牌。前三名運(yùn)動(dòng)員將會(huì)被分別授予”金牌“替废，”銀牌“和”銅牌"（"Gold Medal"箍铭， "Silver Medal"， ”Bronze Medal“）椎镣，注：分?jǐn)?shù)越高的選手诈火，排名越靠前。所有運(yùn)動(dòng)員的成績(jī)都不相同状答。 樣例1：輸入為[5, 4, 3, 2, 1]冷守，輸出為["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]。

解題思路：先實(shí)現(xiàn)降序排列惊科，然后構(gòu)建分?jǐn)?shù)和名詞的字典拍摇，最后根據(jù)原score找出結(jié)果即可。

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        score_sort = sorted(score, reverse=True)
        rank_list = ["Gold Medal", "Silver Medal",
                     "Bronze Medal"]+[str(i+4) for i in range(len(score)-3)]
        dic = dict(zip(score_sort, rank_list))
        res = [dic.get(i) for i in score]
        return res

2.2 面試題 10.01 合并排序的數(shù)組 **

題目描述：給定兩個(gè)排序后的數(shù)組A和B馆截，其中A的末端有足夠的緩沖空間容納B充活。編寫(xiě)一個(gè)方法，將B合并入A并排序蜡娶。初始化A和B的元素?cái)?shù)量分別為m和n混卵。 樣例1：輸入為A=[1, 2, 3, 0, 0, 0], m=3, B=[2, 5, 6], n=3，輸出為[1, 2, 2, 3, 5, 6]窖张。

解題思路：先將數(shù)組B放進(jìn)數(shù)組A的尾部幕随，然后直接對(duì)整個(gè)數(shù)組進(jìn)行排序。

class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        A[m:] = B
        A.sort()

時(shí)間復(fù)雜度：O((m+n)log(m+n))荤堪； 空間復(fù)雜度：O(log(m+n))合陵。

雙指針的思想 妙呀
將兩個(gè)數(shù)組看作隊(duì)列，每次從兩個(gè)隊(duì)列頭部取出較小的數(shù)字放入結(jié)果澄阳。

class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        sorted = []
        pa, pb = 0, 0  # 使用pa和pb來(lái)作為隊(duì)列的頭部指針
        while pa < m or pb < n:
            if pa == m:
                sorted.append(B[pb])
                pb += 1
            elif pb == n:
                sorted.append(A[pa])
                pa += 1
            elif A[pa] < B[pb]:
                sorted.append(A[pa])
                pa += 1
            else:
                sorted.append(B[pb])
                pb += 1
         A[:] = sorted

時(shí)間復(fù)雜度：O(m+n)拥知； 空間復(fù)雜度：O(m+n)。

2.3 劍指Offer 51 數(shù)組中的逆序?qū)?***

題目描述：在數(shù)組中的兩個(gè)數(shù)字碎赢，如果前面一個(gè)數(shù)字大于后面的數(shù)字低剔，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Α］斎胍粋€(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)襟齿。 樣例1：輸入為[7, 5, 6, 4]姻锁，輸出為5。

解題思路：思考中猜欺。位隶。。开皿。理不清涧黄。。赋荆。笋妥。