InsertionSort和ShellSort# JobHunting - 待字闺中
a*e
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;
}
}
哈。另外面试的时候如果问道shellsort下面那个基于InsertionSort的是不是就可以了
？发现现在要求sort linkedlist了。还在看基本算法。
void InsertionSort(vector
{
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
{
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
{
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;
}
}