t**r
发帖数: 3428 | 1 quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerOrEqual = [a | a <- xs, a <= x]
larger = [a | a <- xs, a > x]
in quicksort smallerOrEqual ++ [x] ++ larger
main = do
let a = [ 5, 1, 9, 4, 6, 7, 3]
print $ quicksort a |
|
f*******t
发帖数: 7549 | 2 怎么那么多循环？我的版本只有一层啊：
void quicksort(int arr[], int left, int right)
{
if(left >= right)
return;
int pivot = arr[right];
int i = left;
for(int j = left; j < right; j++)
{
if(arr[j] < pivot)
{
if(i != j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
++i;
}
}
if(i != right) {
int temp = arr[right];
arr[right] = arr[i];
arr... 阅读全帖 |
|
j**l
发帖数: 2911 | 3 难在写partition的具体代码，否则就三句话
Partition,
QuickSort支点左边
QuickSort支点右边
下面是一个比较好记的partition
下界为L, 上界为U
m = L;
for i = [L+1, U]
{
if (x[i] < x[L])
swap(++m, i);
}
swap(L, m); |
|
m********g
发帖数: 272 | 4 虽然worst－case quicksort是O(n^2), 但是on avarage, quicksort 为什么会比
heapsort 快呢？ |
|
y****w
发帖数: 3747 | 5 必须最近准备过，甚至练习过。一般人，包括在巨头的sr.软工们，让他们20分钟写出
来，也得整死大部分。
人家考你这个，就是看你做了多少准备。如果把quicksort都背下来了，得，小伙儿过
来应该比较好用了。 |
|
g********n
发帖数: 4809 | 6 那是因为别人默认你已经在准备面试，就应该会这个，属于考察态度，而不是能力的。
而且quicksort很难吗？ |
|
z****e
发帖数: 2024 | 7 quicksort 不难，heap sort 才难。 |
|
|
|
s********x
发帖数: 914 | 10 heapSort is n/2*log(1.5n)+n*log(1.5n)
quickSort is nlog(n)
node |
|
|
m***p
发帖数: 86 | 12 quicksort时间最差是O(n^2)
mergesort空间上需要O(n)
heapsort时间最差是O(nlogn),空间只需要O(1),为什么提到的频率没有上面两个高呢?
是比较复杂还是其他什么原因? |
|
w**2
发帖数: 8 | 13 1.quicksort 随机化后 nlogn 时间
2.mergesort 链表上 O(1)空间
3.heapsort 需要O(n)辅助空间 除非只是打印 |
|
|
y*******g
发帖数: 6599 | 15 quicksort操作的是local memory
? |
|
V*********r
发帖数: 666 | 16 堆排序很常用啊。之所以在“面试”中不常出，准确的说法是不常考其实现，无非两个
原因：
1. 白板篇幅有限，heapify/siftup/siftdown全写完白板容不下。
2. quicksort/mergesort变种很多，可inplace可外借空间，可迭代可递归（比如考你
非inplace的迭代式mergesort），是分治思想的典型代表，容易形成考点。而且其思想
适用于任何线性表（不管是数组还是链式存储），也可扩展到树形存储。考点密集不奇
怪。
? |
|
J*****a
发帖数: 4262 | 17 quick sort在实践中是最快的，你可以看看相关文献
而且quicksort有很多变种，改变pivot的选取，或者三头并进，能大大提高最坏情况的
性能 |
|
t***t
发帖数: 6066 | 18 quicksort是O(nlogn)算法中常数最小的。 |
|
G*********n
发帖数: 53 | 19 因为 Heapsort 会有大量的 cache 的in & out， 对cache利用不充分，所以用的最少
。对于 mergesort 需要分配一个 新的array来help，所以速度也没有比quick sort快
。相对来说，quicksort最快 |
|
m****y
发帖数: 43 | 20 leetcode哪里找quicksort的code啊？没有这题啊，course里也没有 |
|
i**p
发帖数: 902 | 21 请问面试20分钟写一个quicksort对于毕业10年的工业界程序员reasonable吗? |
|
z****e
发帖数: 54598 | 22 我反正用hadoop的过程中还没遇到过用快排的地方
现在基本上都不sort了，要sort的话，建index的cache就好了
不需要等到用的时候再sort，那多慢呀，而且又吃内存
多sort几下，整个系统就别干其他事了，光忙着sort了
而且快排能并行么？我好像是不太记得怎么做快排的并行
所以感觉做hadoop什么不合适，terasort第一步就是并行化处理
不过说到这里我突然想起来，terasort跟quicksort倒是有些共通之处
可以按照terasort的方式做，但是那样就是terasort而非qs了 |
|
h**o
发帖数: 548 | 23 CLRS problem 7-4:
QUICKSORT using tail recursion is implemented as QUICKSORT':
QUICKSORT'(A, p, r)
1 while p < r
2 do // Partition and sort left subarray.
3 q ← PARTITION(A, p, r)
4 QUICKSORT'(A, p, q − 1)
5 p ← q + 1
QUICKSORT(A, p, r)
1 if p < r
2 then q ← PARTITION(A, p, r)
3 QUICKSORT(A, p, q − 1)
4 QUICKSORT(A, q + 1, r)
请问为何QUICKSORT‘ 和QUICKSORT 是一样的哪？
in QUICKSORT()', 第一次QUICKSORT'(A, p, q − 1), 第二次
因为 p ← q + 1， QUICKSORT'(A, p, q − 1) 相当于 QUICKS... 阅读全帖 |
|
d**e
发帖数: 6098 | 24 ☆─────────────────────────────────────☆
gezwenti (gezwenti) 于 (Sun Feb 28 12:23:17 2010, 美东) 提到:
( 版主能给几个包子吗？ 我从没得过包子， 说的也都是个人真实体验）
真的。 本人在墙街做IT已经六年多了， 拿的也是很普通的薪水， 我现在的Total是135K + 10-25% Bonus （奖金时好时坏， 大致在10% 到 25% 之间）
我只会Java/J2EE。 不会C++, 一点都不会。
现在的Project是做Post-Trading的Changing P&L, Position Calulation.整个
Department是Support Equity Trading的， 公司也是大家都知道的大投行。
我以前的面试经验， 包括我周围IT朋友的面试经验 从来没被问过本版这么难的问题，
1) B-Tree, Graph 这些都太难了， 从没被问过。 最多就问个Binary Tree, 遍历二叉
树。 红黑树都没问道过， 面试官自己都不知道。
2) 数据结构， 最多就问问... 阅读全帖 |
|
h**o
发帖数: 548 | 25 第一次QUICKSORT'后， p = q+1;
然后回line3, q = PARTITION(A, p, r)， 相当于q' = PARTITION(A, q+1, r)；
所以此时得到的新的q'一定在[q+1,r]间吧。
然后line4,QUICKSORT'(A, p, q − 1)， 相当于QUICKSORT'(A, q+1, q' −
; 1)
所以我不明白为何第二次QUICKSORT'后相当于QUICKSORT'(A, q+1, r)而不是
QUICKSORT'(A, q+1, q' − 1)?
q' |
|
d*******n
发帖数: 524 | 26 原本的问题是这样的，我写了一个QuickSorter，如下。但是这样好像只能sort各种
Object的数组，而不能sort built-in 的变量的数组比如int[]
import java.util.Random;
public class QuickSorter> {
public static final Random Rnd = new Random();
public void quickSort(T[] array) {
quickSort(array, 0, array.length-1);
}
private void quickSort(T[] array, int begin, int end) {
if(end > begin) {
int finalPivotPosition = partition(array, begin, end);
quickSort(array, begin, |
|
I******c
发帖数: 163 | 27 in QUICKSORT()', 第一次QUICKSORT'(A, p, q − 1), 第二次
因为 p ← q + 1， QUICKSORT'(A, p, q − 1) 相当于 QUICKSORT'(A, q+1, q'
− 1)
我觉得第二次相当于 QUICKSORT'(A, q+1, r),因为是在同一个function里。我不太清
楚你的q'是如何算出来的。 |
|
p*****2
发帖数: 21240 | 28 QuickSort
static void QuickSort(int[] arr, int start, int end)
{
int pivot=arr[(start+end)/2];
int l=start;
int r=end;
while(l
{
while(arr[l]
l++;
while(arr[r]>pivot)
r--;
if(l<=r)
{
int tmp=arr[l];
arr[l]=arr[r];
arr[r]=tmp;
l++;
r--;
}
... 阅读全帖 |
|
x*******5
发帖数: 152 | 29 这个是我的题库，还有一些题没有coding，比如back of envelop计算，idea思考，等等
Column 4-5 Pearl (namespace Pearl)
64. Implement bitsort (Bitsort)
65 Find the k unique random integers from the range of [0,n-1] (STL, knuth,
swap, floyd) (generate_int_floyd; generate_int_swap; generate_int_knuth)
66. If memory is limited, using k-pass bitsort to sort integers (bitsort_
kpass)
67. Rotation of array (reverse, gcd, blockswap) (rotate; rotate2; rotate3)
68. Permutation of a string (without/with duplicates chars) (String::string_... 阅读全帖 |
|
g***j
发帖数: 1275 | 30 为啥quicksort的空间是lgN, 为啥mergesort的最坏的情况是N? 一般情况是什么？
quicksort, mergesort, heapsort，如何选择用哪个sort？ 我只知道mergesort
stable，那么quicksort和heapsort的差别呢？除了worse case quicksort是n^2
另外，是不是只要涉及到交换的，都不stable? |
|
r********d
发帖数: 7742 | 31 每种sort都有自己的优势和劣势，它们各自都有存在的道理。
quicksort有最好的实践效率。同时是in-place。配上random pivot/shuffle，median-
of-K 和 少量元素转insertion sort是最实用的排序方法。O(n^2)复杂度是极其小概率
事件，一般不会发生。同时因为其对硬件cache的应用效率较高，实践中Quicksort很难
被beat, 因为cache的访问速度比内存寻址快两个数量级。
Mergesort的优势是stable以及在external sort中的使用. 理论分析时候的也会用到
worstcase n(log(n))。同时基本的merge想法和变形，不需要random access, 常常用
在很多其他问题的解决之中。比如说merge lists。但是megersort的constant factor
比较大，是quicksort的好几倍。一般比Quicksort慢。
Heapsort因为在时间上和空间上都是最优，在很多论文只要涉及到sort都会用它做理论
分析。constant factor还不错，比merge sort... 阅读全帖 |
|
s***e
发帖数: 403 | 32 QuickSort递归栈的空间不算内存占用？
我觉得QS应该是时间复杂度O(nlogn)，空间复杂度O(logn)的。
heapsort和quicksort适用面不一样。heap插入删除都是O(logn)的，而quicksort过的
数组如果要插入数据并且保持排序状态，插入要求是O(N)的，删除看具体数据结构而定。
quicksort的cpu cache friendly也要看情况，如果是链表做qs那很难做到每个node都
在cache中。就算是数组，qs里面左移的指针也不一定cache friendly。 |
|
p********2
发帖数: 17 | 33 Randomized Quicksort Variants：
Regularly, RANDOMIZED QUICKSORT selects a single pivot element uniformly at
random. In this problem you will analyze two possible modifications to this
choice of pivot.
For an integer parameter k>=1, the HYBRID RANDOMIZED QUICKSORT algorithm
uses regular RANDOMIZED QUICKSORT whenever n>K , but uses I NSERTION S ORT
whenever n<=k . Analyze the expected running time of HYBRID RANDOMIZED Q
UICKSORT in terms of n and k .
Argue that this sorting algorithm runs in O(nk+n... 阅读全帖 |
|
J********a
发帖数: 5208 | 34 he is looking for using randomized quicksort. (not full sort, just use the
partition routine)
just use inplace quicksort, use the new value as pivot value and while the
final placement is not in the middle, call the partition routine on the
larger portion.
This should be as fast as the heap method, but no additional space needed.
For more information you can watch MIT opencourse for algorithm
Lecture 4: Quicksort, Randomized Algorithms
and
Lecture 6: Order Statistics, Median
median |
|
i**********e
发帖数: 1145 | 35 不好意思，我之前的解答没考虑到还要对 ==0 的也进行数组移位。虽然 DNF 可以改进
来保持顺序，但由于数组移位的关系，复杂度肯定是 O(N^2)。那还不如用 insertion
sort. 感觉不可能会有 O(N) 的 in-place partition 并且保证顺序。唯一一个办法就
是用链表，那就能保证 O(N)。
我在网上找了找，应该就是这题啊，题目也没要求要保持顺序：
http://www.glassdoor.com/Interview/Partition-an-array-in-such-w
还有，另一点是这题也曾在 Programming pearls 出现过。在 Column 11 的第 11 条
练习题。这个 3-way partition 可是应用于 quicksort 里的。可以在网上搜 3-way
quicksort partition。quicksort 也不是 stable sort。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
a*******6
发帖数: 520 | 36 所谓的quicksort不stable不是说partition那一步，而是选pivot那步
一般认为的quicksort，（递归的）每次随机选一个pivot，然后partition，复杂度期
望下是O(nlogn)，最坏是O(n^2)，这个可能是你说的不stable
但是partition那一步肯定是O(n)的
理想情况下，如果pivot选到median，那么复杂度肯定是O(nlogn)了
有一种确定性算法可以每次以O(n)的时间选到一个pivot在median附近（至少1/3的元素
小于他，同时至少1/3的元素大于他），那么这样quicksort的复杂度最坏情况下也是O(
nlogn)了，不过实际中没太多人用这个版本，因为其实实际的performance不如那个随
机选pivot的版本 |
|
x*******5
发帖数: 152 | 37 题目是37道，但是程序（函数数目）是70个，不少题都是要求编两三个程序的，比如
array rotation, string permutation, quick sort(这个就要编5个，各种quicksort,
解决时间，空间，tail-recursion问题, fat-pivot), quicksort还有变体: dutch
flag, select-k，等等
我自己在面试的时候，所有问题都来自这个，有一题还要我分析tournament tree（这
个是pearl的一个小题目，我当时偷懒没想清楚，所以不能偷懒啊），不过我当时的程
序做错了，和面试官一讨论发现错了。另一次面试全是quicksort，如果做了pearl的题
，应该不会有问题。
欢迎大家一起讨论，这些代码一定有不少hidden bugs |
|
s********x
发帖数: 914 | 38 可能java自带的quicksort不够强？
怎么说也该考虑median of three， 已经three way partition来handle duplicate吧
如果你指的是Array.Sort,可能都不是implemented in quicksort。 因为quicksort不
是stable的。
http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html
(For example, the algorithm used by sort(Object[]) does not have to be a
mergesort, but it does have to be stable.) |
|
z****e
发帖数: 2024 | 39 请问 heapsort vs. quicksort.
基本的不提了，什么 worst case, pre-sorted, in place, etc.
不明白，看到一些资料，说 in practice, quicksort beats heapsort, because
quicksort has less comparisons on average.
有这么一说吗？觉得 less comparisons 这句话挺深刻的，有什么文献提到两者的比
较？
谢谢。 |
|
h*******e
发帖数: 225 | 40 I dont think quicksort has less comparisons on average. It really depends on
how you implement them. For example, using William's original heapify
algorithm, you need 2nlogn + O(n) comparisons, whereas using Floyd's heapify
algorithm, you only need nlogn + O(n) on average. There are many variants
for quicksort too.
The reason why quicksort generally beats heapsort is largely due to the data
access pattern. It has better cache locality. |
|
I******c
发帖数: 163 | 41 哦，我明白你说得第一次和第二次的QUICKSORT'的具体意思了。你说第二次QUICKSORT'
(A, q+1, q' − 1)实际上也是相当于QUICKSORT(A, q+1, q' − 1)的。 |
|
l**********n
发帖数: 8443 | 42 这个很难吗？
function quicksort(array)
if length(array) ≤ 1
return array // an array of zero or one elements is already sorted
select and remove a pivot element pivot from 'array' // see '#Choice
of pivot' below
create empty lists less and greater
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), list(pivot), quicksort(greater)) //
two rec |
|
p*u
发帖数: 2454 | 43 #include
#include
#include
// Change this to change the number of elements to be stored and sorted
#define ARRAY_LENGTH 128
template
void quickSort(Type* array, int low, int high)
{
int pivotPosition = -1;
if ( low < high )
{
pivotPosition = partition(array, low, high);
quickSort(array, low, pivotPosition-1);
quickSort(array, pivotPosition+1, high); |
|
c*****t
发帖数: 1879 | 44 回去复习一下 quicksort 的定义吧。你可以弄个 O (nlogn）不错，但是
那不一定是 quicksort 。不要指着 merge sort 或者 merge sort 的变种
说是 quicksort 。 |
|
z****e
发帖数: 2024 | 45 比较 heapsort , quicksort
我怎么觉得从理论上说heapsort比quicksort 好呢？
那为什么大部分书都说 "in practice, quicksort beats heapsort"
看到有个文献是从entropy的角度考虑这个问题。太长了，结论也不清楚。
哪位大侠肯出手相救？ |
|
d******c
发帖数: 2407 | 46 随便搜出来的，不是我写的
def quicksort(list) {
if (list.size() < 2) return list
def pivot = list[list.size() / 2]
def items = list.groupBy { it <=> pivot }.withDefault { [] }
quicksort(items[-1]) + items[0] + quicksort(items[1])
} |
|
s******8
发帖数: 4192 | 47 “有点耗时，是吧？”，如果是对方问的，就是在试探你。你这个时候应该坚持，如果
用quicksort，这是最快的算法了。我觉得这才是正确答案。
当然对于这个题目，可以在quicksort第二个数组的时候做一些优化,或者用binary
search。可能快一点点，但是相对于编程工作量来说，得不偿失。
45 |
|
m*****g
发帖数: 226 | 48 heapsort我觉得比quicksort好写
quicksort下标搞来搞去很烦 |
|
f****4
发帖数: 1359 | 49 也不需要变形的quicksort这么复杂，直接quicksort后再走一遍即可 |
|
m****u
发帖数: 3915 | 50 你说了背景能力相同
如果ee的，写不出quicksort可以理解
如果cs的，写不出quicksort估计就废了 |
|
