在排序中查找数组中第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; 
}