运行超时，怎么改进
求 n 个整数中第 k(1≤k≤n) 大的整数。输入格式
n 和 k
n 个整数
输出格式
第 k 大的整数
#include <stdio.h>
#include <stdlib.h>
int main()
{
long long N,K,i;
scanf("%lld",&N); //输入数的个数
int a;
scanf("%lld",&K); //确定一个第K大的数
for(i=0;i<N;i++){
scanf("%lld",&a);
} //为数组输入变量
int temp,j,m;
for(j=0;j<N-1;j++){
for(m=0;m<N-1-j;m++){
if(a<a){
temp=a;
a=a;
a=temp;
}
}
} //降序冒泡排序
printf("%lld",a); //输出第K大的数
return 0;
} 你的代码使用了冒泡排序算法，当处理大量数据时，可能导致运行超时。可以考虑使用更高效的排序算法，如快速排序（Quick Sort）或堆排序（Heap Sort）
你也可以尝试使用快速选择算法（Quick Select）来提高程序效率。快速选择算法是在快速排序算法的基础上修改而来的，用于在未排序的序列中查找第 k 大的元素，其平均时间复杂度为 O(n)。
以下是使用 C 语言实现的快速选择算法示例：
#include <stdio.h>
#include <stdlib.h>
int partition(int arr[], int low, int high) {
int pivot = arr;
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr > pivot) {
i++;
int temp = arr;
arr = arr;
arr = temp;
}
}
int temp = arr;
arr = arr;
arr = temp;
return i + 1;
}
int quick_select(int arr[], int low, int high, int K) {
if (low == high) {
return arr;
}
int pivot_index = partition(arr, low, high);
if (K == pivot_index) {
return arr;
} else if (K < pivot_index) {
return quick_select(arr, low, pivot_index - 1, K);
} else {
return quick_select(arr, pivot_index + 1, high, K);
}
}
int main() {
long long N, K, i;
scanf("%lld", &N);
int a;
scanf("%lld", &K);
for (i = 0; i < N; i++) {
scanf("%d", &a);
}
int result = quick_select(a, 0, N - 1, K - 1);
printf("%d\n", result);
return 0;
}
这段代码使用了快速选择算法来查找数组中第 K 大的数。这种方法的性能会优于冒泡排序，尤其是在处理大量数据时。
页:
[1]