# -*- coding:utf-8 -*-

import random


def quick_sort(array):
    """快速排序 分冶法"""
    if len(array) < 2:
        return array
    else:
        mid_value = array[0]  #
        less_array = [i for i in array[1:] if i < mid_value]
        great_array = [i for i in array[1:] if i >= mid_value]
        new_array = quick_sort(less_array) + [mid_value] + quick_sort(great_array)
        return new_array


def test_quick_sort():
    q = list(range(10))
    q.append(5)
    random.shuffle(q)
    sorted_q = sorted(q)
    assert quick_sort(q) == sorted_q


#############################################
# 快速排序 第二种方法
#############################################

def quick_sort2(array, begin, end):
    if end > begin:
        pivod = partition(array, begin, end)
        quick_sort2(array, begin, pivod - 1)
        quick_sort2(array, pivod + 1, end)
    return array


def partition(array, begin, end):  # begin:数组开始下标 数组结束下标
    pivod_index = begin
    pivod = array[pivod_index]
    left = pivod_index + 1  # 数组开始下标后一个起
    right = end
    while True:
        while left <= right and array[left] < pivod:
            left += 1
        while left <= right and array[right] >= pivod:
            right -= 1
        if left > right:
            break
        array[left], array[right] = array[right], array[left]
    array[pivod_index], array[right] = array[right], array[pivod_index]
    return right


def test_quick_sort2():
    a = list(range(10))
    random.shuffle(a)
    print(a)
    sorted_a = sorted(a)
    new_a = quick_sort2(a, 0, len(a) - 1)
    print(new_a)
    assert new_a == sorted_a


#############################################
# 无序数组中 寻找第K大的元素
#############################################


def find_k_value(array, begin, end, k):
    index = partition(array, begin, end)
    if len(array[index:]) == k:
        return array[index]
    elif len(array[index:]) > k:
        return find_k_value(array, index + 1, end, k)
    else:
        return find_k_value(array, begin, index, k)


def test_find_k_value():
    a = list(range(10))
    random.shuffle(a)
    print(a)
    k_value = find_k_value(a, 0, len(a) - 1, 10)
    print(k_value)
    assert k_value == 0