简答题

给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素,请设计一个最坏时间复杂度为O(n)的算法,并对其时间复杂度进行分析说明。

正确答案

我们把这种算法叫做快速选择(quickselect)。令〡Si〡为Si中元素的个数,快速选择的步骤如下:
1)如果〡S〡=1,那么k=1并将S中的元素作为答案返回。如果正在使用小数组的截止方法且〡S〡≤CUTOFF,则将S排序并返回第k个最小元。
2)选取一个枢纽元v∈S。
3)将集合S-{v}分割成S1和S2,就像快速排序中所做的那样。
4)如果k≤〡S1〡,那么第K个最小元必然在S1中。在这种情况下,返回quickselect(S1,k),如果k=1+〡S1
,那么枢纽元就是第k个最小元,将它最为答案返回。否则,第k个最小元就在S2中,他是S2中的第(k-〡S1〡-1)个最小元。我们进行一次递归调用并返回quickselect(S2,k-〡S1〡-1)。
与快速排序对比,快速选择只进行了一次递归调用而不是两次。快速选择的最坏情形和快速排序的相同,也就是O(N=2)。直观看来,这是因为快速排序的最坏情形发生在S1和S2有一个是空的时候;于是,快速选择也就不是真的节省一次递归调用。不过平均运行时间是O(N)。具体分析类似快速排序的分析。
快速排序的实现甚至比抽象描述还要简单,当算法终止时,第k个最小元就在位置k-1上(因为数组开始于下标0)。这破坏了原来的排序;如果不希望这样,那么需要做一份拷贝。

答案解析

相似试题
  • 二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单位,并且第一个元素的存储地址是LOC(A[0][0]),则A[i][j]的地址是()。

    填空题查看答案

  • 已知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[i][j]的地址是()。

    填空题查看答案

  • 在一个长度为n的顺序存储线性表中,向第i个元素(1≤i≤n+1)之前插入一个新元素时,需要从后向前依次后移()个元素。

    单选题查看答案

  • 在一个长度为n的顺序存储线性表中,删除第i个元素(1≤i≤n+1)时,需要从前向后依次前移()个元素。

    单选题查看答案

  • 已知一个栈的输入序列为1,2,3,...,n,则其输出序列的第2个元素为n的输出序列的种数是()。

    填空题查看答案

  • 对于n个元素构成的降序顺序线性表,采用冒泡排序按照关键字升序排列时共需进行()趟排序。

    填空题查看答案

  • 对于n个元素构成的降序顺序线性表,采用快速排序按照关键字升序排列时共需进行()次划分。

    填空题查看答案

  • 设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i>=j),在一维数组B的下标位置k的值是()。

    单选题查看答案

  • 已知长度为n的线性表A中的元素是整数,写算法求线性表中值大于item的元素个数。分两种情况编写函数: (1)线性表采用顺序存储; (2)线性表采用单链表存储。

    简答题查看答案