class Solution(object):
    def smallestK(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: List[int]
        """
        self.quick_sort(arr, 0, len(arr) - 1)
        print(arr)

    def quick_sort1(self, arr, start, end):
        """快排1"""
        if start >= end: return
        left, right = start, end
        temp = arr[left]
        while left < right:
            while left < right and arr[right] >= temp:
                right -= 1
            arr[left] = arr[right]

            while left < right and arr[left] <= temp:
                left += 1
            arr[right] = arr[left]

        arr[left] = temp
        self.quick_sort(arr, start, left-1)
        self.quick_sort(arr, left+1, end)

    def quick_sort(self, arr, start, end):
        """快排2: 对应图"""
        if start >= end: return
        left, right = start, end
        temp = arr[left]
        while left < right:
            while left < right and arr[right] >= temp:
                right -= 1
            while left < right and arr[left] <= temp:
                left += 1
            arr[right], arr[left] = arr[left], arr[right]

        arr[start], arr[left] = arr[left], temp
        self.quick_sort(arr, start, left-1)
        self.quick_sort(arr, left+1, end)


s1 = Solution()
arr = [1,3,5,7,2,4,6,8,1]; k = 4
root = s1.smallestK(arr, k)
print(root)