C ++程序通过数组分割方法找到第k个最小元素
我们将开发一个C++程序，通过分割Array的方法找到第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