Task 03： 數(shù)組排序
第5天打卡，附上學習鏈接
1 學習內容
1.1 希爾排序（Shell Sort）
將整個序列按照一定的間隔取值劃分為若干個子序列，每個子序列分別進行插入排序，然后逐漸縮小間隔進行下一輪劃分子序列和插入排序，直至最后一輪排序間隔為1，對整個序列進行插入排序。
算法步驟：
（1）首先確定一個元素間隔數(shù)gap，然后將參與排序的序列按此間隔數(shù)從第1個元素開始一次劃分成若干個子序列，即分別將所有位置相隔為gap的元素視為一個子序列，在各個子序列中采用某種排序方法進行插入排序；
（2）然后減少間隔數(shù)，并重新將整個序列按新的間隔數(shù)劃分為若干個子序列，再分別對各個子序列進行排序，如此下去，直到間隔數(shù)gap=1。
算法分析：
希爾排序方法的速度是一系列間隔數(shù)gapi的函數(shù)；
不穩(wěn)定排序算法
因為每次都除以2，向下取整的方式縮小間隔數(shù)，對有n個元素的序列，若gap1=floor(n/2)，則經過log2n趟排序后就有gapp=1，所以謝爾排序方法的排序總趟數(shù)為floor(log2n)；
最外層的while循環(huán)為log2n數(shù)量級，中間層do-while循環(huán)為n數(shù)量級。當子序列分的越多，子序列中的元素越少，最內層的for循環(huán)的次數(shù)也就越少；反之當分的越少，子序列的元素也隨之增多，但整個序列也逐步有序，而循環(huán)次數(shù)卻不會隨之增加。因此，希爾排序算法的時間復雜度在O(nlog2n)與O(n2)之間。
代碼實現(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）
采用經典的分治策略，先遞歸地將當前序列平均分為兩半，然后將有序序列兩兩合并，最終合并成一個有序序列。
算法步驟：
（1）初始時，將待排序的序列中的n個記錄看成n個有序子序列，每個子序列的長度均為1；
（2）把當前序列組中有序子序列兩兩歸并，完成一遍之后序列組里的排序序列個數(shù)減半，每個子序列的長度加倍；
（3）對長度加倍的有序子序列重復以上操作，最終得到一個長度為n的有序序列。
算法分析：
歸并排序算法的時間復雜度等于歸并趟數(shù)與每一趟歸并的時間復雜度成績。子算法merge(left_arr, right_arr):時間復雜度為O(n)，因此歸并排序算法總的時間復雜度為O(nlog2n)；
歸并排序方法需要用到與參加排序的序列同樣大小的輔助空間，所以空間復雜度為O(n)；
因為在兩個有序子序列的歸并過程中，如果兩個有序序列中出現(xiàn)相同元素，merge(left_arr, right_arr):算法能夠使前一個序列中那個相同元素先被復制，從而確保這兩個元素的相對次序不發(fā)生改變，所以是穩(wěn)定排序算法。
代碼實現(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 練習題目
2.1 0506 相對名次 *
題目描述：給出N名運動員的成績，找出他們的相對名次并授予前三名對應的獎牌。前三名運動員將會被分別授予”金牌“，”銀牌“和”銅牌"（"Gold Medal"， "Silver Medal"， ”Bronze Medal“），注：分數(shù)越高的選手，排名越靠前。所有運動員的成績都不相同。 樣例1：輸入為[5, 4, 3, 2, 1]，輸出為["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]。
解題思路：先實現(xiàn)降序排列，然后構建分數(shù)和名詞的字典，最后根據(jù)原score找出結果即可。
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ù)組 **
題目描述：給定兩個排序后的數(shù)組A和B，其中A的末端有足夠的緩沖空間容納B。編寫一個方法，將B合并入A并排序。初始化A和B的元素數(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放進數(shù)組A的尾部，然后直接對整個數(shù)組進行排序。
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()
時間復雜度：O((m+n)log(m+n))； 空間復雜度：O(log(m+n))。
雙指針的思想 妙呀
將兩個數(shù)組看作隊列，每次從兩個隊列頭部取出較小的數(shù)字放入結果。
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來作為隊列的頭部指針
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
時間復雜度：O(m+n)； 空間復雜度：O(m+n)。
2.3 劍指Offer 51 數(shù)組中的逆序對 ***
題目描述：在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序對。輸入一個數(shù)組，求出這個數(shù)組中的逆序對的總數(shù)。 樣例1：輸入為[7, 5, 6, 4]，輸出為5。
解題思路：思考中。。。。理不清。。。。
