代码拉取完成,页面将自动刷新
同步操作将从 编程语言算法集/C-Sharp 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
using System;
using System.Collections.Generic;
namespace Algorithms.Sorters.Comparison
{
/// <summary>
/// TODO.
/// </summary>
/// <typeparam name="T">TODO. 2.</typeparam>
public class BinaryInsertionSorter<T> : IComparisonSorter<T>
{
/// <summary>
/// Sorts array using specified comparer,
/// variant of insertion sort where binary search is used to find place for next element
/// internal, in-place, unstable,
/// time complexity: O(n^2),
/// space complexity: O(1),
/// where n - array length.
/// </summary>
/// <param name="array">Array to sort.</param>
/// <param name="comparer">Compares elements.</param>
public void Sort(T[] array, IComparer<T> comparer)
{
for (var i = 1; i < array.Length; i++)
{
var target = array[i];
var moveIndex = i - 1;
var targetInsertLocation = BinarySearch(array, 0, moveIndex, target, comparer);
Array.Copy(array, targetInsertLocation, array, targetInsertLocation + 1, i - targetInsertLocation);
array[targetInsertLocation] = target;
}
}
/// <summary>Implementation of Binary Search using an iterative approach.</summary>
/// <param name="array">
/// An array of values sorted in ascending order between the index values left and right to search
/// through.
/// </param>
/// <param name="from">Left index to search from (inclusive).</param>
/// <param name="to">Right index to search to (inclusive).</param>
/// <param name="target">The value to find placefor in the provided array.</param>
/// <param name="comparer">TODO.</param>
/// <returns>The index where to insert target value.</returns>
private static int BinarySearch(T[] array, int from, int to, T target, IComparer<T> comparer)
{
var left = from;
var right = to;
while (right > left)
{
var middle = (left + right) / 2;
var comparisonResult = comparer.Compare(target, array[middle]);
if (comparisonResult == 0)
{
return middle + 1;
}
if (comparisonResult > 0)
{
left = middle + 1;
}
else
{
right = middle - 1;
}
}
return comparer.Compare(target, array[left]) < 0 ? left : left + 1;
}
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。