Алгоритм сортировки, используемый 'Массивом.NET. Вид ()' метод стабильный алгоритм?
Еще одна возможность иметь в виду использование отношения «has-a», иначе «реализовано в терминах» или «композиции». Иногда это более чистый и более гибкий способ структурирования вещей, чем использование наследования «is-a».
Возможно, логично сказать, что у собаки и кошки «есть» питомец, но он избегает распространенных ошибок множественного наследования:
public class Pet
{
void Bathe();
void Train(Trick t);
}
public class Dog
{
private Pet pet;
public void Bathe() { pet.Bathe(); }
public void Train(Trick t) { pet.Train(t); }
}
public class Cat
{
private Pet pet;
public void Bathe() { pet.Bathe(); }
public void Train(Trick t) { pet.Train(t); }
}
Да, этот пример показывает, что существует много дублирования кода и отсутствие элегантности, участвующих в этом. Но стоит также признаться, что это помогает удержать собаку и кошку, отделяемую от класса Pet (в том, что «Собака и кошка» не имеют доступа к частным членам Pet), и она оставляет место для собак и кошек, чтобы наследовать что-то еще, - возможно, класс Млекопитающих.
Композиция предпочтительнее, когда не требуется никакого частного доступа, и вам не нужно ссылаться на Dog и Cat, используя общие рекомендации / указатели Pet. Интерфейсы дают вам общую справочную возможность и могут помочь сократить объем текста вашего кода, но они также могут запутывать вещи, когда они плохо организованы. Наследование полезно, когда вам нужен доступ к частному члену, и при его использовании вы обязуетесь максимально сочетать свои классы «Собаки и кошки» с классом вашего любимца, что является высокой стоимостью оплаты.
Между наследованием, составом , и интерфейсов нет ни одного способа, который бы всегда был прав, и это помогает рассмотреть, как все три варианта могут использоваться в гармонии. Из трех наследований обычно является вариант, который следует использовать наименее часто.
4 ответа
От MSDN:
Эта реализация выполняет нестабильный вид; то есть, если два элемента равны, их порядок не мог бы быть сохранен. Напротив, стабильный вид сохраняет порядок элементов, которые равны.
вид использует самосозерцательный вид. (Quicksort в версии 4.0 и ранее платформы.NET).
при необходимости в стабильном виде можно использовать Счетный. OrderBy.
Поскольку другие ответы указали, Массив. Вид не стабилен. Однако методы LINQ OrderBy (и OrderByDescending и т.д.) стабильны, который может быть очень полезным.
Добавление к ответ Rasmus Faber †¦
Сортировка в LINQ, через Счетный. OrderBy и Счетный. ThenBy, стабильная реализация вида, которая может использоваться в качестве альтернативы Массив. Вид . От [1 110] Счетный. Документация OrderBy в MSDN:
Этот метод выполняет стабильный вид; то есть, если ключи двух элементов равны, порядок элементов сохраняется. Напротив, нестабильный вид не сохраняет порядок элементов, которые имеют тот же ключ.
кроме того, любая нестабильная реализация вида, как этот Array.Sort, может быть стабилизирована при помощи положения элементов в исходной последовательности или массиве как дополнительный ключ для служения в качестве дополнительного времени. Ниже одна такая реализация, как универсальный дополнительный метод на любом одно-мерном массиве и который поворачивается Array.Sort в стабильный вид:
using System;
using System.Collections.Generic;
public static class ArrayExtensions {
public static void StableSort<T>(this T[] values, Comparison<T> comparison) {
var keys = new KeyValuePair<int, T>[values.Length];
for (var i = 0; i < values.Length; i++)
keys[i] = new KeyValuePair<int, T>(i, values[i]);
Array.Sort(keys, values, new StabilizingComparer<T>(comparison));
}
private sealed class StabilizingComparer<T> : IComparer<KeyValuePair<int, T>>
{
private readonly Comparison<T> _comparison;
public StabilizingComparer(Comparison<T> comparison) {
_comparison = comparison;
}
public int Compare(KeyValuePair<int, T> x,
KeyValuePair<int, T> y) {
var result = _comparison(x.Value, y.Value);
return result != 0 ? result : x.Key.CompareTo(y.Key);
}
}
}
Ниже пример программы с помощью StableSort сверху:
static class Program
{
static void Main()
{
var unsorted = new[] {
new Person { BirthYear = 1948, Name = "Cat Stevens" },
new Person { BirthYear = 1955, Name = "Kevin Costner" },
new Person { BirthYear = 1952, Name = "Vladimir Putin" },
new Person { BirthYear = 1955, Name = "Bill Gates" },
new Person { BirthYear = 1948, Name = "Kathy Bates" },
new Person { BirthYear = 1956, Name = "David Copperfield" },
new Person { BirthYear = 1948, Name = "Jean Reno" },
};
Array.ForEach(unsorted, Console.WriteLine);
Console.WriteLine();
var unstable = (Person[]) unsorted.Clone();
Array.Sort(unstable, (x, y) => x.BirthYear.CompareTo(y.BirthYear));
Array.ForEach(unstable, Console.WriteLine);
Console.WriteLine();
var stable = (Person[]) unsorted.Clone();
stable.StableSort((x, y) => x.BirthYear.CompareTo(y.BirthYear));
Array.ForEach(stable, Console.WriteLine);
}
}
sealed class Person
{
public int BirthYear { get; set; }
public string Name { get; set; }
public override string ToString() {
return string.Format(
"{{ BirthYear = {0}, Name = {1} }}",
BirthYear, Name);
}
}
Ниже вывод из примера программы выше (работа машины с Windows Vista SP1 и Платформой.NET 3,5 установленные SP1):
{ BirthYear = 1948, Name = Cat Stevens }
{ BirthYear = 1955, Name = Kevin Costner }
{ BirthYear = 1952, Name = Vladimir Putin }
{ BirthYear = 1955, Name = Bill Gates }
{ BirthYear = 1948, Name = Kathy Bates }
{ BirthYear = 1956, Name = David Copperfield }
{ BirthYear = 1948, Name = Jean Reno }
{ BirthYear = 1948, Name = Jean Reno }
{ BirthYear = 1948, Name = Kathy Bates }
{ BirthYear = 1948, Name = Cat Stevens }
{ BirthYear = 1952, Name = Vladimir Putin }
{ BirthYear = 1955, Name = Bill Gates }
{ BirthYear = 1955, Name = Kevin Costner }
{ BirthYear = 1956, Name = David Copperfield }
{ BirthYear = 1948, Name = Cat Stevens }
{ BirthYear = 1948, Name = Kathy Bates }
{ BirthYear = 1948, Name = Jean Reno }
{ BirthYear = 1952, Name = Vladimir Putin }
{ BirthYear = 1955, Name = Kevin Costner }
{ BirthYear = 1955, Name = Bill Gates }
{ BirthYear = 1956, Name = David Copperfield }
Нет, это не :
Этот метод использует алгоритм QuickSort. Эта реализация выполняет нестабильный вид