算法：排序

class Solution:
  def bubble_sort(self, arr):
     length = len(arr)
      for i in range(1, length):  # 最外面循环n-1次
        for j in range(0, length-i):  # 每次都是从第一个元素开始遍历比较，但末尾不用比较
          if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]
      return arr
  
  def solution(self, arr):
     return self.bubble_sort(arr)

class Solution:
  def selectionSort(self, arr):
    length = len(arr)
    for i in range(length-1):
      min_i = i  # 记录未排序列表中最小数的索引
      for j in range(i+1, length):
        if arr[j] < arr[i]:
          min_i = j
      if min_i != i:  # 如果最小数的位置与i不一致，说明需要进行交换
        arr[i], arr[min_i] = arr[min_i], arr[i]
    return arr
  
 def sortArray(self, nums: List[int]) -> List[int]:
     return self.selectionSort(nums)

class Solution:
  def insertionSort(self, arr):
    length = len(arr)
    for i in range(1, length):
      tmp = arr[i]
      j = i
      while j<i and arr[j-1] > tmp:
        arr[j] = arr[j-1]  # 往右边移动
        j -= 1
      arr[j] = tmp  # 放到该位置
    return arr
 
 def sortArray(self, nums: List[int]) -> List[int]:
    return self.insertionSort(nums)

class Solution:
  def shellSort(self, arr):
    size = len(arr)
    gap = size // 2  # 这里暂定先按照一半进行区分
    while gap > 0:
      for i in range(gap, size):
        tmp = arr[i]
        j = i
        while j>= gap and arr[j-gap] > tmp:  # gap间隔对插入排序
          arr[j] = arr[j-gap]
          j -= gap
        arr[j] = tmp
      gap = gap // 2  # 缩小间隔gap
    return arr
 
 def sortArray(self, nums: List[int]) -> List[int]:
    return self.shellSort(nums)

class Solution:
  def merge(self, 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))
    
    arr += left_arr if left_arr else right_arr
    return arr
    
  def mergeSort(self, arr):
    size = len(arr)
    if size < 2:  # 递归结束条件
      return arr
    mid = size // 2
    left_arr, right_arr = arr[0: mid], arr[mid:]
    return self.merge(self.mergeSort(left_arr), self.mergeSort(right_arr))
 
 def sortArry(self, nums: List[int]) -> List[int]:
    return self.mergeSort(nums)

class Solution:
  def randomPartition(self, arr: List[int], low: int, high: int):
    i = random.randint(low, high)
    arr[i], arr[high] = arr[high], arr[i]
    rerurn self.partition(arr, low, high)
  
  def partition(self, arr: List[int], low: int, high: int):
    i = low - 1
    pivot = arr[high]  # 取最右边值作为基准，但是随机更换后最高元素的值，带来的随机性
    for j in range(low, high):
      if arr[j] < pivot:
        i += 1
        arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]  # 基准点下标是index+1，
    return i+1
    
  def quickSort(self, arr, low, high):
    if low < high:
      pivot = self.randomPartition(arr, low, high)
      self.quickSort(arr, low, pivot-1)
      self.quickSort(arr, pivot+1, high)
    return arr
  
  def sortArray(self, nums: List[int]) -> List[int]:
    return self.quickSort(nums, 0, len(nums)-1)

