設(shè)計一個平均時間為O(n)的算法，在n(1<=n<=1000)個無序的整數(shù)中找出第k小的數(shù)。

提示：函數(shù)int partition(int a[],int left,int right)的功能是根據(jù)a[left]a[right]中的某個元素x(如a[left])對a[left]a[right]進(jìn)行劃分，劃分后的x所在位置的左段全小于等于x,右段全大于等于x,同時利用x所在的位置還可以計算出x是這批數(shù)據(jù)按升非降序排列的第幾個數(shù)。因此可以編制int find(int a[],int left,int right,int k)函數(shù)，通過調(diào)用partition函數(shù)獲得劃分點，判斷劃分點是否第k小，若不是，遞歸調(diào)用find函數(shù)繼續(xù)在左段或右段查找。

輸入格式:

輸入有兩行：

第一行是n和k，0

第二行是n個整數(shù)

輸出格式:

輸出第k小的數(shù)

輸入樣例:

在這里給出一組輸入。例如：

10 4

2 8 9 0 1 3 6 7 8 2

輸出樣例:

在這里給出相應(yīng)的輸出。例如：

2

代碼：

#include

using namespace std;

int partition(int a[],int left,int right){

int i = left+1,j = right;

int x = a[left];

while(i<=j){

while(a[i] <= x && i < right) i++;

while(a[j] > x) j--;

if(i >= j) break;

int m;

m = a[j];

a[j] = a[i];

a[i] = m;

}

a[left] = a[j];

a[j] = x;

return j;

}

int find(int a[], int left, int right, int k)

{

if (left == right)

return a[left];

int i = partition(a, left, right);

int j = i - left + 1;

if (k <= j)

return find(a, left, i-1, k);

else

return find(a, i + 1, right, k - j);

}

int main(){

int n,k;

cin>>n>>k;

int arr[10000];

for(int i=0;i

cin>>arr[i];

}

int q = find(arr,0,n,k);

cout<

return 0;

}

算法時間及空間復(fù)雜度分析：

最壞情況下的時間復(fù)雜度為O(n^2);

每次遞歸將問題分為兩個子問題，每個子問題中又有時間復(fù)雜度為O(n)的操作；

最好情況下，每次取得的基準(zhǔn)為中值，即劃分產(chǎn)生兩個大小為n/2的區(qū)域，有T(n)=2T(n/2)+O(n);

得到時間復(fù)雜度為O(nlogn);

最好情況下空間復(fù)雜度為O(logn)，遞歸調(diào)用最壞情況下調(diào)用n次，空間復(fù)雜度為O(n);

心得體會：

這次隊伍上機(jī)實驗，find函數(shù)其實并不復(fù)雜，只是在partition的基礎(chǔ)上進(jìn)行修改而已，但partition函數(shù)里的小細(xì)節(jié)，即大于小于符號，判斷數(shù)字是否超出界限等需要注意。

總結(jié)

以上是生活随笔為你收集整理的python第二章上机实践_第二章上机实践报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。