今天学习了求第i小元素，被书上忽悠了一下，他硬说是0(n)的复杂度，我怎么看怎么看就是快速排序的思路，只是省去一半的递归而已。我开始还以为真的就0(n)呢，自己还想了好久用一个循环搞定之，结果后来发现，o(n)是最理想情况了。哎。书上说的有个中位数来得到o(n)的求第i小元素的方法，可以我愚笨，没有看懂。我就不信他插入排序不算时间，然后递归一下求中卫数，能正确？反正我是没有看懂，也不敢实现了。只实现了快速排序思路的方法，而且还发现，我写了N遍快速排序了，居然还出错！我也发现我以前的写法也有错。哎，郁闷啊。继续加油吧。。坚持。。
奉上源代码：(没有什么，就是快排)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//随机分隔，(就是快排的分割函数)
int RandomPartition(int nData[], int nBegin, int nEnd)
{
int i = nBegin + rand() % (nEnd - nBegin);
int nX = nData[i];
nData[i] = nData[nBegin];
nData[nBegin] = nX;
--nEnd;
while(nBegin < nEnd)
{
while(nData[nEnd] > nX)
{
--nEnd;
}
if (nBegin < nEnd)
{
nData[nBegin] = nData[nEnd];
nData[nEnd] = nX;
++nBegin;
}
while (nData[nBegin] < nX)
{
++nBegin;
}
if (nBegin < nEnd)
{
nData[nEnd] = nData[nBegin];
--nEnd;
}
}
nData[nBegin] = nX;
return nBegin;
}
//递归调用得到第i小元素
int RandomIzedRecursion(int nData[], int nBegin, int nEnd, int nPos)
{
if (nBegin >= nEnd - 1) //如果nBegin，直接认为找到了该值
{
return nData[nBegin];
}
int i = RandomPartition(nData, nBegin, nEnd); //分割两部分
if (i == nPos) //如果刚好分割符号就是nPos，就找到了这个值。
{
return nData[i];
}
if (i > nPos) //i > nPos。这继续递归nBegin - i的区域。
{
return RandomIzedRecursion(nData, nBegin, i, nPos);
}
//否则递归 i + 1, nEnd区域，不过这时候nPos要相应的改变为nPos - i - 1
return RandomIzedRecursion(nData, i + 1, nEnd, nPos - i - 1);
}
//得到第i小元素
int RandomIzedSelect(int nData[], int nLen, int nPos)
{
srand((size_t)time(NULL));
return RandomIzedRecursion(nData, 0, nLen, nPos);
}
int main()
{
int nData[10] = {8,2,5,9,3,6,4,7,1,6}; //测试
int nTest;
for (int i = 0; i < 10; ++i)
{
nTest = RandomIzedSelect(nData, 10, i);
printf("%d ", nTest);
}
printf("\n");
for (int i = 0; i < 10; ++i) //注意，这里是改变了原来的数据
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}