【C++】基于快速排序的思想求解一堆数中第K大的值,时间复杂度为 O(n)
程序员文章站
2024-03-15 18:58:30
...
2018.03.20:根据实践过程,整理了第一版。
===============================
“求解一堆数中,第k大的值;要求时间复杂度为O(n)”。这是一道经典的编程题,在很多测试中遇到过。比如当年保送到厦大的复试也考了这一题。
本文主要基于快速排序的思想求解该问题,具体代码如下:
#include <iostream>
#include <fstream>
using namespace std;
#define MAXLENGTH 1000
int _array[MAXLENGTH] = {0};
int _len;
int K;
int result = 0;
void get_data(){
fstream in_data;
in_data.open("data.txt");
in_data >> _len;
in_data >> K;
for(int i = 0; i < _len; i++){
in_data >> _array[i];
}
}
void print_data(){
cout<<"_len = "<<_len<<"; K = "<<K<<endl;
for(int i = 0; i<_len; i++){
cout<<_array[i]<<" ";
}
cout<<endl;
}
// quick sort
int partition(int start, int end){
if(start > end){
return 0;
}
int temp_value;
int pivotkey_index = start;
int i = start;
int j = end;
while(i < j){
// move j
while(i<j&&_array[j] > _array[pivotkey_index]){
j--;
}
temp_value = _array[pivotkey_index];
_array[pivotkey_index] = _array[j];
_array[j] = temp_value;
pivotkey_index = j;
// move i
while(i<j&&_array[i] < _array[pivotkey_index]){
i++;
}
temp_value = _array[pivotkey_index];
_array[pivotkey_index] = _array[i];
_array[i] = temp_value;
pivotkey_index = i;
}
return pivotkey_index;
}
// find-top-k
void Q_sort(int start, int end){
// cout<<"call Q_sort function..."<<endl;
if(start < end){
int pivotkey_index = partition(start, end);
// cout<<"pivotkey_index = "<<pivotkey_index<<endl;
if(pivotkey_index+1 == K){
result = _array[pivotkey_index];
}else if(pivotkey_index+1 > K){
Q_sort(0, pivotkey_index-1);
}else{
Q_sort(pivotkey_index+1, end);
}
}
}
// quick sort end.
int main(){
get_data();
print_data();
Q_sort(0, _len-1);
cout<<"the "<<K<<"th number = "<<result<<endl;
return 0;
}
快速排序的代码如下所示:
#include <iostream>
#include <fstream>
using namespace std;
#define MAXLENGTH 1000
int _array[MAXLENGTH] = {0};
int _len;
int k = 5;
void get_data(){
fstream in_data;
in_data.open("data.txt");
in_data >> _len;
for(int i = 0; i < _len; i++){
in_data >> _array[i];
}
}
void print_data(){
for(int i = 0; i<_len; i++){
cout<<_array[i]<<" ";
}
cout<<endl;
}
// quick sort
int partition(int start, int end){
if(start > end){
return 0;
}
int temp_value;
int pivotkey_index = start;
int i = start;
int j = end;
while(i < j){
// move j
while(_array[j] > _array[pivotkey_index]){
j--;
}
temp_value = _array[pivotkey_index];
_array[pivotkey_index] = _array[j];
_array[j] = temp_value;
pivotkey_index = j;
// move i
while(_array[i] < _array[pivotkey_index]){
i++;
}
temp_value = _array[pivotkey_index];
_array[pivotkey_index] = _array[i];
_array[i] = temp_value;
pivotkey_index = i;
}
return pivotkey_index;
}
int Q_sort(int start, int end){
if(start < end){
int pivotkey_index = partition(start, end);
cout<<"pivotkey_index = "<<pivotkey_index<<endl;
Q_sort(0, pivotkey_index-1);
Q_sort(pivotkey_index+1, end);
}
return 0;
}
int quicksort(int start, int end){
int result = Q_sort(start, end);
return result;
}
// quick sort end.
int main(){
get_data();
cout<<"before sort..."<<endl;
print_data();
int result;
result = quicksort(0, _len-1);
cout<<"after sort..."<<endl;
print_data();
cout<<"result = "<<result<<endl;
return 0;
}
上一篇: n个整数的无序数组,找到每个元素后面比它大的第一个数
下一篇: 源点到所有顶点的最短路径