Class Solution

Array/KthLargestElementInAnArray.py:44–132

"""
class Solution(object):

    def quickSort(self, unsorted_list):
        """
            每次都选一个基准点，大的放在右边，小的放在左边，等于的随便归到一个地方，不断拆分拆分。
            这里直接选用[0]，当然这种情况下往往会发生不理想的情况，
            不理想的情况表示每次恰好都是最小或最大，这样的结果会直接导致算法变为O(n^2).
        """

        if len(unsorted_list) <= 1:
            return unsorted_list

        left = []
        right = []

        meta = self._getMiddle(unsorted_list)
        for i in unsorted_list[:meta] + unsorted_list[meta+1:]:
            if i <= unsorted_list[meta]:
                left.append(i)
                continue
            right.append(i)

        return self.quickSort(left) + [unsorted_list[meta]] + self.quickSort(right)

    def _getMiddle(self, unsorted_list):
        """
            返回快排所需的基准点，
            左右中中间选择一个。
            若不足3位，选左。
        """
        if len(unsorted_list) < 3:
            return 0

        left = unsorted_list[0]
        right = unsorted_list[-1]
        middle = unsorted_list[len(unsorted_list) // 2]
        l, r, m = [(0, left), (len(unsorted_list) - 1, right), (len(unsorted_list) // 2, middle)]
        # 这里对比了自己写的merge sort 与内置的差距，
        # 在有key的情况下差距非常大。
        return sorted([l, r, m], key=lambda x: x[1])[1][0]


    def mergeSort(self, unsorted_list, key=None):
        """
            归并排序的基本思路是分治，把一个大问题分解成小问题。逐个解决小问题。
            以长度的一半为基准点，将一个大列表分为两个小列表，一直分一直分，然后合并。
            所以排序分为两步：
               第一步是分解，第二步是合并。
        """
        if len(unsorted_list) <= 1:
            return unsorted_list

        break_point = len(unsorted_list) // 2

        left = self.mergeSort(unsorted_list[:break_point])
        right = self.mergeSort(unsorted_list[break_point:])

        return self._decomposeAndMerge(left, right, key=key)