快速排序算法实现与优化

"快速排序算法实现，包括标准版本和按指定位置排序的版本。" 快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是采用分治策略，通过选取一个基准元素（pivot），将待排序的数组分为两个子数组，一个子数组的所有元素都小于或等于基准，另一个子数组的所有元素都大于基准。然后对这两个子数组递归地进行快速排序，直到所有元素都在正确的位置上。 在提供的代码中，快速排序算法的实现主要包含以下部分： 1. `partition` 函数：这是快速排序的核心，它接收一个整数数组、一个起始索引`low`和一个结束索引`high`。该函数首先选取数组中的第一个元素（即`arr[low]`）作为基准元素，然后通过两个指针`low`和`high`在数组中移动，将小于基准的元素移动到基准的左边，大于基准的元素移动到右边。当`low`和`high`相遇时，返回基准元素的新位置。 2. `sort` 函数：这是快速排序的递归部分，它调用`partition`函数来分割数组，然后对分割后的子数组分别进行递归调用，直至数组完全排序。 3. `sortNum` 函数：这个函数扩展了快速排序，除了排序整个数组外，还允许用户指定一个位置`seq`，使得排序后数组的第`seq`个位置的元素保持不变。它使用类似于`partition`的逻辑，但会根据基准元素的新位置与目标位置的关系，调整搜索范围。 4. `main` 函数：在主函数中，用户可以输入数组的大小`n`和一个特定位置`m`，程序首先对数组进行排序，然后输出第`m`个位置的元素，接着输出整个排序后的数组。如果输入的`n`和`m`满足条件（`n > 0`且`m < n`），则程序会继续运行，否则退出。 快速排序在平均情况下的时间复杂度为O(n log n)，最坏情况下（例如数组已经排序或逆序）为O(n^2)，但这种情况在实际应用中较少出现。空间复杂度为O(log n)至O(n)，取决于递归深度。由于快速排序在内部交换元素而不是创建新的数据结构，因此在空间效率上表现较好。此外，快速排序的性能在实践中通常优于其他O(n log n)的排序算法，如归并排序，因为它在大多数情况下具有较低的常数因子和更好的缓存效率。