在排序中查找數組中第n個最小元素？

Question

我想編寫一個程序，找到第n個最小的元素，而不使用任何排序技術..

我們可以遞歸地做，分而治之風格像快速排序嗎？

如果不是，如何？

Answer 1

您可以找到有關這個問題在這裏的信息：Selection algorithm。

Answer 2

可以像這樣使用兩個堆棧來一次定位第N個最小號碼。

• 開始與空棧-A和SP-B
• PUSH第一號到堆棧-A
• 下一個數字開始，選擇推入堆棧-A僅在數小於其頂部
• 當你不得不推入堆棧-A，通過這些步驟
  • 雖然棧-A的TOP是不是新號，協議棧-A的POP TOP較大的運行，並將其推入堆棧-B
  • Wh EN堆棧-A轉爲空或它的頂部是不是新的號碼，推新數量少並對其
  • 恢復堆棧-B的內容。在這一點上，你已經插入新的號碼到其正確（排序）的地方堆棧-A和SP-B又是空
  • 如果堆棧-A現在深度足夠你已經達到你的搜索

---

我大致同意Noldorins'優化分析結束。
這個堆棧解決方案是一個簡單的方案，將工作（相對更多的數據移動 - 跨越兩個堆棧）。堆方案將第N個最小數的提取減少爲樹遍歷（log m）。

如果你的目標是一個最佳的解決方案（假定對於大型組數字也許對編程賦值，優化和它的示範是至關重要的），你應該使用堆技術。

堆棧溶液可以在空間需求由K個元素（其中，K是數據集的大小）相同的空間內實現兩個堆疊被壓縮。所以，缺點就是插入時額外的堆疊運動。

Answer 3

這個任務是很可能通過使用大致O(n)時間（n是所述列表的長度）內完成heap structure（具體地，基於一個Fibonacci heap一個priority queue），其給出O(1)插入時間和O(log n)去除時間）。

考慮從列表中檢索第m個最小元素的任務。通過簡單地遍歷列表並將每個項目添加到優先級隊列（大小爲m），您可以在O(n)時間內有效地創建列表中每個項目的隊列（或者使用某些優化可能更少，儘管我不是當然這是非常有用的）。然後，刪除隊列中優先級最低的元素（最高優先級爲最小項）是一個直接的問題，總共只需要O(log m)時間，並且完成。

所以，總體來說，該算法的時間複雜度將是O(n + log n)，但由於log n << n（即n增長了很多比log n快），這降低了簡單O(n)。在一般情況下，我認爲你不會得到比這更高效的任何東西。

Answer 4

你所指的是選擇算法，如前所述。具體來說，您對快速排序的參考建議您考慮partition based selection。

下面是它如何工作的：

• 就像在快速排序，你就開始採摘了良好的 支點：你認爲是近 中途通過您的列表的東西。然後你 辦理項目的完整清單 交換的東西來回，直到比你的支點 少 所有項目都在列表的開頭，並 比你樞 更大所有的東西都在最後。你的支點進入中間的剩餘點。
• 通常在快速排序你遞歸在樞軸兩側 ，但 選擇算法你只 就在身邊遞歸包含 索引你有興趣，所以，如果 你想找到第三個最低值 值，在包含索引2（因爲索引0是 第一個最低值）的任何一方上遞歸。
• 如果您已將 範圍縮小爲只有一個 索引，則可以停止遞歸。最後，您將有一個「未被排序的」m-1「對象列表」 「對象，以及另一個未排序的」n-m「對象列表。第m個對象將介於兩者之間。

該算法還適用於查找最高m個元素的排序列表...只需選擇第m個最大元素，然後對其上方的列表進行排序。或者，對於速度稍快的算法，執行快速排序算法，但拒絕遞歸到與您想要查找排序值的區域不重疊的區域。

這件事真的很整齊，它通常運行在O（n）時間。第一次通過，它會看到整個列表。在第一次遞歸中，它看到大約一半，然後是四分之一等。因此，它看起來大約2n個元素，因此它運行在O（n）時間。不幸的是，就像在快速排序中一樣，如果你一直選擇一個不好的關鍵點，那麼你將在O（n ）時間內運行。

Answer 5

如果你不想使用斐波那契堆，你可以使用二進制堆。

ALGO：

1. Contruct從陣列這個操作將需要O（n）的時間最小二進制堆。

2. 由於這是一個最小二進制堆，因此根中的元素是最小值。

3. 所以繼續刪除元素frm根，直到你得到你的第k個最小值。 o（1）操作

4. 確保在每次刪除後重新存儲堆kO（logn）操作。

所以運行時間在這裏是O（klogn）+ O（N）............所以它是O（klogn）...

Answer 6

Here is the Ans to find Kth smallest element from an array: 

#include<stdio.h> 
#include<conio.h> 
#include<iostream> 
using namespace std; 
int Nthmin=0,j=0,i; 
int GetNthSmall(int numbers[],int NoOfElements,int Nthsmall); 
int main() 
{ 
    int size; 
    cout<<"Enter Size of array\n"; 
    cin>>size; 
    int *arr=(int*)malloc(sizeof(int)*size); 
    cout<<"\nEnter array elements\n"; 
    for(i=0;i<size;i++) 
     cin>>*(arr+i); 
    cout<<"\n"; 
    for(i=0;i<size;i++) 
     cout<<*(arr+i)<<" "; 
    cout<<"\n"; 
    int n=sizeof(arr)/sizeof(int); 
    int result=GetNthSmall(arr,size,3); 
    printf("Result = %d",result); 
    getch(); 
    return 0; 
} 

int GetNthSmall(int numbers[],int NoOfElements,int Nthsmall) 
{ 
    int min=numbers[0]; 
    while(j<Nthsmall) 
    { 
     Nthmin=numbers[0]; 
     for(i=1;i<NoOfElements;i++) 
     { 
      if(j==0) 
      { 
       if(numbers[i]<min) 
       { 
        min=numbers[i]; 
       } 
       Nthmin=min; 
      } 
      else 
      { 
       if(numbers[i]<Nthmin && numbers[i]>min) 
        Nthmin=numbers[i]; 
      } 
     } 
     min=Nthmin; 
     j++; 
    } 
    return Nthmin; 
}