C# с использованием лямбда-выражений





using System;using System.Collections.Generic;using System.Linq; static public class Qsort { public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> list) where T : IComparable<T> { if (!list.Any()) { return Enumerable.Empty<T>(); } var pivot = list.First(); var smaller = list.Skip(1).Where(item => item.CompareTo(pivot) <= 0).QuickSort(); var larger = list.Skip(1).Where(item => item.CompareTo(pivot) > 0).QuickSort(); return smaller.Concat(new[] { pivot }).Concat(larger); } //(тоже самое, но записанное в одну строку, без объявления переменных) public static IEnumerable<T> shortQuickSort<T>(this IEnumerable<T> list) where T : IComparable<T> { return !list.Any() ? Enumerable.Empty<T>() : list.Skip(1).Where( item => item.CompareTo(list.First()) <= 0).shortQuickSort().Concat(new[] { list.First() }) .Concat(list.Skip(1).Where(item => item.CompareTo(list.First()) > 0).shortQuickSort()); } }JavaScript/* * Алгоритм быстрой сортировки * * @param data Array * @param compare function(a, b) - возвращает 0 если a=b, -1 если a<b и 1 если a>b (необязательная) * @param change function(a, i, j) - меняет местами i-й и j-й элементы массива а (необязательная) * */function qsort(data, compare, change) { var a = data, f_compare = compare, f_change = change; if (!a instanceof Array) { // Данные не являются массивом return undefined; }; if (f_compare == undefined) { // Будем использовать простую функцию (для чисел) f_compare = function(a, b) {return ((a == b) ? 0 : ((a > b) ? 1 : -1));}; }; if (f_change == undefined) { // Будем использовать простую смены (для чисел) f_change = function(a, i, j) {var c = a[i];a[i] = a[j];a[j] = c;}; }; var qs = function (l, r) { var i = l, j = r, x = a[Math.floor(Math.random()*(r-l+1))+l]; // x = a[l]; // Если нет желания использовать объект Math while(i <= j) { while(f_compare(a[i], x) == -1) {i++;} while(f_compare(a[j], x) == 1) {j--;} if(i <= j) {f_change(a, i++, j--);} }; if(l < j) {qs(l, j);} if(i < r) {qs(i, r);} }; qs(0, a.length-1);};Ruby

Вариант 1:

class Array def qsort return self.dup if size <=1 l,r = partition {|x| x <= self.first} c,l = l.partition {|x| x == self.first} l.qsort + с + r.qsort endend

Вариант 2:

class Array def partition3 a = Array.new(3) {|i| []} each do |x| a[yield(x)].push x end a end def qsort return self.dup if size <=1 c,l,r = partition3 {|x| first <=> x} l.qsort + c + r.qsort endendPython def qsort(L): if L == []: return [] return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + qsort([x for x in L[1:] if x>=L[0]])Haskell qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)Pascal

В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его — зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве — он проще и быстрее, хотя, теоретически, может быть хуже.

Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.

const max=20; { можно и больше... }type list = array[1..max] of integer; procedure quicksort(var a: list; Lo,Hi: integer); procedure sort(l,r: integer); var i,j,x,y: integer; begin i:=l; j:=r; x:=a[random(r-l+1)+l]; { x := a[(r+l) div 2]; - для выбора среднего элемента } repeat while a[i]<x do i:=i+1; { a[i] > x - сортировка по убыванию} while x<a[j] do j:=j-1; { x > a[j] - сортировка по убыванию} if i<=j then begin if a[i] > a[j] then {это условие можно убрать} {a[i] < a[j] при сортировке по убыванию} begin y:=a[i]; a[i]:=a[j]; a[j]:=y; end; i:=i+1; j:=j-1; end; until i>=j; if l<j then sort(l,j); if i<r then sort(i,r); end; {sort} begin {quicksort}; randomize; {нужно только если используется выборка случайного опорного элемента} sort(Lo,Hi)end; {quicksort}

Устойчивый вариант (требует дополнительно O(n)памяти)

