为什么插入排序总是跳动在此实现归并排序？

编程入门行业动态更新时间:2024-10-20 11:24:29

本文介绍了为什么插入排序总是跳动在此实现归并排序？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

我不明白：为什么我插入排序实施殴打，每次归并排序，任何规模的 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