class Solution:
  # 调整为大顶堆
  def heapify(self, arr: List[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[rignt] > arr[max_index]:
        max_index = right
      if max_index == index:
        # 如果不用交换，则说明已经交换结束
        break
      arr[index], arr[max_index] == arr[max_index], arr[index]
      # 继续调整子树
      index = max_index
      left = index * 2 + 1
      right = left + 1
   
  def buildMaxHeap(self, arr: List[int]):
    # 初始化大顶堆
    size = len(arr)  # (size-2)//2 是最后一个非叶节点，叶节点不用调整
    for i in range((size-2), i, size-1):
      self.heapify(arr, i, size-1)
    return arr
  
  # 生序堆排序，思路如下：
  # 1.先建立大顶堆
  # 2.让大顶堆最大元素与最后一个交换，然后调整第一个元素和倒数第二个元素，这一步获取最大值
  # 3.再交换堆顶元素与倒数第二个元素，然后调整第一个元素和倒数第三个元素，这一步获取第二大值
  # 4.以此类推，直到最后一个元素交换之后结束
  def maxHeapSort(self, arr: List[int]):
    self.buildMaxHeap(arr)
    size = len(arr)
    for i in range(size):
      arr[0], arr[size-i-1] = arr[size-i-1], arr[0]  # 第一个元素与后面的元素进行交换
      self.heapify(arr, 0, size-i-2)  # 重新调整
    return arr
  
  def sortArray(self, nums: List[int]) -> List[int]:
    return self.maxHeapSort(nums)

class Solution:
  def countingSort(self, arr):
    arr_min, arr_max = min(arr), max(arr)
    size = arr_max - arr_min
    counts = [0 for _ in range(size)]
    
    for num in arr:
      counts[num-arr_min] += 1
    for j in range(1, size):
      counts[j] += counts[j-1]   
    
    res = [0 for _ in range(len(arr))]
    for i in range(len(arr)-1, -1, -1):
      res[counts[arr[i]-arr_min]-1] = arr[i]
      counts[arr[i]-arr_min] -= 1
    return res
 
 def sortArray(self, nums: List[int]) -> List[int]:
    return self.countingSort(nums)

class Solution:
  def insertionSort(self, arr):
    for i in range(1, len(arr)):
      tmp = arr[i]
      j = i
      while j>0 and arr[j-1] > tmp:
        arr[j] = arr[j-1]
        j -= 1
      arr[j] = tmp
    return arr
  
  def bucketSort(self, arr, bucket_size=5):
    arr_min, arr_max = min(arr), max(arr)
    bucket_count = (arr_max-arr_min)//bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]
    
    for num in arr:
      buckets[(num-min_arr)//bucket_size].append(num)
    
    res = []
    for bucket in buckets:
      self.insertionSort(bucket)
      res.extend(bucket)
    return res
 
 def sortArray(self, nums: List[int]) -> List[int]:
    return self.bucketSort(nums)

class Solution:
  def radixSort(self, arr):
    size = len(str(max(arr)))
    
    for i in range(size):
      buckets = [[] for _ in range(10)]
      for num in arr:
        buckets[num//(10**i)%10].append(num)
      arr.clear()
      for bucket in buckets:
        for num in bucket:
          arr.append(num)
    return arr
  
  def sortArray(self, nums: List[int]) -> List[int]:
    return self.radixSort(nums)

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        
        index1 = m - 1
        index2 = n - 1
        index = m + n - 1
        while index1 >= 0 or index2 >=0:
            if nums1[index1] < nums2[index2]:
                nums1[index] = nums2[index2]
                index2 -= 1
            else:
                nums1[index] = nums1[index1]
                index1 -= 1
            index -= 1
        # nums2 still have elements
        nums1[:index2+1] = nums2[:index2+1]
        return nums1

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int index1 = m - 1;
        int index2 = n - 1;
        int index = m + n - 1;
        while(index1 >= 0 && index2 >= 0)
        {
            if (nums1[index1] < nums2[index2])
            {
                nums1[index] = nums2[index2];
                index2--;
            }
            else
            {
                nums1[index] = nums1[index1];
                index1--;
            }
            index--;
        }
        
        if(index1==-1 && index2 != -1)  // 如果nums2还有元素没有被遍历，继续遍历和赋值
        {
            while(index2 != -1)
            {
                nums1[index] = nums2[index2];
                index--;
                index2--;
            }
        }
        /*  这部分好像不需要
        if(index1 != -1 && index2 == -1)
        {
            while(index1 != -1)
            {
                nums1[index] = nums1[index1];
                index--;
                index1--;
            }
        }
        */ 
    }
};

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

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

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.merge_sort(nums)
    
    def merge_sort(self, nums):
        size = len(nums)
        if size < 2:
            return nums
        mid = size // 2
        left_nums, right_nums = nums[0:mid], nums[mid:]
        return self.merge(self.merge_sort(left_nums), self.merge_sort(right_nums))  # 递归到一个元素，再合并
    
    def merge(self, left_nums, right_nums):
        nums = []
        while left_nums and right_nums:
            if left_nums[0] <= right_nums[0]:
                nums.append(left_nums.pop(0))
            else:
                nums.append(right_nums.pop(0))
        nums += left_nums if left_nums else right_nums
        return nums

class Solution {
public:
    void merge(vector<int> &nums, int front, int mid, int end)
    {
        vector<int> left_nums(nums.begin()+front, nums.begin()+mid+1);
        vector<int> right_nums(nums.begin()+mid+1, nums.begin()+end+1);
        int idx_left = 0;
        int idx_right = 0;
        //left_nums.insert(left_nums.end(), numeric_limits<int>::max());
        //right_nums.insert(right_nums.end(), numeric_limits<int>::max());
        for(int i=front; i<= end; i++)
        {
            if(left_nums[idx_left] < right_nums[idx_right])
            {
                nums[i] = left_nums[idx_left];
                idx_left++;
            }
            else
            {
                nums[i] = right_nums[idx_right];
                idx_right++;
            }
        }
    }
    
    void merge_sort(vector<int> &nums, int front, int end)
    {
        if(front >= end)
        {
            return;
        }
        int mid = (front+end) / 2;
        merge_sort(nums, front, mid);
        merge_sort(nums, mid+1, end);
        merge(nums, front, mid, end);
    }
    
    vector<int> sortArray(vector<int>& nums) {
        merge_sort(nums, 0, nums.size());
        return nums;
    }
};

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        
        i, j, pos = 0, n-1, n-1
        while i <= j:
            if nums[i] * nums[i] > nums[j] * nums[j]:
                ans[pos] = nums[i] * nums[i]
                i += 1
            else:
                ans[pos] = nums[j] * nums[j]
                j -= 1
            pos -= 1
        return ans

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        
        int i = 0;
        int j = n-1;
        int pos = n-1;
        vector<int> res(n);
        while(i <= j)
        {
            if(nums[i] * nums[i] > nums[j] * nums[j])
            {
                res[pos] = nums[i] * nums[i];
                ++i;
            }
            else
            {
                res[pos] = nums[j] * nums[j];
                --j;
            }
            pos--;
        }
        
        return res;
    }
};

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44] 

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        element_nums = [0] * 1001
        for num in arr1:
            element_nums[num] += 1
        
        res = []
        for num in arr2:
            while element_nums[num]:
                res.append(num)
                element_nums[num] -= 1
        
        for index in range(1001):
            while element_nums[index]:
                res.append(index)
                element_nums[index] -= 1
        return res

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
            vector<int> cnt(1001);  // 统计频次
            int n1 = arr1.size();
            int n2 = arr2.size();
            // 统计arr1中每个数字出现的次数
            for(int a1: arr1)
            {
                cnt[a1]++;
            }
            
            // 将arr2中的每个数字重复放入arr1中
            int i = 0;
            for(int a2: arr2)
            {
                while(cnt[a2] > 0)
                {
                    arr1[i] = a2;
                    i++;
                    cnt[a2]--;
                }
            }
            
            // 剩下的依次放入即可
            for(int j=0; j<cnt.size(); j++)
            {
                while(cnt[j] > 0)
                {
                    arr1[i] = j;
                    i++;
                    cnt[j]--;
                }
            }
        return arr1;
    }
};

输入: head = [4,2,1,3]
输出: [1,2,3,4]

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head:
            return head;
        dummyHead = ListNode(0)
        dummyHead.next = head
        lastSorted = head
        curr = head.next
        while curr:
            if lastSorted.val <= curr.val:
                lastSorted = lastSorted.next
            else:
                prev = dummyHead
                while prev.next.val <= curr.val:
                    prev = prev.next
                lastSorted.next = curr.next
                curr.next = prev.next
                prev.next = curr
            curr = lastSorted.next
        
        return dummyHead.next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(head == nullptr)
        {
            return head;
        }
        
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* lastSorted = head;
        ListNode* curr = head->next;
        while(curr != nullptr)
        {
            if(lastSorted->val <= curr->val)
            {
                lastSorted = lastSorted->next;
            }
            else
            {
                ListNode* prev = dummyHead;
                while(prev->next->val <= curr->val)
                {
                    prev = prev->next;
                }
                lastSorted->next = curr->next;
                curr->next = prev->next;
                prev->next = curr;
            }
            curr = lastSorted->next;
        }
        return dummyHead->next;
    }
};