Task 03： 数组排序
第6天打卡，附上学习链接
1 学习内容
1.1 快速排序（Quick Sort）
通过一趟排序将无序序列分为独立的两个序列，第一个序列的值均比第二个序列的值小，然后递归地排序两个子序列，以达到整个序列有序。
算法步骤：
（1）从数组中找到一个基准数；
（2）然后将数组中比基数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧，从而将数组拆分为左右两个部分；
（3）再对左右两个部分分别重复第二步，直到各个部分只有一个数，则排序结束。
算法分析：
在参加排序的元素初始时已经有序的情况下，快速排序方法花费的时间最长。此时，第1趟经过n-1次比较之后，确定第1个元素仍然在原来的位置上，并得到1个长度为n-1的子序列；第2趟排序经过n-2次比较后，确定第2个元素在它原来的位置上，又得到1个长度为n-2的子序列，类推得到最终的总比较次数为n-1+n-2+...+1=n(n-1)/2，因此时间复杂度为O(n2)；
还有一种情况，每趟排序后，分界元素正好定位在序列的中间，从而把当前参加排序的序列分成大小相等的前后两个子序列，而对长度为n的序列进行快速排序所需要的时间为T(n)<=n+2T(n/2)<=2n+4T(n/4)<=3n+8T(n/8)...<=(log2n)，因此快速排序方法的时间复杂度为O(nlog2n)，时间性能显然优于之前的几种排序算法。
无论快速排序算法递归与否，排序过程中都需要用到堆栈或其他结构的辅助空间来存放当前待排序序列的首、尾位置。最坏的情况下，空间复杂度为O(n)；
进一步改进，在一趟排序之后比较被划分所得到的两个子序列的长度，先对长度较短的子序列进行快速排序，此时空间复杂度可以达到O(log2n)；
快速排序是一种不稳定排序算法，也是一种不适合在链表结构上实现的排序算法。
代码实现：
import random
def randomPartition(arr: [int], low: int, high: int):
i = random.randint(low, high)
arr[i], arr[high] = arr[high], arr[i]
return partition(arr, low, high)
def partition(arr: [int], low: int, high: int):
x = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= arr[high]:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
def quickSort(arr, low, high):
if low < high:
pi = randomPartition(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
return arr
1.2 堆排序（Heap Sort）
将数组转化为大顶堆，重复从大顶堆中取出数值最大的节点，并让剩余的堆维持大顶堆性质。
堆的定义：堆是符合以下两个条件之一的完全二叉树，大顶堆即根节点值>=子节点值；小顶堆即根节点值<=子节点值。
算法步骤（主要涉及初始堆建立方法和堆调整方法）：
（1）首先将无序序列构造成第1个大顶堆（初始堆），使得n个元素的最大值处于序列的第1个位置；
（2）然后交换序列的第1个元素(最大值元素)与最后一个元素的位置；
（3）此后，再把序列的前n-1个元素组成的子序列调整成一个新的大顶堆，这样得到第2个最大值元素，把子序列的第1个元素（最大值元素）与第n-1个元素交换位置；
（4）此后再把序列的前n-2个元素调整成一个新的大顶堆，...，如此下去，直到整个序列变换成一个有序序列。
初始堆建立方法：
（1）如果原始序列对应的完全二叉树（不一定是堆）的深度为d，则从d-1层最右侧分支节点（序号为floor(n/2)）开始，初始时令i=floor(n/2)，调用堆调整算法；
（2）每调用一次堆调整算法，执行一次i=i-1，直到i==1时，再调用一次，就把原始序列调整为了一个初始堆。
堆调整方法：
即把移走了最大值元素以后的剩余元素的序列再构造为一个新的堆积。
（1）从根节点开始，自上而下地调整节点的位置，使其成为堆积。即把序号为i的节点与其左子树节点（序号为2i）、右子树节点（序号为2i+1）中值最大的节点交换位置；
（2）因为交换了位置，使得当前节点的左右子树原有的堆积特性被破坏。于是从当前节点的左右子树节点开始，自上而下地继续进行类似的调整；
（3）如此下去直到整颗完全二叉树成为一个大顶堆。
算法分析：
堆排序的时间主要花费在将原始序列构造为一个初始堆和不断调整堆两方面；
设原始序列所对应的完全二叉树深度为d，算法由两个独立的循环组成：
（1）在第1个循环构造初始堆时，从i=d-1层开始，到i=1层为止，对每个分支节点都要调用一次adjust算法，每一次adjust算法，对于第i层一个节点到第d层上建立的子堆积，所有节点可能移动的最大距离为该子堆根节点移动到最后一层（第d层）的距离即d-i；
（2）第i层上节点最多有2i-1个，所以每次adjust算法最大移动距离为2i-1*(d-i)。所以堆排序的第1个循环所需时间应该是各层上的节点数与该层上节点可移动的最大距离之积的总和，时间复杂度为O(n)（原谅我没看懂）；
（3）第2个循环中每次调用adjust算法一次，节点移动的最大距离为这棵完全二叉树的深度d=floor(log2n)+1，一共调用了n-1次adjust算法，此循环的时间复杂度为(n-1)(floor(log2n)+1)=O(nlog2n)；
（4）综合，堆排序的时间复杂度为O(nlog2n)；
堆排序需要一个记录大小的辅助空间，所以堆排序的空间复杂度为O(1)。
堆排序属于不稳定排序算法，也是一种不适合在链表上实现的排序。
代码实现：
# 调整为大顶堆
def heapify(arr: [int], index: int, end: int):
left = index * 2 + 1
right = left + 1
while left <= end:
# 当前节点为非叶子结点
max_index = index
if arr[left] > arr[max_index]:
max_index = left
if right <= end and arr[right] > arr[max_index]:
max_index = right
if index == max_index:
# 如果不用交换，则说明已经交换结束
break
arr[index], arr[max_index] = arr[max_index], arr[index]
# 继续调整子树
index = max_index
left = index * 2 + 1
right = left + 1
# 初始化大顶堆
def buildMaxHeap(arr: [int]):
size = len(arr)
# (size-2) // 2 是最后一个非叶节点，叶节点不用调整
for i in range((size - 2) // 2, -1, -1):
heapify(arr, i, size - 1)
return arr
# 升序堆排序，思路如下：
# 1. 先建立大顶堆
# 2. 让堆顶最大元素与最后一个交换，然后调整第一个元素到倒数第二个元素，这一步获取最大值
# 3. 再交换堆顶元素与倒数第二个元素，然后调整第一个元素到倒数第三个元素，这一步获取第二大值
# 4. 以此类推，直到最后一个元素交换之后完毕。
def maxHeapSort(arr: [int]):
buildMaxHeap(arr)
size = len(arr)
for i in range(size):
arr[0], arr[size-i-1] = arr[size-i-1], arr[0]
heapify(arr, 0, size-i-2)
return arr
2 练习题目
2.1 0075 颜色分类 ** (经典的「荷兰国旗问题」)
题目描述：给定一个包含红色、白色和蓝色，一共n个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按红色、白色、蓝色顺序排列，此处使用整数0、1和2表示红、白和蓝。 样例1：输入为nums=[2, 0, 2, 1, 1, 0]，输出为[0, 0, 1, 1, 2, 2]； 样例2：输入为nums=[2, 0, 1]，输出为[0, 1, 2]； 样例3：输入为nums=[0]，输出为[0]； 样例4：输入为nums=[1]，输出为[1]。
解题思路1：单指针。用一个指针ptr表示头部，代表数组nums从位置0到位置ptr-1都属于头部。第一次遍历，找到0，就与头部位置的元素交换，并往后扩充一个位置；第二次遍历，同理找到1。
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
ptr = 0
for i in range(n):
if nums[i] == 0:
nums[i], nums[ptr] = nums[ptr], nums[i]
ptr += 1
for i in range(ptr, n):
if nums[i] == 1:
nums[i], nums[ptr] = nums[ptr], nums[i]
ptr += 1
时间复杂度：O(n)； 空间复杂度：O(1)。
解题思路2：双指针。一次遍历，p0指针用来交换0，p1指针用来交换1。
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
p0 = p1 = 0
for i in range(n):
if nums[i] == p1:
nums[i], nums[p1] = nums[p1], nums[i]
p1 += 1
elif nums[i] == 0:
nums[i], nums[p0] = nums[p0], nums[i]
if p0 < p1:
nums[i], nums[p1] = nums[p1], nums[i]
p0 += 1
p1 += 1
时间复杂度：O(n)； 空间复杂度：O(1)。
解题思路3：双指针。p0指针用来交换0到首部，初始值为0，从左向右遍历；p2指针用来交换2到尾部，初始值为n-1，从右向左遍历。
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
p0, p2 = 0, n-1
i = 0
while i <= p2:
while i <= p2 and nums[i] == 2:
nums[i], nums[p2] = nums[p2], nums[i]
p2 -= 1
if nums[i] == 0:
nums[i], nums[p0] = nums[p0], nums[i]
p0 += 1
i += 1
时间复杂度：O(n)； 空间复杂度：O(1)。
2.2 0215 数组中的第K个最大元素 **
题目描述：给定整数数组nums和整数k，返回数组中第k个最大的元素。 样例1：输入为[3, 2, 1, 5, 6, 4]， k=2，输出5； 样例2：输入为[3, 2, 3, 1, 2, 4, 5, 5, 6]，k=4，输出为4。
解题思路：乱，整理一下。
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def partition(nums, left, right):
pivot = nums[left]
i, j = left, right
while i < j:
while i < j and nums[j] >= pivot:
j -= 1
nums[i] = nums[j]
while i < j and nums[i] <= pivot:
i += 1
nums[j] = nums[i]
nums[i] = pivot
return i
def topk_split(nums, k, left, right):
if left < right:
index = partition(nums, left, right)
if index == k:
return
elif index < k:
topk_split(nums, k, index+1, right)
else:
topk_split(nums, k, left, index-1)
def topk_large(nums, k):
topk_split(nums, len(nums)-k, 0, len(nums)-1)
return nums[len(nums)-k]
return topk_large(nums, k)
2.3 剑指Offer 40 最小的k个数 *
题目描述：输入整数数组arr，找出其中最小的k个数。 样例1：输入为arr=[3, 2, 1], k=2，输出为[1, 2]或[2, 1]； 样例2：输入为arr=[0, 1, 2, 1], k=1，输出为[0]。
解题思路：排序，去前k个数即可。
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
arr.sort()
return arr[:k]
