我一直在研究讨论快速排序和快速选择的各种教程和文章,但是我对它们的理解仍然不稳定.
鉴于这种代码结构,我需要能够掌握并解释quickselect的工作原理.
// return the kth smallest item
int quickSelect(int items[], int first, int last, int k) {
int pivot = partition(items, first, last);
if (k < pivot-first) {
return quickSelect(items, first, pivot, k);
} else if (k > pivot) {
return quickSelect(items, pivot+1, last, k-pivot);
} else {
return items[k];
}
}
我需要一些帮助来分解伪代码,虽然我没有提供分区功能代码,但我想了解在提供quickselect功能的情况下它会做什么.
我知道quicksort是如何工作的,只是没有快速选择.我刚才提供的代码就是如何格式化快速选择的一个例子.
编辑:更正后的代码是
int quickSelect(int items[], int first, int last, int k)
{
int pivot = partition(items, first, last);
if (k < pivot-first+1)
{ //boundary was wrong …问题:我经常需要查看特定日志最后一天内最常重复的"模式".就像这里的一小部分tomcat日志一样:
GET /app1/public/pkg_e/v3/555413242345562/account/stats 401 954 5
GET /app1/public/pkg_e/v3/555412562561928/account/stats 200 954 97
GET /app1/secure/pkg_e/v3/555416251626403/ex/items/ 200 517 18
GET /app1/secure/pkg_e/v3/555412564516032/ex/cycle/items 200 32839 50
DELETE /app1/internal/pkg_e/v3/accounts/555411543532089/devices/bbbbbbbb-cccc-2000-dddd-43a8eabcdaa0 404 - 1
GET /app1/secure/pkg_e/v3/555412465246556/sessions 200 947 40
GET /app1/public/pkg_e/v3/555416264256223/account/stats 401 954 4
GET /app2/provisioning/v3/555412562561928/devices 200 1643 65
...
如果我想找出最常用的URL(以及方法和重新编码) - 我会这样做:
[root@srv112:~]$ N=6;cat test|awk '{print $1" "$2" ("$3")"}'\
|sed 's/[0-9a-f-]\+ (/%GUID% (/;s/\/[0-9]\{4,\}\//\/%USERNAME%\//'\
|sort|uniq -c|sort -rn|head -$N
4 GET /app1/public/pkg_e/v3/%USERNAME%/account/stats (401)
2 GET /app1/secure/pkg_e/v3/%USERNAME%/devices (200)
2 GET /app1/public/pkg_e/v3/%USERNAME%/account/stats (200)
2 DELETE /app1/internal/pkg_e/v3/accounts/%USERNAME%/devices/%GUID% (404)
1 POST /app2/servlet/handler …是否可以在O（n）上对多集执行第k个元素的搜索（值可以重复）？
因为据我了解的快速选择的想法，我必须使用一些支点来划分输入。然后，我有2个数组，我选择进行递归搜索取决于我要搜索的索引元素+两个数组的大小分别是多少：
1 7 8 5 3 2 4
假设数据透视为4，我正在搜索第二大元素。所以分区后我可能会得到像
1 3 2 4 7 8 5
因为正确的子数组由3个元素组成，如果我是正确的话，我仍然会尝试在正确的数组中找到第二大的数组？
但是，如果我以8为支点，我可能会得到类似
1 3 2 7 5 4 8
因此，我将尝试在左侧表格中找到最大的元素（适当地通过线性查找，但一般而言，我将采用左侧子数组并搜索元素-（|右侧子数组大小| + 1））
但是多集呢？假设我有数组：
4 5 6 7 7 7 4 3 2 1
我的枢纽是6搜索第三大元素，分区后我收到：
4 5 3 2 4 1 6 7 7 7
因此，如果我使用上面介绍的方法，我将尝试在右子数组上执行递归，而显而易见的第三大值是5，它在左边？
我想出的唯一解决方案是使用某些数据结构（例如BST，Set等）来过滤O（nlogn）重复项。然后使用O（n）快速选择。但是总的来说，它会给我非线性方法，这可以线性吗？
我还有一个额外的问题，如果无法完成分配内存该怎么办？我所能做的就是只使用局部整数+堆栈递归。这个问题可以在O（n）中解决吗？因为O（nlogn）可以通过排序+线性“通过计数”来完成。
从https://en.wikipedia.org/wiki/Quickselect它说
“然而，不像快速排序那样递归到两边，quickselect 只递归到一侧——它正在搜索的元素所在的一侧。这将平均复杂度从 O(n log n) 降低到 O(n)，其中O(n^2) 的最坏情况。”
我不明白减少到只看一侧如何将平均复杂度降低到 O(n)？是不是更多的 O(N/2 log N) 仍然是 O(N log N)。最坏的情况如何 O(n^2)