寻找第k小的元素快速排序代码

快速排序是一种高效的排序算法，但它本身并不直接提供查找第k小元素的功能。不过我们可以结合快速排序的思想和其他数据结构如堆或二分查找来实现这个功能。这里提供一种基于随机化快速选择（Quickselect）的简化版本，它可以在平均时间复杂度O(n)内找到数组中的第k小元素。
import random

def quickselect(arr, k):
if len(arr) == 1:
return arr[0]

pivot = random.choice(arr)
lows = [el for el in arr if el < pivot]
highs = [el for el in arr if el > pivot]
pivots = [el for el in arr if el == pivot]

if k < len(lows):
return quickselect(lows, k)
elif k < len(lows) + len(pivots):
return pivots[0]
else:
return quickselect(highs, k - len(lows) - len(pivots))

# 示例
arr = [3,6,8,10,1,2,1]
k = 3
print(f"第{k}小的元素是: {quickselect(arr, k)}")
登录后复制

相关问题

寻找第k小的元素快速排序C++代码

快速排序是一种高效的排序算法，但它的原版实现并不是稳定的，并且在最坏的情况下时间复杂度会退化到O(n^2)。如果你需要在快速排序中寻找第k小的元素，可以采用一种改进版本——“三向切分”的思想，也称为“快速选择”算法。
以下是一个简单的C++代码示例，使用了三向切分法：
#include <vector>
using namespace std;

int partition(vector<int>&amp; nums, int low, int high, int&amp; kth)
{
int pivot = nums[low];
int small = low, equal = low + 1, large = high;

while (equal <= large)
{
if (nums[equal] < pivot)
swap(nums[small++], nums[equal++]);
else if (nums[equal] == pivot)
equal++;
else // nums[equal] > pivot
swap(nums[equal], nums[large--]);
}

if (kth == small)
return equal; // 找到了第k小的元素
else if (kth < small)
return partition(nums, low, small - 1, kth);
else // kth > small
return partition(nums, large + 1, high, kth - small - 1);
}

int quickSelectKth(vector<int>&amp; nums, int k)
{
int n = nums.size();
return partition(nums, 0, n - 1, k - 1);
}

// 示例用法
int main()
{
vector<int> nums = {9, 7, 5, 11, 12, 2, 14, 3, 10};
int k = 3;
int kthElement = quickSelectKth(nums, k);
cout << "第" << k << "小的元素是: " << nums[kthElement] << endl;
return 0;
}
登录后复制

快速排序法寻找n个整数中第k小的元素C语言完整代码

以下是使用快速排序法寻找 n 个整数中第 k 小的元素的完整 C 语言代码：
#include <stdio.h>

void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(&amp;arr[i], &amp;arr[j]);
}
}
swap(&amp;arr[i + 1], &amp;arr[high]);
return i + 1;
}

int kthSmallest(int arr[], int low, int high, int k) {
int partitionIndex = partition(arr, low, high);
if (partitionIndex == k - 1) {
return arr[partitionIndex];
} else if (partitionIndex < k - 1) {
return kthSmallest(arr, partitionIndex + 1, high, k);
} else {
return kthSmallest(arr, low, partitionIndex - 1, k);
}
}

int main() {
int n, k;
printf("Enter the value of n and k: ");
scanf("%d %d", &amp;n, &amp;k);
int arr[n];
printf("Enter the array elements:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &amp;arr[i]);
}
int result = kthSmallest(arr, 0, n - 1, k);
printf("The %dth smallest element is %d\n", k, result);
return 0;
}
登录后复制
在上面的代码中，swap() 函数用于交换两个整数的值，partition() 函数用于对数组进行划分（选择最后一个元素作为基准值），kthSmallest() 函数用于递归查找第 k 小的元素。
在 main() 函数中，先读取输入的 n 和 k，然后读取数组元素，最后调用 kthSmallest() 函数查找第 k 小的元素，并输出结果。