s****A
发帖数: 80 | 1 如果只找一般的SDE工作
是不是只需要看bubble sort, insertion sort, selection sort, merge sort，quick
sort, radix sort, heap sort，BST, Balanced tree, hashing 就够了？
我看的书还有如下章节:
shell sort
special-purpose sorts(Batcher's odd-even merge sort, sorting networks,
external sorting, parallel sort/merge)
radix search
external searching
这些还需要看吗？
谢谢！ |
|
f****p
发帖数: 18483 | 2 在一般情况下，quick sort比heap sort快是因为下面几个原因。
1）quick sort没有事先的准备。heap sort一开始要建堆。
2) quick sort 在一个pass以后，分界的那个element就是最终结果，一个pass的cost
和整个pass的数乘积基本上就是nlogn。heap sort取出一个后得要从上到下做调整，就
是差不多logn，乘积也差不多是nlogn。
3) 如果是多个cpu，多个thread，quick sort 绝对要比heap sort 强。
其实quick sort 主要的强的就是1) |
|
x********u
发帖数: 1150 | 3 1. merge sort
no extra space needed. It is decided by the nature of linked list.
when merging two sorted sub lists, you can represent ordering by reassigning
node's next pointers. array elements don't have next pointers. so extra
array is needed to hold merged result. ordering in array is reflected by
array's indexes.
2. quick sort
copy linked list's node values into an array.
quick sort this array.
reassign linked list by copying values from the sorted array.
why this is a good approach? it can... 阅读全帖 |
|
l*******y
发帖数: 1498 | 4 quick sort时间依赖于pviot，最好情况下才是nlgn，但是有较好的cache behavior.
heap sort 最差情况下是nlgn，但是heap sort 有很多random access，如果数据是从
high latency的设备上读的话会比较慢。
merge sort最差是nlgn，需要额外的空间(上面2个sort都可以in place完成)，也有比较好的cache behavior，还有merge sort更容易parallelize |
|
r*********r
发帖数: 3195 | 5 in STL, stable_sort() is merge sort. it's O(n*logn) when extra memory is
available, but O(n*(logn)^2) when not using extra memory.
STL's sort() is quick sort with some twists, it switches to heap sort when
the recursion depth is high, and uses insertion sort for small chunks.
sometimes this hybrid algorithm is called "introspective sort".
quick sort's performance heavily depends on how to pick the pivot. |
|
c**********e
发帖数: 2007 | 6 How do you use STL's std::sort algorithm to sort an array declared as int v[
1000]?
a) std::sort(v);
b) std::sort(v,v+1000);
c) std::sort((void*)v, 1000, sizeof(int), sortInt);
(assuming sortInt is defined properly)
d) std::sort((void*)v,(void*) &v+1000, sizeof(int));
e) std::sort(v.begin(),v.end()); |
|
f****p
发帖数: 18483 | 7
我其实还好少说了一个。
quick sort把一个分裂成两个的时候，理想情况是平均分。而下一步两个子表的长度都
是那个父表的一伴。而heap sort则不是。
你仔细观察这个动画。heap的准备和每一步做的都有。
http://en.wikipedia.org/wiki/Heapsort
如果一般情况下
quick sort cost = n + (n/2 + n/2) + (n/4 + n/4 + n/4 + n/4) + ...
= n * log(n)
heap sort cost = sum [log(i)] for i = n, n-1, n-2, ..., 1
所以尽管heap sort 是 n log(n)，quick sort基本上是最优的。
为了达到最优效果，对于大的n，一般还会做个randomization。很多randomized
algorithms就是这个思路。一般就一两遍就可以达到了，就是说再加上个n 或者 2n。 |
|
r**********g
发帖数: 22734 | 8 quick sort是O(n^2)好吧。要O(nlogn)，需要先randomize。quick sort还不是stable
的。以前说qsort快主要是cache line优化得好，如果是sort object的话其实都是一样
，我试过，用java写qsort还不如heap sort快。heap sort很适合用在需要不断添加删
除对象的sorted heap对象。而现在大规模parallel，像MapReduce，其实MergeSort要
好得多。 |
|
b******p
发帖数: 49 | 9 我来贴个CPP的（注意：以下有乱七八糟的code……）
合并排序确实比较好用，我还在写第一遍leetcode，代码风格也比较乱，带了很多
debug code，还带了测试用例，试了9次才通过…
有一些多边界条件需要判断的。我的方法是加很多debug，或加很多assertion（我做别
的题里面经常用assertion……不知道是不是好习惯）
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
#include
#include
using namespace std;
/*
Merge sort ?
*/
// Start: 22:40
// End: 23:45 用了一个小时
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
#define TOMMYDBG
class Solution {
public:
... 阅读全帖 |
|
w******g
发帖数: 67 | 10 【 以下文字转载自 JobHunting 讨论区 】
发信人: wyizhang (MM), 信区: JobHunting
标 题: 哪位大写给说说 何时用 merge sort, 何时用 heap sort， 何时用 quick sort?
发信站: BBS 未名空间站 (Mon Aug 23 19:59:19 2010, 美东)
刚开始看书，理解不够深刻，哪位大侠给科普一下。
1. 这三个算法都平均复杂度都是 (nlgn), 该怎么选择用哪一种算法呢？
2. 看到以前有例子说n非常大的话用merge sort，几台机器分别sort，然后再merge，
这是为什么
呢？merge sort 不是需要而外的空间～n 吗？这时候用quicksort 会不会好一些？
多谢。 |
|
r*d
发帖数: 896 | 11 merge sort是stable的
quick sort是unstable
如果要保留原数据的顺序，要用merge sort
也有stable quick sort，不过比较复杂 |
|
x*********w
发帖数: 533 | 12
In practice quick sort is faster,
I think this is because every iteration the array becomes more "tend to be
sorted" so less "swap" operation like heapsort. And if the number of
members is less than a certain limite, insert sort is taken place, which is
the best sorting method for "almost sorted" array. |
|
m**********n
发帖数: 97 | 13 leetcode上有一道 sort list的题目，
Sort a linked list in O(n log n) time using constant space complexity.
我刚开始想用quick sort，但是答案不accept，看网上的解答大部分是用C++做merge
sort，想问问大家有木有java的解，都用的是merge sort吗？还有用merge sort的
space complexity是O(1)吗？我觉得不是啊。。。
二爷快快出来 |
|
h*******3
发帖数: 3775 | 14 有一组数据，其中的fied有surname, department,payRate,等等
要求是按照surname 从A 到Z 排列这组数据。排列的方法是straight insertion
我现在的方法已经可以sort surname, department,但是如何能把他改成templates呢？
这样就能用来sort 任何数据。
我的目前sort的方法是这样的：
struct emp
{
char surname[15];
char given[15];
char depart[20];
double payRate;
char eyeColor[10];
};
void sort(struct emp person[], int nums, compare cmp, copy cpy)
{
void *key;
int j, i, flag;
struct emp temp;
for (j = 1; j < nums; j ++)
{
i = j - 1;
(*cpy)(key, (person + j));
te... 阅读全帖 |
|
g****5
发帖数: 1639 | 15 对于无序的数列，O(nlgn)就是平均最快的sort。当然能够达到O(nlgn)的sort算法有很
多。对比其他数量级最快的算法，quick sort比heap sort一般O(nlgn)的系数要小，所
以更快。跟merge sort比，不需要征用O(n)的额外内存，所以空间上更有效。 |
|
k*k
发帖数: 49 | 16 Constructing Young's Tableau does not offer too much benefit on sorting...
for n^2 numbers, the lower bound for comparison-based sorting is
2 n^2 log n (or N log N if N == n^2)
given each row/col is sorted, sorting will take in O(N^1.5) N * sqrt(N);
N for total numbers, sqrt(N)=n for complexity to extract min from remaining matrix.
N*sqrt(N) > N log N ...
so i guess it is better just sort it directly. |
|
w******g
发帖数: 67 | 17 刚开始看书，理解不够深刻，哪位大侠给科普一下。
1. 这三个算法都平均复杂度都是 (nlgn), 该怎么选择用哪一种算法呢？
2. 看到以前有例子说n非常大的话用merge sort，几台机器分别sort，然后再merge，
这是为什么
呢？merge sort 不是需要而外的空间～n 吗？这时候用quicksort 会不会好一些？
多谢。 |
|
s*********t
发帖数: 1663 | 18 heap sort很常用，比如找top k，动态的，就可以开个k size的heap
merge sort我在搜索引擎的应用里用过，搜两个关键字，索引返回两个集合，这时候需
要合并。 这两个集合应该是有序的，此时只需要merge sort的merge即可。
qsort很省事，一般的排序，算法题目，都可以使用。 |
|
x*********w
发帖数: 533 | 19 quick sort版本
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
void sort(NODE* pNode, int nLen)
{
if (NULL == pNode || nLen <= 0)
return;
int nCount = 0;
int nPivot = pNode->nVal;
NODE* pPrev = pNode;
NODE* pIterBeg = pPrev->pNext;
NODE* pIterEnd = pIterBeg;
while (NULL != pIterEnd)
{
if (pIterEnd->nVal < nPivot)
{
swap(pIterBeg->nVal, pIterEnd->nVal);
pPrev = pPrev->pNext;
... 阅读全帖 |
|
r*********n
发帖数: 4553 | 20 irrespective of CPU caching, quick sort has another theoretical advantage
over heap sort: 3way-quick sort is entropy-optimal, O(nh) where h is the
entropy, whereas the other one is not.
if all the elements are truly uniformly distributed btw 0 and n-1, then h =
logn. however, for all other discrete distributions, h < logn and hence
quick sort is superior |
|
l******9
发帖数: 579 | 21 【 以下文字转载自 Database 讨论区 】
发信人: light009 (light009), 信区: Database
标 题: sort two same tables SQL but different results
发信站: BBS 未名空间站 (Fri May 9 09:57:41 2014, 美东)
I am sorting two tables on SQL.
The two tables have the same column names and types and rows numbers.
I used order by to do sorting but the two tables are different in order.
Example,
SELECT *
FROM table1 AS t1
ORDER BY t1.col1 , t1.col2, t1.col3, t1.col4 ASC
SELECT *
FROM table2 AS t2
ORDER BY t2.col1 , t2.col2, t2.col3, t2.col4 ASC
T... 阅读全帖 |
|
l********o
发帖数: 89 | 22 我只是就quick sort而言随便一说，想说明大多数的时间是省在不需要sort全部的N。
那个heap的办法是很好的。当然也是可以进一步优化。你在heap内部sort完的部分
用binary查找，又可以把X省成logX。
quick sort只是在一般情况下比较快。 这个特殊情况显然有比quick sort好的办法。 |
|
g*****g
发帖数: 34805 | 23 Quicksort is an internal sorting algorithm, typically you have
to put the entire arrary in memory. Also, QS can be as slow as
O(N^2) in worst case. Merge sort normally is slower than QS
for a random array, but external sort is possible.
sort? |
|
l******9
发帖数: 579 | 24 【 以下文字转载自 Database 讨论区 】
发信人: light009 (light009), 信区: Database
标 题: sort two same tables SQL but different results
发信站: BBS 未名空间站 (Fri May 9 09:57:41 2014, 美东)
I am sorting two tables on SQL.
The two tables have the same column names and types and rows numbers.
I used order by to do sorting but the two tables are different in order.
Example,
SELECT *
FROM table1 AS t1
ORDER BY t1.col1 , t1.col2, t1.col3, t1.col4 ASC
SELECT *
FROM table2 AS t2
ORDER BY t2.col1 , t2.col2, t2.col3, t2.col4 ASC
T... 阅读全帖 |
|
l******9
发帖数: 579 | 25 【 以下文字转载自 Database 讨论区 】
发信人: light009 (light009), 信区: Database
标 题: sort two same tables SQL but different results
发信站: BBS 未名空间站 (Fri May 9 09:57:41 2014, 美东)
I am sorting two tables on SQL.
The two tables have the same column names and types and rows numbers.
I used order by to do sorting but the two tables are different in order.
Example,
SELECT *
FROM table1 AS t1
ORDER BY t1.col1 , t1.col2, t1.col3, t1.col4 ASC
SELECT *
FROM table2 AS t2
ORDER BY t2.col1 , t2.col2, t2.col3, t2.col4 ASC
T... 阅读全帖 |
|
z****e
发帖数: 2024 | 26 是一个基于quick sort，但是具有探查机制的算法，一旦检测到出现二次方增长倾向，
就自动改为insertion sort。
对于一个general sort算法，几乎STL 的sort已经是目前最快的。 |
|
u****g
发帖数: 402 | 27 online测试题，哪个function 可以来 sort array of string，
qsort or sort？
网上搜出来的都是在讲怎么用qsort来排序array of string, 但sort应该更好用并且更
简单吧。 |
|
e***s
发帖数: 799 | 28 求 Leetcode Online Judge Sort Color one pass constant space 解法。
Copy 下题目：
Given an array with n objects colored red, white or blue, sort them so that
objects of the same color are adjacent, with the colors in the order red,
white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white
, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using coun... 阅读全帖 |
|
|
p*****3
发帖数: 488 | 30 给个我以前写的吧，快速排序版本的
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
void sort(NODE* pNode, int nLen)
{
if (NULL == pNode || nLen <= 0)
return;
int nCount = 0;
int nPivot = pNode->nVal;
NODE* pPrev = pNode;
NODE* ... 阅读全帖 |
|
f**********3
发帖数: 295 | 31 public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode tail = head.next;
while (tail.next != null) {tail = tail.next;}
HeadTail ret = sort(head, tail);
return ret.head;
}
class HeadTail {
ListNode head;
ListNode tail;
public HeadTail(ListNode head, ListNode tail) {
this.head = head;
this.tail = tail;
}
}
... 阅读全帖 |
|
n*****g
发帖数: 178 | 32 在网上看到这题在：Sort numbers stored on different machines
出处：http://www.geeksforgeeks.org/sort-numbers-stored-on-different-machines/
Given N machines. Each machine contains some numbers in sorted form. But the
amount of numbers, each machine has is not fixed. Output the numbers from
all the machine in sorted non-decreasing form.
Example:
Machine M1 contains 3 numbers: {30, 40, 50}
Machine M2 contains 2 numbers: {35, 45}
Machine M3 contains 5 numbers: {10, 60, 70, 80, 100}
... 阅读全帖 |
|
S*******C
发帖数: 822 | 33 If you were given an array of 1 million integers representing age of people
in a city. What kind of sort would you use for that array?
然后要我实现因为在写bucketsort用了一些时间还卡顿了一下，小哥也给了提示，最后
还是写出来了。其中有试着去google，结果被小哥听到了，说你是在coding吗？你先给
我一个思路再coding···表示超级囧···
最后小哥说你做得很好，成功了99%由于时间关系，我们就停止了（此处表示很虚啊·
·····）
我认为应该用counting sort啊。bucket sort只能实现分段排序，不能每个元素都依次
排序啊 |
|
b*********n
发帖数: 1258 | 34 比如说一个vector x是1,2,3,4,5
另外一个vector y是a,b,c,d,e
我想sort 1,2,3,4,5成5,4,3,2,1,同时a,b,c,d,e成e,d,c,b,a
C++里面我用sort函数来sort x w/ Comp函数f
怎样才可以同时以同样的order来sort y但是却不用Comp函数f呢？
谢谢 |
|
p*****1
发帖数: 128 | 35 HP申请一个create partially sorted index的专利 (US 2008/0104102)。
"To provide an index for a table in a database system, the index is
partially sorted in an initial phase of building the index. Subsequently, in
response to accessing portions of the index to process a database query,
further sorting of the accessed portions of the index is performed."
it is using B-Tree, divid index into different internal nodes, will sort the nodes (but not the entire tree). where each node may overlap with each other. |
|
v*****r
发帖数: 1119 | 36 Oracle 的 B-Tree 是 fully sorted,好像没有这种 partilly sorted 的
implementation. 和 "fully sorted" 比较， "partilly sorted" 应该speed up
insert new record, but will slow down query using index. |
|
l******9
发帖数: 579 | 37 I am sorting two tables on SQL.
The two tables have the same column names and types and rows numbers.
I used order by to do sorting but the two tables are different in order.
Example,
col1 INT
col2 INT
col3 INT
col4 DOUBLE PRECISION
SELECT *
FROM table1 AS t1
ORDER BY t1.col1 , t1.col2, t1.col3, t1.col4 ASC
SELECT *
FROM table2 AS t2
ORDER BY t2.col1 , t2.col2, t2.col3, t2.col4 ASC
Table1 is :
col1 col2 col3 col4
80 790 3498 18654.064361
81 589 3182 2138518.05404
80 ... 阅读全帖 |
|
p******f
发帖数: 162 | 38
you can sort c++ map by value if you want, but this would not be the
same sort carried out by the map container. I believe hash sort by
value in perl is the same case, ie. you just pass all the values to a
sort function. |
|
b***y
发帖数: 2799 | 39 ☆─────────────────────────────────────☆
babyfacenan (黑土) 于 (Wed Feb 20 01:47:45 2008) 提到:
比如说一个vector x是1,2,3,4,5
另外一个vector y是a,b,c,d,e
我想sort 1,2,3,4,5成5,4,3,2,1,同时a,b,c,d,e成e,d,c,b,a
C++里面我用sort函数来sort x w/ Comp函数f
怎样才可以同时以同样的order来sort y但是却不用Comp函数f呢？
谢谢
☆─────────────────────────────────────☆
kukutf (五脚蟹★酷酷豆腐) 于 (Wed Feb 20 02:06:42 2008) 提到:
偷懒的办法，用map做
map，建一个，然后逐个读出来。
☆─────────────────────────────────────☆
coconut (向唐僧大师学习中) 于 (Wed Feb 20 02:21:49 2008) 提到:
std: |
|
X****r
发帖数: 3557 | 40 一般来说quick sort就好，只有在要保证最坏情况也是O(n*log(n))下才用heap sort。
merge虽然需要O(n)的额外空间，但是并不需要这个空间同时在内存里。换句话说
它的输入输出都是顺序读写的，而不是随机读写的。
sort? |
|
r********n
发帖数: 7441 | 41 some thoughts based on branch and bound method: recursion + divide and conquer + merge sort
i) pick a number a, then divide n sorted linked lists into three classes:
1. min(list elements) > a
2. max(list elements) < a
3. remaining lists
ii) create three branches for them: L, M, R, if any branch contains <= 3
lists, perform merge sort, make the branch as fathomed
iii) pick any unfathomed node, perform i) ~ iii) |
|
c******n
发帖数: 4965 | 42 【 以下文字转载自 THU 讨论区 】
发信人: creation (努力自由泳50m/45sec !), 信区: THU
标 题: parsing bibliography and sorting
发信站: BBS 未名空间站 (Sun Nov 11 13:27:54 2012, 美东)
my wife was spending a lot of time sorting the bibliography of her thesis,
because her bib was obtained in plain text form, I have to parse out the
first author last name first. so I wrote this little piece of code. hope it
will be useful for someone too....
right now it fails to parse single-author bib, cuz it's difficult to
recognize a human name fr... 阅读全帖 |
|
d******e
发帖数: 2265 | 43 sorted('a', 'aa', 'bba')
Traceback (most recent call last):
File "", line 1, in
TypeError: 'str' object is not callable
>>> sorted(['a', 'aa', 'bba'])
['a', 'aa', 'bba']
算法是tim sort.
实现是进一个iterable.然后sort by key呗。就知道这么多。
你要问那么深，我认为有点装了。python这种胶水语言，知道上面怎么粘就够了。 |
|
i**********r
发帖数: 36 | 44 Do you mean pre-sort or post-sort?
Pre-sorting is none of pine's business, pine only manipulate on the emails
that are already somewhere. If you want some emails go to some assigned
folders, try write a .procmailrc file in you home directory. try
"man procmail" to see how to write one.
If you want post-sort the emails you've already read, pine CAN do that. |
|
T***B
发帖数: 137 | 45 I need to sort some very large files (30G for each) and want to estimate the
size of the temperary file created during the sorting. Is 3 or 4 times the
sorted file size large enough for the temperary file?
Since I want to know I could run how many sortings simultaneously if CPUs are
available. Thanks a lot. |
|
T***B
发帖数: 137 | 46 15 AA-1 119k118
13 BB-8 119k24
13 AB-4 22as149
11 BC-4 22as90
11 BA-1 16pk187
11 AB-1 16pk246
I need to sort the above text this way:
sort according to the first 4 characters in the
3rd column( like 119k, 12as );
then sort according to the number beginning from
the 5th character in the 3rd column (that is,
sort numerically).
the output should be:
13 BB-8 119k24
15 AA-1 119k118
11 BA-1 16pk187
11 AB-1 16pk246
11 BC-4 22as90
13 AB-4 2 |
|
b***l
发帖数: 15 | 47 I want to sort a file by first field, and if first fields are the same, then
by second filed, and so on. how to do that using command "sort" or other
command?
"sort -k 1 file" will sort according to first field.
Thanks |
|
G***i
发帖数: 150 | 48 知道numerical 范围的话 如果不是很多 可以用 bucket 或者 radix sort O(n)
complexity
一般的话 comparison sort 直接上quick sort好了 average O(nlogn) |
|
z*****u
发帖数: 3010 | 49 February 7, 2014 Depart USPS Sort Facility
February 6, 2014 , 10:16 pm Processed at USPS Origin Sort Facility
February 6, 2014 , 9:01 pm Accepted at USPS Origin Sort Facility
February 5, 2014 Electronic Shipping Info Received
md 处于这个状态 已经好几天了
有没有人有经验？ 是不是包裹凶多吉少了啊？
每次用usps，心情都很紧张。 感觉usps真是挺不靠谱的 |
|
m******9
发帖数: 968 | 50 有个关于inplace merge的题目没想明白：
two sorted arrays A and B，size 分别为m和n，需要in place merge它们，不能用
extra space
一个常见的题目是：A中有足够的空间可以另外容纳下整个B。这个题目可以用的方法是
： 用merge sort中merge的办法，都从A和B的最后一个元素开始往前scan，A[i] B[j]
哪个大，就将大的放置在A的尾端，下次比较将大的放置在次尾端，依次进行下去。O(m+n)
比如：
A: 1 3 5 _ _ _ _
B: 2 4 6 8
output: A: 1 2 3 4 5 6 8
但是另外一个变形的题目是： A就是A，没有另外的空间可以容纳B。
即：
A: 1 3 5
B: 2 4 6 8
结果应当是：
A: 1 2 3
B: 4 5 6 8
我知道的一个方法是利用selection sort的思想，每次都从A B中select一个min放在最
左端，然后下次选择sec min放在次左端，依次下去。O(n^2)
这种题目，大家有什么好办法吗？ 谢了 |
|
