今天學習了求第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;
}