Swift.最小的K个数

题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

import Foundation

class For30Solution {
    func topK(_ n: [Int],_ minK: Int) -> [Int] {
        
        if n.count == 0 || minK == 0 {
            return []
        }
        
        var nums = n
        var start = 0
        var end = n.count - 1
        var index = partition(&nums, start, end)
        while index != minK - 1 {
            if index > minK - 1 {
                end = index - 1
                index = partition(&nums, start, end)
            }
            
            if index < minK - 1 {
                start = index + 1
                index = partition(&nums, start, end)
            }
        }
        
        return Array(nums[0..<minK])
    }
    
    
    //快排partition
    func partition(_ n: inout [Int],_ leftIn: Int,_ rightIn: Int ) -> Int {
        let temp = n[leftIn]
        var left = leftIn
        var right = rightIn
        
        while left < right {
            while left < right && n[right] >= temp {
                right -= 1
            }
            n[left] = n[right]
            
            while left < right && n[left] <= temp {
                left += 1
            }
            n[right] = n[left]
        }
        
        n[left] = temp
        
        return left
    }
}

算法思想：利用快速排序划分的思想，每一次划分就会有一个数字位于以数组从小到达排列的的最终位置index；最后index=K就完成了。

github地址：https://github.com/cubegao/LeetCode