leetcode912. 排序数组

题目描述

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

链接：https://leetcode-cn.com/problems/sort-an-array

解题思路

1.快速排序
没什么好说的，递归+分治的应用，通常的时间复杂度最好，常用来只排序前k个数（某次排序完，返回的pivot_pos等于k即可，因为pivot_pos之前所有的数都比pivot_key小）。
时间复杂度O(nlogn) 空间复杂度O(logn)。
注意：原版快排在例子为几乎已经排好序的时候会超时，需要做一下pivot随机化，即随便在low和high中间找个数和low交换。

random_pos = random.randint(low, high)
nums[low], nums[random_pos] = nums[random_pos], nums[low]

2.堆排序（大根堆）

在计算机科学中，堆是专门的树型数据结构。堆的属性有：如果P 是C 的父节点，那么P 的关键(P 的值)就大于或等于(在最大堆排序) 或 小于或等于(在最小堆排序)C 的关键。堆在堆的最“顶部”（没有父节点）的节点称为根节点。

堆是建立在数组基础上的数据结构，堆排序本质上是对选择排序的优化，就是用O(logn)的时间内在剩下的数中找出最大的那个。
当数组需要升序排序的时候，使用的是大根堆；当数组需要降序排序的时候，需要用小根堆。
为什么呢？以递增数组用大根堆为例：
使用堆排序主要是用堆顶元素，如果使用大根堆排降序，此时堆顶的元素是最大的，当我们取出堆顶元素时，此时大根堆的性质就变了。那么下次就难以找到第二大元素，要重新建堆。
整个过程持续迭代至只有一个数剩下。
基本过程：
- 输入：一系列的无序元素（比如说，数字）组成的输入数组A。
- 经过：堆排序的过程可以具体分为三步，创建堆，调整堆，堆排序。
- 创建堆，以数组的形式将堆中所有的数据重新排序，使其成为最大堆/最小堆。
- 调整堆，调整过程需要保证堆序性质：在一个二叉堆中任意父节点大于其子节点。
- 堆排序，取出位于堆顶的第一个数据（最大堆则为最大数，最小堆则为最小数），放入A的末尾，再将末尾之前的数组对作调整堆的迭代/重复运算，直至输入数组A中只剩下最后一个元素。
- 输出：已经排序完成的A数组。
时间复杂度O(nlogn) 空间复杂度O(1)。堆排序是一种原地排序，很节省存储空间。
3.归并排序
归并排序基于分治思想需要使用递归。
归并排序的原理是不断利用二分法将数组一直“归”到数组里面只剩两个，然后再两个数两个组排序后归起来->四个数两个组排序后归起来->八个数两个组排序后归起来->...->所有的都排序完成。
mergeSort函数需要背一下。
时间复杂度O(nlogn) 空间复杂度O(n)，因为tmp数组最长可以到n。归并排序的优点是它是一种稳定排序。

稳定排序有：冒泡，插入，归并。
不稳定排序有：选择、快速、堆、冒泡、希尔。

解题代码

1.快速排序

class Solution:
    def Partition(self, nums: List[int], low: int, high: int):
        random_pos = random.randint(low, high)
        nums[low], nums[random_pos] = nums[random_pos], nums[low]
        pivot_key = nums[low]
        while low < high:
            while low < high and nums[high] >= pivot_key:
                high -= 1
            nums[low], nums[high] = nums[high], nums[low]
            while low < high and nums[low] <= pivot_key:
                low += 1
            nums[low], nums[high] = nums[high], nums[low]
        return low

    def QuickSort(self, nums: List[int], low: int, high: int):
        if low < high:
            pivot_pos = self.Partition(nums, low, high)
            self.QuickSort(nums, low, pivot_pos-1)
            self.QuickSort(nums, pivot_pos+1, high)

    def sortArray(self, nums: List[int]) -> List[int]:
        self.QuickSort(nums, 0, len(nums)-1)
        return nums

2.堆排序（大根堆）

class Solution:
    # 堆排序
    def sortArray(self, nums: List[int]) -> List[int]:
        self.heapSort(nums)
        return nums

    # 将当前堆某个父节点下沉到该去的位置（和那个位置的节点交换）
    def adjust(self, nums: List[int], parentIndex: int, lastIndex: int):
        lchildIndex = 2 * parentIndex + 1
        # 看看这个节点的最大子节点需不需要和父节点交换（先判断有没有左子节点，并进一步判断右子节点）
        while lchildIndex <= lastIndex:
            rchildIndex = lchildIndex + 1
            maxChildIndex = lchildIndex
            # 判断哪个是最大的子节点
            if rchildIndex <= lastIndex and nums[rchildIndex] > nums[maxChildIndex]:
                maxChildIndex = rchildIndex
            # 如果父节点比子节点都大，那就不用交换了
            if nums[parentIndex] >= nums[maxChildIndex]:
                break
            # 如果父节点比较小，那就需要和最大子节点交换（下沉）
            nums[parentIndex], nums[maxChildIndex] = nums[maxChildIndex], nums[parentIndex]
            # 这时候被下沉的那个原来的父节点可能并不适合做下一个子树的父节点，因此还要循环
            parentIndex = maxChildIndex
            lchildIndex = 2 * parentIndex + 1

    # 堆排序（升序）
    def heapSort(self, nums: List[int]):
        lastIndex = len(nums) - 1
        # 先建一个大根堆(下沉每一个父节点到正确位置)
        for i in range(int((lastIndex-1)/2), -1, -1):
            self.adjust(nums, i, lastIndex)
        # 对每一个堆进行调整，调整完了下沉当前最新的父节点以后生成一个新堆
        for i in range(lastIndex, 0, -1): # 要一直调整到堆只剩下一个节点
            # 交换堆顶和堆底
            nums[i], nums[0] = nums[0], nums[i]
            # 生成长度-1的新堆，调整新的堆的root节点该去的位置
            self.adjust(nums, 0, i-1)

3.归并排序

class Solution:
    # 堆排序
    def sortArray(self, nums: List[int]) -> List[int]:
        self.mergeSort(nums, 0, len(nums)-1)
        return nums

    # 把当前归出来的小数组（最低有俩数）从low到high的位置并起来
    def merge(self, nums: List[int], low: int, mid: int, high: int):
        tmp = [] # 需要建立一个临时数组，把两个数组中较小的数添加进这个数组里
        # 第一个数组为nums[low:mid+1]，第二个数组为nums[mid:high+1]
        i, j = low, mid+1
        while i <= mid and j <= high: # 找两个数组中较小的那个数
            if nums[i] <= nums[j]:
                tmp.append(nums[i])
                i += 1
            elif nums[i] > nums[j]:
                tmp.append(nums[j])
                j += 1
        # 接上没有走完的那个数组的剩余部分
        if i > mid:
            while j <= high:
                tmp.append(nums[j])
                j += 1
        if j > high:
            while i <= mid:
                tmp.append(nums[i])
                i += 1
        # 此时tmp已经是排好序的两个数组的合并数组了
        nums[low: high+1] = tmp # 把tmp合并回原来的数组


    # 归并排序，注意包含mid，背过这一段
    def mergeSort(self, nums: List[int], low: int, high: int):
        if low < high: # 每个组剩一个就不需要再归了
            mid = int((low+high)/2)
            self.mergeSort(nums, low, mid)
            self.mergeSort(nums, mid+1, high)
            self.merge(nums, low, mid, high)