Quick Sort & Merge Sort

Merge Sort & Quick Sort，这两个排序算法都是利用Divide & Conquer最经典的例子。Merge Sort是先局部有序再整体有序，而Quick Sort是先整体有序再局部有序。由于Merge Sort需要一个拷贝数组的过程，所以速度不及Quick Sort。但两种排序算法中的思想都是非常重要的，在很多题中都会用到，所以在此提及。
Merge Sort: 由于是先局部有序再整体有序，所以要先调用两次mergeSort()之后再调用merge()将已排序的两个子数组合并。还需要注意需要一个辅助数组aux[]以及在merge时，对一个数组已经结束时的处理。
Quick Sort: 由于是先整体有序再局部有序，所以要先调用partision()根据pivot将原数组化为两个字数组，在调用两次quickSort()对子数组进行排序。我们默认left指针所对应的元素即为pivot元素，注意下标的处理。

Merge Sort代码如下：

class Solution:
    """
    @param A: an integer array
    @return: nothing
    """
    def sortIntegers2(self, A):
        aux = self.mergeSort(A)
        for i in range(len(A)):
            A[i] = aux[i]

    def mergeSort(self, A):
        result = []
        if len(A) < 2:
            return A
        mid = int(len(A) / 2)
        left = self.mergeSort(A[:mid])
        right = self.mergeSort(A[mid:])
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result += left[i:]
        result += right[j:]
        return result

Quick Sort代码如下：

class Solution:
    """
    @param A: an integer array
    @return: nothing
    """
    def sortIntegers2(self, A):
        self.quickSort(A, 0, len(A) - 1)

    def quickSort(self, A, left, right):
        if left >= right:
            return
        low = left
        high = right
        key = A[low]
        while left < right:
            while left < right and A[right] > key:
                right -= 1
            while left < right and A[left] <= key:
                left += 1
            A[left], A[right] = A[right], A[left]
        A[right], A[low] = A[low], A[right]
        self.quickSort(A, low, left - 1)
        self.quickSort(A, left + 1, high)