Я написал базовый класс связанных списков в С#. Он имеет объект Node, который (очевидно) представляет каждый Node в списке.
В коде не используется IEnumerable, однако я могу реализовать функцию сортировки? Язык, который я использую, - это С#. Есть ли пример этого в С#?
Я работаю над этим образцом:
Спасибо
Вот связанный список с методами quicksort и mergesort, написанными в функциональном стиле:
class List
{
public int item;
public List rest;
public List(int item, List rest)
{
this.item = item;
this.rest = rest;
}
// helper methods for quicksort
public static List Append(List xs, List ys)
{
if (xs == null) return ys;
else return new List(xs.item, Append(xs.rest, ys));
}
public static List Filter(Func<int,bool> p, List xs)
{
if (xs == null) return null;
else if (p(xs.item)) return new List(xs.item, Filter(p, xs.rest));
else return Filter(p, xs.rest);
}
public static List QSort(List xs)
{
if (xs == null) return null;
else
{
int pivot = xs.item;
List less = QSort(Filter(x => x <= pivot, xs.rest));
List more = QSort(Filter(x => x > pivot, xs.rest));
return Append(less, new List(pivot, more));
}
}
// Helper methods for mergesort
public static int Length(List xs)
{
if (xs == null) return 0;
else return 1 + Length(xs.rest);
}
public static List Take(int n, List xs)
{
if (n == 0) return null;
else return new List(xs.item, Take(n - 1, xs.rest));
}
public static List Drop(int n, List xs)
{
if (n == 0) return xs;
else return Drop(n - 1, xs.rest);
}
public static List Merge(List xs, List ys)
{
if (xs == null) return ys;
else if (ys == null) return xs;
else if (xs.item <= ys.item) return new List(xs.item, Merge(xs.rest, ys));
else return new List(ys.item, Merge(xs, ys.rest));
}
public static List MSort(List xs)
{
if (Length(xs) <= 1) return xs;
else
{
int len = Length(xs) / 2;
List left = MSort(Take(len, xs));
List right = MSort(Drop(len, xs));
return Merge(left, right);
}
}
public static string Show(List xs)
{
if(xs == null) return "";
else return xs.item.ToString() + " " + Show(xs.rest);
}
}
Бонус: heapsort (с использованием функциональной спаривающей кучи).
class List
{
// ...
public static Heap List2Heap(List xs)
{
if (xs == null) return null;
else return Heap.Merge(new Heap(null, xs.item, null), List2Heap(xs.rest));
}
public static List HSort(List xs)
{
return Heap.Heap2List(List2Heap(xs));
}
}
class Heap
{
Heap left;
int min;
Heap right;
public Heap(Heap left, int min, Heap right)
{
this.left = left;
this.min = min;
this.right = right;
}
public static Heap Merge(Heap a, Heap b)
{
if (a == null) return b;
if (b == null) return a;
Heap smaller = a.min <= b.min ? a : b;
Heap larger = a.min <= b.min ? b : a;
return new Heap(smaller.left, smaller.min, Merge(smaller.right, larger));
}
public static Heap DeleteMin(Heap a)
{
return Merge(a.left, a.right);
}
public static List Heap2List(Heap a)
{
if (a == null) return null;
else return new List(a.min, Heap2List(DeleteMin(a)));
}
}
Для реального использования вы хотите переписать вспомогательные методы без использования рекурсии и, возможно, использовать измененный список, например встроенный.
Как использовать:
List xs = new List(4, new List(2, new List(3, new List(1, null))));
Console.WriteLine(List.Show(List.QSort(xs)));
Console.WriteLine(List.Show(List.MSort(xs)));
Console.WriteLine(List.Show(List.HSort(xs)));
Запрошена версия на месте. Здесь очень быстрая реализация. Я написал этот код сверху вниз, не ища возможности сделать код лучше, т.е. Каждая строка - первая строка, которая пришла на ум. Это очень уродливо, потому что я использовал null как пустой список:) Отступ несовместим и т.д.
Кроме того, я проверил этот код только на одном примере:
MList ys = new MList(4, new MList(2, new MList(3, new MList(1, null))));
MList.QSortInPlace(ref ys);
Console.WriteLine(MList.Show(ys));
Волшебно это сработало в первый раз! Я уверен, что этот код содержит ошибки. Не держите меня в ответе.
class MList
{
public int item;
public MList rest;
public MList(int item, MList rest)
{
this.item = item;
this.rest = rest;
}
public static void QSortInPlace(ref MList xs)
{
if (xs == null) return;
int pivot = xs.item;
MList pivotNode = xs;
xs = xs.rest;
pivotNode.rest = null;
// partition the list into two parts
MList smaller = null; // items smaller than pivot
MList larger = null; // items larger than pivot
while (xs != null)
{
var rest = xs.rest;
if (xs.item < pivot) {
xs.rest = smaller;
smaller = xs;
} else {
xs.rest = larger;
larger = xs;
}
xs = rest;
}
// sort the smaller and larger lists
QSortInPlace(ref smaller);
QSortInPlace(ref larger);
// append smaller + [pivot] + larger
AppendInPlace(ref pivotNode, larger);
AppendInPlace(ref smaller, pivotNode);
xs = smaller;
}
public static void AppendInPlace(ref MList xs, MList ys)
{
if(xs == null){
xs = ys;
return;
}
// find the last node in xs
MList last = xs;
while (last.rest != null)
{
last = last.rest;
}
last.rest = ys;
}
public static string Show(MList xs)
{
if (xs == null) return "";
else return xs.item.ToString() + " " + Show(xs.rest);
}
}
Конечно, вы можете реализовать функцию сортировки с использованием простого связанного списка. Merge sort может быть подходящим алгоритмом, чтобы попробовать, это довольно просто.
Простейшим вариантом является, вероятно, извлечение данных, сортировка их в механизме, который уже поддерживает сортировку (массивы, List<T> или IEnumerable<T> через LINQ) и перестроить связанный список с отсортированными данными.
Если вы хотите написать свой собственный алгоритм сортировки, вы можете найти Comparer<T>.Default полезным (при условии, что вы используете дженерики). Это должно позволить вам сравнить любые элементы IComparable<T> или IComparable.
Отметим, что .NET уже включает LinkedList<T> и т.д.; если это только для обучения и т.д., тогда отлично; -p
Это может быть не лучшее решение, но это так просто, как я могу придумать. Если кто-нибудь может подумать о чем-то более простом, но все же быстро, я бы хотел его услышать.
Извините, что это С++ он должен перевести.
List * SortList(List * p_list)
{
if(p_list == NULL || p_list->next == NULL)
return p_list;
List left, right;
List * piviot = p_list;
List * piviotEnd = piviot;
List * next = p_list->next;
do
{
p_list = next;
next = next->next;
//FIGURE OUT WHICH SIDE I'M ADDING TO.
if(p_list->data > piviot->data )
right.InsertNode(p_list);
else if(p_list->data < piviot->data)
left.InsertNode(p_list);
else
{ //we put this in it own list because it doesn't need to be sorted
piviotEnd->next = p_list;
piviotEnd= p_list;
}
}while(next);
//now left contains values < piviot and more contains all the values more
left.next = SortList(left.next);
right.next = SortList(right.next);
//add the piviot to the list then add the rigth list to the full list
left.GetTail()->next = piviot;
piviotEnd->next = right.next;
return left.next;
}
Некоторые люди (включая меня), возможно, захотели отсортировать LinkedList<T> из библиотеки .net.
Простым способом является использование Linq, сортировка и, наконец, создание нового связанного списка. но это создает мусор. для небольших коллекций это не будет проблемой, но для больших коллекций это может быть не так эффективно.
для людей, которые хотят некоторую степень оптимизации, вот общая реализация быстрой сортировки на месте для дважды связанного списка .net.
эта реализация не разбивается/объединяется, а проверяет узлы для границ каждой рекурсии.
/// <summary>
/// in place linked list sort using quick sort.
/// </summary>
public static void QuickSort<T>(this LinkedList<T> linkedList, IComparer<T> comparer)
{
if (linkedList == null || linkedList.Count <= 1) return; // there is nothing to sort
SortImpl(linkedList.First, linkedList.Last, comparer);
}
private static void SortImpl<T>(LinkedListNode<T> head, LinkedListNode<T> tail, IComparer<T> comparer)
{
if (head == tail) return; // there is nothing to sort
void Swap(LinkedListNode<T> a, LinkedListNode<T> b)
{
var tmp = a.Value;
a.Value = b.Value;
b.Value = tmp;
}
var pivot = tail;
var node = head;
while (node.Next != pivot)
{
if (comparer.Compare(node.Value, pivot.Value) > 0)
{
Swap(pivot, pivot.Previous);
Swap(node, pivot);
pivot = pivot.Previous; // move pivot backward
}
else node = node.Next; // move node forward
}
if (comparer.Compare(node.Value, pivot.Value) > 0)
{
Swap(node, pivot);
pivot = node;
}
// pivot location is found, now sort nodes below and above pivot.
// if head or tail is equal to pivot we reached boundaries and we should stop recursion.
if (head != pivot) SortImpl(head, pivot.Previous, comparer);
if (tail != pivot) SortImpl(pivot.Next, tail, comparer);
}
for(int i=0; i<counter;i++)
{
while(current.next!=null)
{
if(current.elemen>current.next.element)
{
Swap(current.elment,current.next.element);
}
current=current.next;
}
}
счетчик приращений при добавлении или вставке элементов в связанные списки.
Если вы действительно хотите использовать тот факт, что используете связанный список, в отличие от работы с ним, я бы предложил сортировку вставки.
Обычно сортировка вставки не очень эффективна - O(n^2) в худшем случае, но со связанным списком это можно улучшить до O(n log n)
псевдо:
for i in range (1,n):
item = arr[i]
location = binary_search(l=root, r=i, value=item.val) // O(log i)
insert_item_before(arr[location], item) // O(1)
В регулярном алгоритме часть вставки принимает O(i), потому что нам может потребоваться сдвинуть все элементы, которые больше, чем item. потому что связанный список позволяет нам вставлять без сдвига, мы можем искать местоположение с двоичным поиском, и поэтому вставляемая часть принимает только O(log i)
note: обычно сортировка вставки имеет O(n) производительность в лучшем случае (если массив отсортирован). К сожалению, это не так, потому что бинарный поиск всегда выполняет шаги O(log n).
public LinkedListNode<int> Sort2(LinkedListNode<int> head, int count)
{
var cur = head;
var prev = cur;
var min = cur;
var minprev = min;
LinkedListNode<int> newHead = null;
LinkedListNode<int> newTail = newHead;
for (int i = 0; i < count; i++)
{
cur = head;
min = cur;
minprev = min;
while (cur != null)
{
if (cur.Value < min.Value)
{
min = cur;
minprev = prev;
}
prev = cur;
cur = cur.Next;
}
if (min == head)
head = head.Next;
else if (min.Next == null)
minprev.Next = null;
else
minprev.Next = minprev.Next.Next;
if (newHead != null)
{
newTail.Next = min;
newTail = newTail.Next;
}
else
{
newHead = min;
newTail = newHead;
}
}
return newHead;
}