215. Kth Largest Element in an A

1. 冒泡排序
   两两比较，把最大的放在最后，然后次大的放倒数第二，依次执行。。。

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        for i in range(len(nums)):
            for j in range(len(nums) - i - 1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
        return nums[len(nums) - k]

2.选择排序
从list中比较所有的选择最大的和最后一个元素交换，重复此动作。

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        for i in range(k):
            temp = 0
            for j in range(len(nums)-i):
                if nums[j] > nums[temp]:
                    temp = j
            nums[temp], nums[len(nums)-i-1] = nums[len(nums)-i-1], nums[temp]
        return nums[len(nums)-k]

3. 快速排序
   每次选最右边为pivot，小于pivot放在左侧，大于pivot的放在右侧，如果k在左边就继续排左边，要不然就不管左边，继续排右边。

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return self.findKthSmallest(nums, len(nums)+1-k)
    
    def findKthSmallest(self, nums, k):
        # if len(nums) == 1:
        #     return nums[0]
        
        pivot = self.partition(nums, 0, len(nums) - 1)
        
        if k > pivot + 1:
            return self.findKthSmallest(nums[pivot+1:], k-pivot-1)
        elif k < pivot + 1:
            return self.findKthSmallest(nums[:pivot], k)
        else:
            return nums[pivot]
    def partition(self, nums, l, r):
        pos = l
        while l < r:
            if nums[l] < nums[r]:
                nums[l], nums[pos] = nums[pos], nums[l]
                pos += 1
            l += 1
        nums[pos], nums[r] = nums[r], nums[pos]
        return pos