整数排序 II - quick_sort and merge_sort

https://www.lintcode.com/problem/464/?utm_source=sc-cheatsheet-cyc

描述

给一组整数，请将其在原地按照升序排序。使用归并排序，快速排序，堆排序或者任何其他 O(n log n) 的排序算法。

样例

例1：

输入：[3,2,1,4,5]，输出：[1,2,3,4,5]。

例2：

输入：[2,3,1]，输出：[1,2,3]。

为了对输入的数组进行排序，我们可以使用一个常见的排序算法——快速排序（Quick Sort）。以下是实现此算法的步骤：

1. 确定一个基准点（pivot），可以选择数组的第一个元素。

2. 将数组分成两个子数组，一个包含所有小于基准点的元素，另一个包含所有大于基准点的元素。

3. 对这两个子数组递归地应用上述步骤。

4. 最终将所有子数组合并起来得到排序后的数组。

```python
from typing import (
    List,
)

class Solution:
    """
    @param a: an integer array
    @return: nothing
    """
    def sort_integers2(self, a: List[int]):
        # write your code here
        self.quick_partition(a, 0, len(a)-1) #err: len(a)
    
    def quick_partition(self, a: List[int], start:int, end:int):
        if start >= end: # start > end也可以
            return
        pivot = a[(start + end) // 2]
        left, right = start, end
        while left <= right:
            while left <= right and a[left] < pivot: #err: a[left] <= pivot 有大小才有必要换，等于没必要
                left += 1
            while left <= right and a[right] > pivot: #error: a[right] >= pivot
                right -= 1
            if left <= right:
                a[left], a[right] = a[right], a[left]
                left += 1 #err: missing 不要忘了这个
                right -= 1 #err: missing
        self.quick_partition(a, start, right)
        self.quick_partition(a, left, end)
```

```python
from typing import (
    List,
)

class Solution:
    """
    @param a: an integer array
    @return: nothing
    """
    def sort_integers2(self, a: List[int]):
        # write your code here
        if not a:
            return
        temp = [0] * len(a) #Missing 因为需要合并，一定要有这个Helper array 
        self.merge_sort(a, 0, len(a) - 1, temp)
           
    def merge_sort(self, a:List[int], start: int, end: int, temp: List[int]):
        if start >= end: #递归一定要有程序出口，必须是>= 不能是> ，至少2个数才需要合并
            return 
        mid = (start + end) // 2
        self.merge_sort(a, start, mid, temp)
        self.merge_sort(a, mid + 1, end, temp)
        self.merge(a, start, end, temp)
    
    def merge(self, a:List[int], start: int, end: int, temp: List[int]):
        mid = (start + end) // 2
        left, right = start, mid + 1
        cur = start #ERROR!不能从0开始！！！！！！
        while left <= mid or right <= end:
            if left == mid + 1 and right <= end:
                temp[cur] = a[right]
                right += 1
            elif right == end + 1 and left <= mid:
                temp[cur] = a[left]
                left += 1
            elif a[left] > a[right]:
                temp[cur] = a[right]
                right += 1
            else:
                temp[cur] = a[left]
                left += 1
            cur += 1
        for i in range(start, end+1):
            a[i] = temp[i]


```