a***e
发帖数: 413 | 1 请问下面两种不同 的InsertionSort的implementation有啥优劣么？我觉得都一样
哈。另外面试的时候如果问道shellsort下面那个基于InsertionSort的是不是就可以了
？发现现在要求sort linkedlist了。还在看基本算法。
void InsertionSort(vector &v)
{
int j;
for (int i = 1; i < v.size(); i++)
{
int cur = v[i];
for (j = i - 1; j >= 0 && v[j]>cur; j--)
{
v[j + 1] = v[j];
}
v[j+1] = cur;
}
}
void insertionSort2(vector &v)
{
int n = v.size()... 阅读全帖 |
|
x*******5
发帖数: 152 | 2 这个是我的题库，还有一些题没有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_... 阅读全帖 |
|
|
s********x
发帖数: 914 | 4 我找到proof啦 - quick sort worst case is nlog(n)
Data Structures
& Algorithms
in Java
Second Edition
Robert Lafore
page 725
TABLE 15.3 Comparison of Sorting Algorithms
Sort Average Worst Comparison Extra Memory
Bubble O(N2) O(N2) Poor No
Selection O(N2) O(N2) Fair No
Insertion O(N2) O(N2) Good No
Shellsort O(N3/2) O(N3/2) — No
Quicksort O(N*logN) O(N2) Good No
Mergesort O(N*logN) O(N*logN) Fair Yes
Heapsort O(N*logN) O(N*logN) Fair No |
|