const max=20; { можно и больше… }type list = array[1..max] of integer; procedure quicksort(var a: list; Lo,Hi: integer); procedure sort(l,r: integer); var i,j,x,xval,y: integer; begin i:=l; j:=r; x:=random(r-l+1)+l; xval:=a[x]; xvaln:=num[x]{ x :=(r+l) div 2; - для выбора среднего элемента } repeat while (a[i]<xval)or((a[i]=xval)and(num[i]<xvaln)) do i:=i+1; {> - сортировка по убыванию} while (xval<a[j])or((a[j]=xval)and(xvaln<num[j])) do j:=j-1; {> - сортировка по убыванию} if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; y:=num[i]; num[i]:=num[j]; num[j]:=y; i:=i+1; j:=j-1 end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r) end; {sort} begin {quicksort} randomize; {нужно только если используется выборка случайного опорного элемента} for i:=1 to n do num[i]:=i; sort(Lo,Hi)end; {quicksort}

Быстрая сортировка, нерекурсивный вариант

Нерекурсивная реализация быстрой сортировки через стек. Функции compare и change реализуются в зависимости от типа данных.

procedure quickSort(var X: itemArray; n: integer);type p_node = ^node; node = record node: integer; next: p_node end;var l,r,i,j: integer; stack: p_node; temp: item; procedure push(i: integer); var temp: p_node; begin new(temp); temp^.node:=i; temp^.next:=stack; stack:=temp end; function pop: integer; var temp: p_node; begin if stack=nil then pop:=0 else begin temp:=stack; pop:=stack^.node; stack:=stack^.next; dispose(temp) end end; begin stack:=nil; push(n-1); push(0); repeat l:=pop; r:=pop; if r-l=1 then begin if compare(X[l],X[r]) then change(X[l],X[r]) end else begin temp:=x[(l+r) div 2]; {random(r-l+1)+l} i:=l; j:=r; repeat while compare(temp,X[i]) do i:=i+1; while compare(X[j],temp) do j:=j-1; if i<=j then begin change(X[i],X[j]); i:=i+1; j:=j-1 end; until i>j; if l<j then begin push(j); push(l) end; if i<r then begin push(r); push(i) end end; until stack=nilend;Prologsplit(H, [A|X], [A|Y], Z) :- order(A, H), split(H, X, Y, Z).split(H, [A|X], Y, [A|Z]) :- not(order(A, H)), split(H, X, Y, Z).split(_, [], [], []).quicksort([], X, X).quicksort([H|T], S, X) :- split(H, T, A, B), quicksort(A, S, [H|Y]), quicksort(B, Y, X). Perl #! /usr/bin/perl use strict; sub qsort { my ($q, $s, $e) = @_; my $m = $s-1; for (my $i = $s; $i < $e; $i++) { if ($q->[$i] < $q->[$e]) { $m++; ($q->[$m], $q->[$i]) = ($q->[$i], $q->[$m]); } } $m++; ($q->[$m], $q->[$e]) = ($q->[$e], $q->[$m]); qsort($q, $s, $m-1) if $s < $m-1; qsort($q, $m+1, $e) if $m+1 < $e; } my @data = map { int(rand(10)) } (1 .. 30); print "@data\n"; qsort(\@data, 0, $#data); print "@data\n";F# let rec quicksort = function [] -> [] | h::t -> quicksort ([ for x in t when x<=h -> x]) @ [h] @ quicksort ([ for x in t when x>h -> x]);;OCaml let rec qsort l=match l with []->[] |a::b-> (qsort (List.filter ((>=) a) b) lt) @ [a] @ (qsort (List.filter ((<) a) b ));;Erlangqsort([]) -> [];qsort([H|T]) -> qsort([X || X <- T, X < H]) ++ [H] ++ qsort([X || X <- T, X >= H])].Darray qsort(array)(array _a){ alias typeof(array.init[0]) _type; array filter(bool delegate(_type) dg, array a){ array buffer = null; foreach(value; a) { if(dg(value)){ buffer ~= value; } } return buffer; } if(_a.length <= 1) { return _a; } else { return qsort( filter((_type e){ return _a[0] >= e; }, _a[1 .. $] ) ) ~ _a[0] ~ qsort( filter((_type e){ return _a[0] < e; }, _a[1 .. $] ) ); } }Scala def qsort[A <% Ordered[A]](list: List[A]): List[A] = list match { case head::tail => { qsort( tail filter(head>=) ) ::: head :: qsort( tail filter(head<) ) } case _ => list; }PHPfunction quicksort (&$array, $l, $r) { function swap (&$x, &$y) { list($x, $y) = array($y, $x); } function qsort ($left, $right) { global $array; $i = $left; $j = $right; $x = $array[($left + $right) / 2]; do { while ($array[$i] < $x) $i++; while ($array[$j] > $x) $j--; if ($i <= $j) { if ($array[$i] > $array[$j]) swap ($array[$i], $array[$j]); $i++; $j--; } } while ($i <= $j); if ($i < $right) qsort ($i, $right); if ($j > $left) qsort ($left, $j); } qsort ($l, $r);}Встроенный язык 1С

