時常在筆試,面試題中看到這個問題,《算法導論》中給出了很好的解答。

Selection of the ith smallest element of the array A can be done in θ(n) times.

The psuedocode is following:

Code
Randomized_Select(A,p,r,i)
{
??? if p==r
??????? then return A[p]
??? q=Randomized_Partition(A,p,r)
??? k=q-p+1
??? if i==k
??????? then return A[q]
??? else if i<k
??????? then return Randomized_select(A,p,q-1,i)
??? else
??????? return Randomized_select(A,q+1,r,i-k)
}


=====================================
Randomized_Partition(A,p,r)
{
??? i=RANDOW(p,r)
??? exchange A[r] ? A[i]
??? return Partition(A,p,r)
}
=====================================
Partition(A,p,r)
{
??? x=A[r]
??? i=p-1
??? for j=p to r-1
??????? if A[j]<=x
????????????? then i=i+1
????????????????? exchange A[i]?A[j]
??? exchange A[i+1] ?A[r]
??? return i+1
}

?

Transfer to C# code:

?

Code
namespace SelectMinimum
{
class Program
{
static void Main(string[] args)
{
int[] A = new int[] {0,25,12,14,57,45,18,75,85,74,45,63,35,28,39 };
SelectSort ss = new SelectSort();
int result;
result=ss.Randomized_Select(A,0,14,11);
Console.WriteLine(result);
Console.ReadLine();
}


}

public class SelectSort
{
public int Randomized_Select(int[] A, int p, int r, int i)
{
if (p == r)
return A[p];
int q = Randomize_Partition(A, p, r);
int k = q - p + 1;
if (i == k)
return A[q];
else if (i < k)
return Randomized_Select(A, p, q - 1, i);
else
return Randomized_Select(A, q + 1, r, i - k);

}

public int Randomize_Partition(int[] A, int p, int r)
{
Random rd = new Random();
int i = rd.Next(p, r);
int temp;
temp = A[r];
A[r] = A[i];
A[i] = temp;
return Partition(A, p, r);
}

public int Partition(int[] A, int p, int r)
{
int x = A[r];
int i = p - 1;
for (int j = p; j <= r - 1; j++)
{
if (A[j] <= x)
{
i += 1;
int temp;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
int temp2;
temp2 = A[i + 1];
A[i + 1] = A[r];
A[r] = temp2;
return i + 1;
}
}
}

轉載于:https://www.cnblogs.com/ision/archive/2008/11/05/1327313.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的从N个元素中选择第i小的元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。