由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - InsertionSort和ShellSort
相关主题
implement hash tableA家一面
java: use vector to shuffle a deck of Card 问题EA 面筋
lc 上面4 sum的时间复杂度要求多少?M家一道题
有没有人总结过binary search是mid加减1和小于或者等于的情况分类Some coding problems from Amazon
binary search什么时候用lA家onsite,已悲剧
Amazon First Round Phone Interview请教java linkedlist问题
amazon第一轮电话要注意些什么我的面试题总结
An Old Question -- Top N Occurance Frequancems sdet onsite
相关话题的讨论汇总
话题: int话题: shellsort话题: tmp话题: cur
进入JobHunting版参与讨论
1 (共1页)
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();
for (int i = 1; i < n; i++)
{
for (int j = i; j > 0 && v[j] < v[j - 1]; j--)
{
int tmp = v[j];
v[j] = v[j - 1];
v[j - 1] = tmp;
}
}

}
void shellsort(vector &v)
{
int n = v.size(), h=1;

while (h < n / 3) h = 3 * h + 1;
while (h >= 1)
{
for (int i = h; i < n; i++)
{
for (int j = i; j >= h&& v[j] < v[j - h]; j -= h)
{
int tmp = v[j];
v[j] = v[j - h];
v[j - h] = tmp;
}
}
h = h / 3;
}
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
ms sdet onsitebinary search什么时候用l
刚弄完Amazon online test, 求blessAmazon First Round Phone Interview
Tripadvisor面筋amazon第一轮电话要注意些什么
tango家Chris电面出撒题目An Old Question -- Top N Occurance Frequance
implement hash tableA家一面
java: use vector to shuffle a deck of Card 问题EA 面筋
lc 上面4 sum的时间复杂度要求多少?M家一道题
有没有人总结过binary search是mid加减1和小于或者等于的情况分类Some coding problems from Amazon
相关话题的讨论汇总
话题: int话题: shellsort话题: tmp话题: cur