Здесь приведен алгоритм сортировки на примере объекта типа "СписокЗначений", но его можно модифицировать для работы с любым объектом, для этого нужно изменить соответствующим образом код функций "СравнитьЗначения", "ПолучитьЗначение", "УстановитьЗначение".

Функция СравнитьЗначения(Знач1, Знач2) Если Знач1>Знач2 Тогда Возврат 1; КонецЕсли; Если Знач1<Знач2 Тогда Возврат -1; КонецЕсли; Возврат 0;КонецФункции Функция ПолучитьЗначение(Список, Номер) стр=""; Возврат Список.ПолучитьЗначение(Номер, стр);КонецФункции Процедура УстановитьЗначение(Список, Номер, Значение) Список.УстановитьЗначение(Номер, Значение);КонецПроцедуры Процедура qs_0(s_arr, first, last) i = first; j = last; x = ПолучитьЗначение(s_arr, (first + last) / 2); Пока СравнитьЗначения(ПолучитьЗначение(s_arr, i), x)=-1 Цикл i=i+1; КонецЦикла; Пока СравнитьЗначения(ПолучитьЗначение(s_arr, j), x)=1 Цикл j=j-1; КонецЦикла; Если i <= j Тогда Если i < j Тогда к=ПолучитьЗначение(s_arr, i); УстановитьЗначение(s_arr, i, ПолучитьЗначение(s_arr, j)); УстановитьЗначение(s_arr, j, к); КонецЕсли; i=i+1; j=j-1; КонецЕсли; Пока i <= j Цикл Пока СравнитьЗначения(ПолучитьЗначение(s_arr, i), x)=-1 Цикл i=i+1; КонецЦикла; Пока СравнитьЗначения(ПолучитьЗначение(s_arr, j), x)=1 Цикл j=j-1; КонецЦикла; Если i <= j Тогда Если i < j Тогда к=ПолучитьЗначение(s_arr, i); УстановитьЗначение(s_arr, i, ПолучитьЗначение(s_arr, j)); УстановитьЗначение(s_arr, j, к); КонецЕсли; i=i+1; j=j-1; КонецЕсли; КонецЦикла; Если i < last Тогда qs_0(s_arr, i, last); КонецЕсли; Если first < j Тогда qs_0(s_arr, first,j); КонецЕсли;КонецПроцедуры Процедура Сортировать(Список, Размер="", Первый="", Последний="") Если ПустоеЗначение(Первый)=1 Тогда Первый=1; КонецЕсли; Если ПустоеЗначение(Последний)=1 Тогда Последний=Размер; КонецЕсли; qs_0(Список, Первый, Последний);КонецПроцедуры

 





Читайте также:
Примеры решений задач по астрономии: Фокусное расстояние объектива телескопа составляет 900 мм, а фокусное ...
Функции, которые должен выполнять администратор стоматологической клиники: На администратора стоматологического учреждения возлагается серьезная ...

Рекомендуемые страницы:


Поиск по сайту

©2015-2020 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:

Обратная связь
0.013 с.