为什么插入排序总是跳动在此实现归并排序？ [英] Why is insertion sort always beating merge sort in this implementation?
本文介绍了为什么插入排序总是跳动在此实现归并排序？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我不明白：为什么我插入排序实施殴打，每次归并排序，任何规模的 N
公开名单＆LT;的Int32＆GT; InsertionSort（名单＆LT;的Int32＆GT;元素，布尔升=真）
{
对于（的Int32 J = 1; J＆LT; elements.Count; J ++）
{
INT32键=因素[J]。
INT32 I =的J - 1;
而（ⅰ＆GT; = 0＆安培;及（元素[I] .CompareTo（键）大于0）==升序）
元素[I + 1] =元素[我 - ]。
元素[I + 1] =键;
}
返回元素;
}
公开名单＆LT;的Int32＆GT;归并（名单＆LT;的Int32＆GT;元素，布尔升=真）
{
排序（元素，0，elements.Count - 1）;
返回元素;
}
私人无效归并（名单＆LT;的Int32＆GT;元素的Int32在startIndex，的Int32计数）
{
如果（在startIndex＆LT;计数）
{
INT32一半=（在startIndex +计数）.Divide（2 RoundMethod.Floor）;
排序（元素，在startIndex一半）;
排序（元素，半数+ 1，计数）;
合并（元素，在startIndex，一半，算）;
}
}
公开名单＆LT;的Int32＆GT;合并（名单＆LT;的Int32＆GT;元素的Int32下界，的Int32一半的Int32上界）
{
的Int32 I = 0;
的Int32 J = 0;
INT32 lowerElementsCount =半 - 下界+ 1;
INT32 upperElementsCount =上界 - 半;
名单＆LT;的Int32＆GT;左=新的名单，其中，的Int32＆GT;（）;
而（I＆LT; lowerElementsCount）
left.Add（元素[下界+ I +]）;
名单＆LT;的Int32＆GT;右=新的名单，其中，的Int32＆GT;（）;
而（J＆LT; upperElementsCount）
right.Add（元素[半数+ J + + + 1]）;
left.Add（Int32.MaxValue）;
right.Add（Int32.MaxValue）;
I = 0;
J = 0;
对于（INT K =下界; K＆LT; =上界; k ++）
如果（左[1] - =右[J]。）
{
元素[K] =左[I]
我++;
}
其他
{
元素[K] =右[J]。
J ++;
}
返回元素;
}
下面是我的结果：
分拣1个元素
合并排序：花费时间：0毫秒（1513蜱）
插入排序：花费时间：0毫秒（1247蜱）
分拣10种元素
合并排序：花费时间：1毫秒（2710蜱）
插入排序：花费时间：0毫秒（3蜱）
分拣100个元素
合并排序：花费时间：0毫秒（273蜱）
插入排序：花费时间：0毫秒（11刻度）
分拣1000个元素
合并排序：花费时间：1毫秒（3142蜱）
插入排序：花费时间：0毫秒（72刻度）
分拣10000元素
合并排序：执行时间：18毫秒（30491蜱）
插入排序：花费时间：0毫秒（882蜱）
而code来进行测试：
静态无效的主要（字串[] args）
{
的for（int i = 1; I＆LT; 100000; I * = 10）
{
名单＆LT;的Int32＆GT;元素= GetFilledList（I，0，Int32.MaxValue，假）;
Console.WriteLine（排序{0}元素，elements.Count）;
秒表SW =新的秒表（）;
//合并排序
sw.Start（）;
新归并（）排序（元素）。
sw.Stop（）;
Console.WriteLine（合并排序：花费时间：{0}毫秒（{1}蜱），sw.ElapsedMilliseconds，sw.ElapsedTicks）;
//插入排序
sw.Restart（）;
新InsertionSort（）排序（元素）。
sw.Stop（）;
Console.WriteLine（插入分页：花费时间：{0}毫秒（{1}蜱），sw.ElapsedMilliseconds，sw.ElapsedTicks）;
Console.WriteLine（）;
}
Console.ReadKey（）;
}
在万一有人想知道我是从算法导论这些算法，托马斯H Cormen（作者）查尔斯E. Leiserson（作者），罗纳德·L.维斯特（作者），克利福德·斯坦（作者）
编辑：
静态列表＆LT;的Int32＆GT; GetFilledList（的Int32量的Int32下界，的Int32上界，布尔mayRepeat =真）
{
名单＆LT;的Int32＆GT;数=新的名单，其中，的Int32＆GT;（）;
随机R =新的随机（）;
的for（int i = 0; I＆LT;数量;我++）
{
INT32 NUMERO = r.Next（下界，上界）;
而（mayRepeat＆安培;！＆安培; numbers.Contains（NUMERO））
NUMERO = r.Next（下界，上界）;
numbers.Add（NUMERO）;
}
返回的数字;
}
解决方案
因为，合并排序后，在元素中的对象已经排序。做的是另
元素= GetFilledList（I，0，Int32.MaxValue，假）;
在
sw.Restart（）;
I don't understand: why is my insertion sort implementation beating merge sort every time, for any size of n?
public List<Int32> InsertionSort(List<Int32> elements, Boolean ascending = true)
{
for (Int32 j = 1; j < elements.Count; j++)
{
Int32 key = elements[j];
Int32 i = j - 1;
while (i >= 0 && (elements[i].CompareTo(key) > 0) == ascending)
elements[i + 1] = elements[i--];
elements[i + 1] = key;
}
return elements;
}
public List<Int32> MergeSort(List<Int32> elements, Boolean ascending = true)
{
Sort(elements, 0, elements.Count - 1);
return elements;
}
private void MergeSort(List<Int32> elements, Int32 startIndex, Int32 count)
{
if(startIndex < count)
{
Int32 half = (startIndex + count).Divide(2, RoundMethod.Floor);
Sort(elements, startIndex, half);
Sort(elements, half + 1, count);
Merge(elements, startIndex, half, count);
}
}
public List<Int32> Merge(List<Int32> elements, Int32 lowerBound, Int32 half, Int32 upperBound)
{
Int32 i = 0;
Int32 j = 0;
Int32 lowerElementsCount = half - lowerBound + 1;
Int32 upperElementsCount = upperBound - half;
List<Int32> left = new List<Int32>();
while (i < lowerElementsCount)
left.Add(elements[lowerBound + i++]);
List<Int32> right = new List<Int32>();
while (j < upperElementsCount)
right.Add(elements[half + j++ + 1]);
left.Add(Int32.MaxValue);
right.Add(Int32.MaxValue);
i = 0;
j = 0;
for (int k = lowerBound; k <= upperBound; k++)
if (left[i] <= right[j])
{
elements[k] = left[i];
i++;
}
else
{
elements[k] = right[j];
j++;
}
return elements;
}
Here are my results:
SORTING 1 ELEMENTS
MERGE-SORT: TIME SPENT: 0ms (1513 ticks)
INSERTION-SORT: TIME SPENT: 0ms (1247 ticks)
SORTING 10 ELEMENTS
MERGE-SORT: TIME SPENT: 1ms (2710 ticks)
INSERTION-SORT: TIME SPENT: 0ms (3 ticks)
SORTING 100 ELEMENTS
MERGE-SORT: TIME SPENT: 0ms (273 ticks)
INSERTION-SORT: TIME SPENT: 0ms (11 ticks)
SORTING 1000 ELEMENTS
MERGE-SORT: TIME SPENT: 1ms (3142 ticks)
INSERTION-SORT: TIME SPENT: 0ms (72 ticks)
SORTING 10000 ELEMENTS
MERGE-SORT: TIME SPENT: 18ms (30491 ticks)
INSERTION-SORT: TIME SPENT: 0ms (882 ticks)
And the code for testing:
static void Main(string[] args)
{
for (int i = 1; i < 100000; i*=10)
{
List<Int32> elements = GetFilledList(i, 0, Int32.MaxValue, false);
Console.WriteLine("SORTING {0} ELEMENTS", elements.Count);
Stopwatch sw = new Stopwatch();
//MERGE SORT
sw.Start();
new MergeSort().Sort(elements);
sw.Stop();
Console.WriteLine("MERGE-SORT: TIME SPENT: {0}ms ({1} ticks)", sw.ElapsedMilliseconds, sw.ElapsedTicks);
//INSERTION SORT
sw.Restart();
new InsertionSort().Sort(elements);
sw.Stop();
Console.WriteLine("INSERTION-SORT: TIME SPENT: {0}ms ({1} ticks)", sw.ElapsedMilliseconds, sw.ElapsedTicks);
Console.WriteLine();
}
Console.ReadKey();
}
In case anyone wondering I got these algorithms from Introduction to Algorithms, Thomas H. Cormen (Author), Charles E. Leiserson (Author), Ronald L. Rivest (Author), Clifford Stein (Author)
EDIT:
static List<Int32> GetFilledList(Int32 quantity, Int32 lowerBound, Int32 upperBound, Boolean mayRepeat = true)
{
List<Int32> numbers = new List<Int32>();
Random r = new Random();
for (int i = 0; i < quantity; i++)
{
Int32 numero = r.Next(lowerBound, upperBound);
while(!mayRepeat && numbers.Contains(numero))
numero = r.Next(lowerBound, upperBound);
numbers.Add(numero);
}
return numbers;
}
解决方案
because, after the merge sort, the objects in elements are already sorted. do another
elements = GetFilledList(i, 0, Int32.MaxValue, false);
before the
sw.Restart();
这篇关于为什么插入排序总是跳动在此实现归并排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
