西北工业大学noj大作业排序算法

### 西北工业大学 NOJ 平台排序算法大作业示例题目解题报告

#### 示例题目：优化版快速排序实现

在西北工业大学 NOJ 平台上，有一道关于优化版快速排序的大作业题目。该题目不仅要求学生掌握基本的快速排序原理，还强调了对不同数据分布情况下的性能优化。

#### 题目描述
给定一组整数数组 `arr` 和一个正整数 `k` (1 ≤ k ≤ length of array)，编写程序找到前 K 小的元素并按升序返回这些元素组成的列表。为了提高效率，不允许使用额外的空间来存储中间结果（即空间复杂度应尽可能低）。此外，在最坏情况下时间复杂度不应超过 O(n log n)[^1]。

#### 思路分析
此问题可以通过修改传统的快速排序算法解决。传统方法会构建完整的有序序列再截取所需部分；而本题只需要获取特定位置上的若干个最小值，则可以利用分治法的思想只处理涉及目标范围内的子区间，从而减少不必要的比较次数达到加速效果。

#### Python 实现代码

import random

def partition(nums, low, high):
    pivot = nums[(low + high) // 2]
    i = low - 1
    j = high + 1
    
    while True:
        i += 1
        while nums[i] < pivot:
            i += 1
        
        j -= 1
        while nums[j] > pivot:
            j -= 1
            
        if i >= j:
            return j
        
        nums[i], nums[j] = nums[j], nums[i]

def quick_select(nums, left, right, index):
    pos = partition(nums, left, right)

    if pos + 1 == index:
        return nums[pos]
    elif pos + 1 < index:
        return quick_select(nums, pos + 1, right, index)
    else:
        return quick_select(nums, left, pos - 1, index)

def smallestK(arr, k):
    if not arr or k <= 0:
        return []
    
    result = []
    for _ in range(k):
        min_val = quick_select(arr[:], 0, len(arr)-1-_ ,len(arr)-_)
        arr.remove(min_val)
        result.append(min_val)
        
    return sorted(result)

# 测试用例
print(smallestK([7, 10, 4, 3, 20, 15], 3))  

上述解决方案通过调整标准快排逻辑实现了更高效的 top-k 查询功能，并且满足题目对于时间和空间复杂性的严格限制条件。