- 冒泡排序
两两比较，把最大的放在最后，然后次大的放倒数第二，依次执行。。。
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]
- 快速排序
每次选最右边为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
