数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用数组划分法查找数组中第 k 个最小元素的 C++ 程序\n
我们将开发一个 C++ 程序，使用数组划分法来查找第 k 个最小元素。
算法
Begin Function CreatePartition() has an array a, and the lower l and upper limit h as arguments in := l and pi := h for i in range l to h, do if a[i] < a[pi], then exchange the values of a[i] and a[in] increase the in by 1 done exchange the values of a[pi] and a[in] return in End Begin Function Partition(): Arguments: An array A, and the lower and upper limit low and high, and also k. Body of the function: if low < high, then p_in := Create_Partition(A, low, high) if p_in = k-1, then return k-1 else if p_in > k-1 Partition (A, low, p_in – 1, k) else Partition (A, p_in + 1, high, k) End
示例代码
#include<iostream>
using namespace std;
void swap(int *a, int *b) {
int t;
t = *a;
*a = *b;
*b = t;
}
int CreatePartition(int a[], int l, int h) {
int pi, in, i;
in = l;
pi = h;
for(i=l; i < h; i++) {
if(a[i] < a[pi]) {
swap(&a[i], &a[in]);
in++;
}
}
swap(&a[pi], &a[in]);
return in;
}
int Partition(int a[], int low, int high, int k) {
int p_in;
if(low < high) {
p_in = CreatePartition(a, low, high);
if(p_in == k-1)
return k-1;
else if(p_in > k-1)
Partition(a, low, p_in-1, k);
else
Partition(a, p_in+1, high, k);
}
}
int main() {
int n, i, k, k_k;
cout<<"\nEnter the number array elements: ";
cin>>n;
int a[n];
for(i = 0; i < n; i++) {
cout<<"Enter element "<<i+1<<": ";
cin>>a[i];
}
cout<<"\nEnter the k for the kth smallest element: ";
cin>>k;
k_k = Partition(a, 0, n-1, k);
cout<<"\nThe kth smallest element: "<<a[k_k];
return 0;
}输出
Enter the number array elements: 4 Enter element 1: 3 Enter element 2: 2 Enter element 3: 5 Enter element 4: 4 Enter the k for the kth smallest element: 3 The kth smallest element: 4
更新于： 2019 年 7 月 30 日
239 次查看
广告