Task 03： 数组排序

第5天打卡，附上学习链接

1 学习内容

1.1 希尔排序（Shell Sort）

将整个序列按照一定的间隔取值划分为若干个子序列，每个子序列分别进行插入排序，然后逐渐缩小间隔进行下一轮划分子序列和插入排序，直至最后一轮排序间隔为1，对整个序列进行插入排序。

算法步骤：

• （1）首先确定一个元素间隔数gap，然后将参与排序的序列按此间隔数从第1个元素开始一次划分成若干个子序列，即分别将所有位置相隔为gap的元素视为一个子序列，在各个子序列中采用某种排序方法进行插入排序；

• （2）然后减少间隔数，并重新将整个序列按新的间隔数划分为若干个子序列，再分别对各个子序列进行排序，如此下去，直到间隔数gap=1。

算法分析：

• 希尔排序方法的速度是一系列间隔数gap_i的函数；

• 不稳定排序算法

• 因为每次都除以2，向下取整的方式缩小间隔数，对有n个元素的序列，若gap₁=floor(n/2)，则经过log₂n趟排序后就有gap_p=1，所以谢尔排序方法的排序总趟数为floor(log2n)；

• 最外层的while循环为log2n数量级，中间层do-while循环为n数量级。当子序列分的越多，子序列中的元素越少，最内层的for循环的次数也就越少；反之当分的越少，子序列的元素也随之增多，但整个序列也逐步有序，而循环次数却不会随之增加。因此，希尔排序算法的时间复杂度在O(nlog2n)与O(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）把当前序列组中有序子序列两两归并，完成一遍之后序列组里的排序序列个数减半，每个子序列的长度加倍；

• （3）对长度加倍的有序子序列重复以上操作，最终得到一个长度为n的有序序列。

算法分析：

• 归并排序算法的时间复杂度等于归并趟数与每一趟归并的时间复杂度成绩。子算法merge(left_arr, right_arr):时间复杂度为O(n)，因此归并排序算法总的时间复杂度为O(nlog₂n)；

• 归并排序方法需要用到与参加排序的序列同样大小的辅助空间，所以空间复杂度为O(n)；

• 因为在两个有序子序列的归并过程中，如果两个有序序列中出现相同元素，merge(left_arr, right_arr):算法能够使前一个序列中那个相同元素先被复制，从而确保这两个元素的相对次序不发生改变，所以是稳定排序算法。

代码实现：

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“），注：分数越高的选手，排名越靠前。所有运动员的成绩都不相同。 样例1：输入为[5, 4, 3, 2, 1]，输出为["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]。

解题思路：先实现降序排列，然后构建分数和名词的字典，最后根据原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 合并排序的数组 **

题目描述：给定两个排序后的数组A和B，其中A的末端有足够的缓冲空间容纳B。编写一个方法，将B合并入A并排序。初始化A和B的元素数量分别为m和n。 样例1：输入为A=[1, 2, 3, 0, 0, 0], m=3, B=[2, 5, 6], n=3，输出为[1, 2, 2, 3, 5, 6]。

解题思路：先将数组B放进数组A的尾部，然后直接对整个数组进行排序。

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))。

双指针的思想 妙呀
将两个数组看作队列，每次从两个队列头部取出较小的数字放入结果。

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 数组中的逆序对 ***

题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 样例1：输入为[7, 5, 6, 4]，输出为5。

解题思路：思考中。。。。理不清。。。。