當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

随机查找数组中第i个元素（按顺序排列的）

發布時間：2025/4/16 编程问答 36 豆豆

生活随笔收集整理的這篇文章主要介紹了随机查找数组中第i个元素（按顺序排列的）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

在一個無序的序列中，要查找第i小的元素最簡單的方法就是將所有元素排序，就可以直接找到地i小的元素，然而比較排序算法最快也只能是O(nlogn)，比如堆排序、歸并排序、快速排序。這里研究了只要時間復雜度為O(n)的算法。

?????? 利用快速排序算法中的樞軸元素，即樞軸元素的左邊全是小于等于它的元素，樞軸元素的右邊全是大于等于它的元素，則樞軸元素的位置k就是它在序列中第k小的元素，然后用k和要查找的i比較判斷即可。這里用到了分治算法，每次遞歸調用都可以排除掉部分元素：樞軸元素的全部左部分元素或樞軸元素的全部右部分元素。

主要思想：

1、假設n=1時，就是只有一個數，

直接返回這個位置的值就是所求的第i個值

int RandomSelect(int *pnArr, int nLeft, int nRight, int i) {if (nLeft == nRight){return pnArr[nLeft];}//尋找一個nTmpPos下標，nTmpPos左邊的值都小于它，右邊的值都大于它int nTmpPos = RandomPartiton(pnArr, nLeft, nRight);int nLCount = nTmpPos - nLeft + 1;if (nLCount == i){return pnArr[nTmpPos];}else if (i < nLCount){return RandomSelect(pnArr, nLeft, nTmpPos - 1, i);}else{return RandomSelect(pnArr, nTmpPos + 1, nRight, i - nLCount);} } 2、當數組的個數大于2時，運用快速排序的思想，尋找一個主元的地址，

如果主元在的位置正好是所求的第i個數，則返回值

//尋找一個nTmpPos下標，nTmpPos左邊的值都小于它，右邊的值都大于它int nTmpPos = RandomPartiton(pnArr, nLeft, nRight); </pre><pre name="code" class="html">
</pre>如果i小于所求的主元地址，則在數組的前半部分求第i個數，主要運用遞歸的思想，第i個數也是在前半部分數組的第i個位置，所以遞歸時所查找的位置還是i<pre name="code" class="html" style="line-height: 24px;"> else if (i < nLCount){return RandomSelect(pnArr, nLeft, nTmpPos - 1, i);} 如果第i個元素的地址大于主元地址 <pre name="code" class="html"> {return RandomSelect(pnArr, nTmpPos + 1, nRight, i - nLCount);} 所查找的地址在數組的后半段，所在的地址是i - nLCount的位置 代碼： <pre name="code" class="html">#include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <time.h>void PrintArr(int *pnArr, int nLen) {for (int i = 0; i < nLen; i++){printf("%d ", pnArr[i]);}printf("\n"); }void Swap(int *p1, int *p2) {int nTmp = *p1;*p1 = *p2;*p2 = nTmp; }int Partition(int *pnArr, int nLeft, int nRight) {int nKey = nRight;int i = nLeft - 1;for (int j = nLeft; j < nRight; j++){if (pnArr[j] <= pnArr[nKey]){i++;Swap(&pnArr[i], &pnArr[j]);}}Swap(&pnArr[i+1], &pnArr[nKey]);return i+1; }int RandomPartiton(int *pnArr, int nLeft, int nRight) {srand(time(NULL));int i = rand()%(nRight - nLeft + 1) + nLeft;Swap(&pnArr[i], &pnArr[nRight]);return Partition(pnArr, nLeft, nRight); } //i 第i小元素 int RandomSelect(int *pnArr, int nLeft, int nRight, int i) {if (nLeft == nRight){return pnArr[nLeft];}//尋找一個nTmpPos下標，nTmpPos左邊的值都小于它，右邊的值都大于它int nTmpPos = RandomPartiton(pnArr, nLeft, nRight);int nLCount = nTmpPos - nLeft + 1;if (nLCount == i){return pnArr[nTmpPos];}else if (i < nLCount){return RandomSelect(pnArr, nLeft, nTmpPos - 1, i);}else{return RandomSelect(pnArr, nTmpPos + 1, nRight, i - nLCount);} }int main() {int nArr[10] = {0,2,1,3,5,6,9,7,4,12}; PrintArr(nArr, 10);printf("第5最小元素的值為%d\n", RandomSelect(nArr, 0, 9, 5));system("pause");return 0; }

總結

以上是生活随笔為你收集整理的随机查找数组中第i个元素（按顺序排列的）的全部內容，希望文章能夠幫你解決所遇到的問題。

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