把一个list里面的数字排序，找出第K大的数字
主要考察排序算法，这里使用快排会比较快
但是用python自带的sort才是最快的，查了资料，使用的是Timsort，链接如下：
https://en.wikipedia.org/wiki/Timsort
import random class Solution(object): def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ self.b=nums def partion(a,l,r): if l<r: i=l j=r x=a[l] while i<j: while i<j and a[j]>=x: j-=1 if i<j: a[i]=a[j] i+=1 while i<j and a[i]<x: i+=1 if i<j: a[j]=a[i] j-=1 a[i]=x partion(a,l,i-1) partion(a,i+1,r) return random.shuffle(self.b) partion(self.b,0,len(nums)-1) return self.b[len(nums)-k]
这里最难的部分是使用切分函数来划分数组分割，这里有一个很好的博客：https://blog.csdn.net/morewindows/article/details/6684558
采用挖坑+填数的想法，比较好理解
先选择一个分支点，把分支点数字保存起来，
从右边开始，找一个小于这个分支点的数字，并把这个数字填在分支点。（这是右边这个数字的位置就是一个坑，可以被填）
在把左边找起，找一个大于分支点数值的数字，把这个数字填到右边
这样不断的右边，左边的挖坑填数，直到i=j,这个时候把保存的数值填到这个i位置。
这个时候，这个i位置左边的数字都小于分支点，右边的数字都大于这个分支点的数
后面在依次对左边和右边进行划分就可以了
http://drops.dagstuhl.de/opus/volltexte/2018/9467/pdf/LIPIcs-ESA-2018-4.pdf
class Solution(object): def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ nums.sort(reverse=True) return nums[k-1]
1.python里面的函数是真的厉害，很想学习一下，但是时间不足，后面再刷的时候，我一定会好好看一下
215. Kth Largest Element in an Array
原文：https://www.cnblogs.com/captain-dl/p/10810087.html