题解 | #寻找第K大# quicksort 优化

# -*- coding:utf-8 -*-
def swap(arr, idx1, idx2):
    t = arr[idx1]
    arr[idx1] = arr[idx2]
    arr[idx2] = t


def findMedian(arr, left, right):
    center = int((left + right) / 2)
    if arr[left] < arr[center]: swap(arr, left, center)
    if arr[left] < arr[right]: swap(arr, left, right)
    if arr[center] < arr[right]: swap(arr, center, right)
    return center


def QSort(arr, left, right,k):
    center = findMedian(arr, left, right)
    swap(arr, center, right)
    pivot = arr[right]
    i, j = 0, right
    while i < j:
        while arr[i] > pivot and i<j: i += 1
        arr[j] = arr[i];
        if i<j: j-=1
        while arr[j] < pivot and i<j: j -= 1
        arr[i] = arr[j];
        if i<j: i += 1
    arr[i] = pivot
    if i>k:
        if left < i - 1: QSort(arr, left, i - 1,k)
    if i<k:
        if i + 1 < right: QSort(arr, i + 1, right,k)

def quickSort(arr,k):
    left, right = 0, len(arr) - 1
    QSort(arr, left, right,k)
class Solution:
    def findKth(self, a, n, K):
        # write code here
        quickSort(a,K-1)
        return a[K-1]