演算法實現/排序/快速排序
function QuickSort(Array, Left, Right)
var
L2, R2, PivotValue
begin
Stack.Push(Left, Right); // pushes Left, and then Right, on to a stack
while not Stack.Empty do
begin
Stack.Pop(Left, Right); // pops 2 values, storing them in Right and then Left
repeat
PivotValue := Array[(Left + Right) div 2];
L2 := Left;
R2 := Right;
repeat
while Array[L2] < PivotValue do // scan left partition
L2 := L2 + 1;
while Array[R2] > PivotValue do // scan right partition
R2 := R2 - 1;
if L2 <= R2 then
begin
if L2 != R2 then
Swap(Array[L2], Array[R2]); // swaps the data at L2 and R2
L2 := L2 + 1;
R2 := R2 - 1;
end;
until L2 >= R2;
if R2 - Left > Right - L2 then // is left side piece larger?
begin
if Left < R2 then
Stack.Push(Left, R2);
Left := L2;
end;
else
begin
if L2 < Right then // if left side isn't, right side is larger
Stack.Push(L2, Right);
Right := R2;
end;
until Left >= Right;
end;
end;
使用PAR子句將作業分解成多個執行緒的ALGOL 68中的快速排序。
MODE DATA = INT;
PROC partition =(REF [] DATA array, PROC (REF DATA, REF DATA) BOOL cmp)INT: (
INT begin:=LWB array;
INT end:=UPB array;
WHILE begin < end DO
WHILE begin < end DO
IF cmp(array[begin], array[end]) THEN
DATA tmp=array[begin];
array[begin]:=array[end];
array[end]:=tmp;
GO TO break while decr end
FI;
end -:= 1
OD;
break while decr end: SKIP;
WHILE begin < end DO
IF cmp(array[begin], array[end]) THEN
DATA tmp=array[begin];
array[begin]:=array[end];
array[end]:=tmp;
GO TO break while incr begin
FI;
begin +:= 1
OD;
break while incr begin: SKIP
OD;
begin
);
PROC qsort=(REF [] DATA array, PROC (REF DATA, REF DATA) BOOL cmp)VOID: (
IF LWB array < UPB array THEN
INT i := partition(array, cmp);
PAR ( # remove PAR for single threaded sort #
qsort(array[:i-1], cmp),
qsort(array[i+1:], cmp)
)
FI
);
PROC cmp=(REF DATA a,b)BOOL: a>b;
main:(
[]DATA const l=(5,4,3,2,1);
[UPB const l]DATA l:=const l;
qsort(l,cmp);
printf(($g(3)$,l))
)AppleScript
[編輯 | 編輯原始碼]這是一個使用C.A.R. Hoare演算法的基本實現，其中樞紐位於中間（有時稱為二進位制或二分排序）。使用指令碼物件來儲存列表使此版本比以前提出的版本快約10倍（對於包含1000個字串的列表）。此外，“left”和“right”是關鍵字，可能並不總是按預期執行。還可以根據要排序的資料透過隨機選擇樞紐或增加其數量來進行改進。
on QuickSort(aList, Le, Ri)
--> Sorts list of of simple types such as reals, integers, strings or even booleans
script Sal --> script object aList
property Array : aList
end script
set [i, j] to [Le, Ri]
set v to Sal's Array's item ((Le + Ri) div 2) --> pivot in middle (as C.A.R. Hoare's algorithm)
repeat while j > i
repeat while Sal's Array's item i < v
set i to i + 1
end repeat
repeat while Sal's Array's item j > v
set j to j - 1
end repeat
if not i > j then
tell (a reference to Sal's Array) to set [item i, item j] to [item j, item i] --> let's swap
set [i, j] to [i + 1, j - 1]
end if
end repeat
if Le < j then QuickSort(Sal's Array, Le, j)
if Ri > i then QuickSort(Sal's Array, i, Ri)
end QuickSort
這是一個簡單的實現。當然可以想出一個更有效的實現，但它可能不如這個清晰。
on sort( array, left, right )
set i to left
set j to right
set v to item ( ( left + right ) div 2 ) of array -- pivot
repeat while ( j > i )
repeat while ( item i of array < v )
set i to i + 1
end repeat
repeat while ( item j of array > v )
set j to j - 1
end repeat
if ( not i > j ) then
tell array to set { item i, item j } to { item j, item i } -- swap
set i to i + 1
set j to j - 1
end if
end repeat
if ( left < j ) then sort( array, left, j )
if ( right > i ) then sort( array, i, right )
end sort
此ARM RISC組合語言實現用於對32位整數陣列進行排序，演示了快速排序如何充分利用典型機器指令集的暫存器模型和功能（請注意，此特定實現不符合標準呼叫約定，並且可能使用超過O(log n)的空間）
qsort: @ Takes three parameters:
@ a: Pointer to base of array a to be sorted (arrives in r0)
@ left: First of the range of indexes to sort (arrives in r1)
@ right: One past last of range of indexes to sort (arrives in r2)
@ This function destroys: r1, r2, r3, r5, r7
stmfd sp!, {r4, r6, lr} @ Save r4 and r6 for caller
mov r6, r2 @ r6 <- right
qsort_tailcall_entry:
sub r7, r6, r1 @ If right - left <= 1 (already sorted),
cmp r7, #1
ldmlefd sp!, {r4, r6, pc} @ Return, restoring r4 and r6
ldr r7, [r0, r1, asl #2] @ r7 <- a[left], gets pivot element
add r2, r1, #1 @ l <- left + 1
mov r4, r6 @ r <- right
partition_loop:
ldr r3, [r0, r2, asl #2] @ r3 <- a[l]
cmp r3, r7 @ If a[l] <= pivot_element,
addle r2, r2, #1 @ ... increment l, and
ble partition_test @ ... continue to next iteration.
sub r4, r4, #1 @ Otherwise, decrement r,
ldr r5, [r0, r4, asl #2] @ ... and swap a[l] and a[r].
str r5, [r0, r2, asl #2]
str r3, [r0, r4, asl #2]
partition_test:
cmp r2, r4 @ If l < r,
blt partition_loop @ ... continue iterating.
partition_finish:
sub r2, r2, #1 @ Decrement l
ldr r3, [r0, r2, asl #2] @ Swap a[l] and pivot
str r3, [r0, r1, asl #2]
str r7, [r0, r2, asl #2]
bl qsort @ Call self recursively on left part,
@ with args a (r0), left (r1), r (r2),
@ also preserves r4 and r6
mov r1, r4
b qsort_tailcall_entry @ Tail-call self on right part,
@ with args a (r0), l (r1), right (r6)
該呼叫為每個遞迴呼叫生成3個字的堆疊，並且能夠利用其自身行為的知識。更有效的實現將透過更有效的方法對小範圍進行排序。如果需要符合標準呼叫約定的實現，則可以為對上述函式的初始呼叫編寫一個簡單的包裝器，以儲存相應的暫存器。
這是一個基於AppleScript示例的簡單實現。當然可以想出一個更有效的實現，但它可能不如這個清晰。
Func sort( ByRef $array, $left, $right )
$i = $left
$j = $right
$v = $array[Round( ( $left + $right ) / 2 ,0)]
While ( $j > $i )
While ($array[$i] < $v )
$i = $i + 1
WEnd
While ( $array[$j] > $v )
$j = $j - 1
WEnd
If ( NOT ($i > $j) ) then
swap($array[$i], $array[$j])
$i = $i + 1
$j = $j - 1
EndIf
WEnd
if ( $left < $j ) then sort( $array, $left, $j )
if ( $right > $i ) then sort( $array, $i, $right )
EndFunc
核心實現部分中的實現僅限於整數陣列。以下實現適用於任何資料型別，前提是已知其大小和比較函式。這類似於ISO/POSIX相容的C標準庫提供的功能。
#include <stdlib.h>
#include <stdio.h>
static void swap(void *x, void *y, size_t l) {
char *a = x, *b = y, c;
while(l--) {
c = *a;
*a++ = *b;
*b++ = c;
}
}
static void sort(char *array, size_t size, int (*cmp)(void*,void*), int begin, int end) {
if (end > begin) {
void *pivot = array + begin;
int l = begin + size;
int r = end;
while(l < r) {
if (cmp(array+l,pivot) <= 0) {
l += size;
} else if ( cmp(array+r, pivot) > 0 ) {
r -= size;
} else if ( l < r ) {
swap(array+l, array+r, size);
}
}
l -= size;
swap(array+begin, array+l, size);
sort(array, size, cmp, begin, l);
sort(array, size, cmp, r, end);
}
}
void qsort(void *array, size_t nitems, size_t size, int (*cmp)(void*,void*)) {
if (nitems > 0) {
sort(array, size, cmp, 0, (nitems-1)*size);
}
}
typedef int type;
int type_cmp(void *a, void *b){ return (*(type*)a)-(*(type*)b); }
int main(void){ /* simple test case for type=int */
int num_list[]={5,4,3,2,1};
int len=sizeof(num_list)/sizeof(type);
char *sep="";
int i;
qsort(num_list,len,sizeof(type),type_cmp);
printf("sorted_num_list={");
for(i=0; i<len; i++){
printf("%s%d",sep,num_list[i]);
sep=", ";
}
printf("};\n");
return 0;
}
結果
sorted_num_list={1, 2, 3, 4, 5};
這是另一個包含各種其他改進的版本。
/***** macros create functional code *****/
#define pivot_index() (begin+(end-begin)/2)
#define swap(a,b,t) ((t)=(a),(a)=(b),(b)=(t))
void sort(int array[], int begin, int end) {
/*** Use of static here will reduce memory footprint, but will make it thread-unsafe ***/
static int pivot;
static int t; /* temporary variable for swap */
if (end > begin) {
int l = begin + 1;
int r = end;
swap(array[begin], array[pivot_index()], t); /*** choose arbitrary pivot ***/
pivot = array[begin];
while(l < r) {
if (array[l] <= pivot) {
l++;
} else {
while(l < --r && array[r] >= pivot) /*** skip superfluous swaps ***/
;
swap(array[l], array[r], t);
}
}
l--;
swap(array[begin], array[l], t);
sort(array, begin, l);
sort(array, r, end);
}
}
#undef swap
#undef pivot_index
另一個簡單的C快速排序。上面的第一個C實現如果初始輸入是反向排序的列表，或者在樞紐恰好是列表中最大元素的任何時候，都不能正確排序列表。這是另一個解決這些問題的快速排序實現示例。請注意，此實現中交換操作是在內聯完成的。它們可以用上面示例中的交換函式替換。
void quick(int array[], int start, int end){
if(start < end){
int l=start+1, r=end, p = array[start];
while(l<r){
if(array[l] <= p)
l++;
else if(array[r] >= p)
r--;
else
swap(array[l],array[r]);
}
if(array[l] < p){
swap(array[l],array[start]);
l--;
}
else{
l--;
swap(array[l],array[start]);
}
quick(array, start, l);
quick(array, r, end);
}
}
這使用原地分割槽快速排序對整數陣列進行排序。
void quicksort(int x[], int first, int last) {
int pivIndex = 0;
if(first < last) {
pivIndex = partition(x,first, last);
quicksort(x,first,(pivIndex-1));
quicksort(x,(pivIndex+1),last);
}
}
int partition(int y[], int f, int l) {
int up,down,temp;
int piv = y[f];
up = f;
down = l;
goto partLS;
do {
temp = y[up];
y[up] = y[down];
y[down] = temp;
partLS:
while (y[up] <= piv && up < l) {
up++;
}
while (y[down] > piv && down > f ) {
down--;
}
} while (down > up);
y[f] = y[down];
y[down] = piv;
return down;
}
以下C程式碼示例可以編譯為對字串向量（定義為char *list[]）、整數、雙精度數等進行排序。這段程式碼實現了混合迭代-遞迴策略，即使在最壞情況下也能避免堆疊溢位風險。它比標準C庫函式qsort()執行得更快，尤其是在使用部分排序的陣列時（使用免費的Borland bcc32編譯並在100萬個字串向量上測試）。
/********** QuickSort(): sorts the vector 'list[]' **********/
/**** Compile QuickSort for strings ****/
#define QS_TYPE char*
#define QS_COMPARE(a,b) (strcmp((a),(b)))
/**** Compile QuickSort for integers ****/
//#define QS_TYPE int
//#define QS_COMPARE(a,b) ((a)-(b))
/**** Compile QuickSort for doubles, sort list in inverted order ****/
//#define QS_TYPE double
//#define QS_COMPARE(a,b) ((b)-(a))
void QuickSort(QS_TYPE list[], int beg, int end)
{
QS_TYPE piv; QS_TYPE tmp;
int l,r,p;
while (beg<end) // This while loop will avoid the second recursive call
{
l = beg; p = beg + (end-beg)/2; r = end;
piv = list[p];
while (1)
{
while ( (l<=r) && ( QS_COMPARE(list[l],piv) <= 0 ) ) l++;
while ( (l<=r) && ( QS_COMPARE(list[r],piv) > 0 ) ) r--;
if (l>r) break;
tmp=list[l]; list[l]=list[r]; list[r]=tmp;
if (p==r) p=l;
l++; r--;
}
list[p]=list[r]; list[r]=piv;
r--;
// Recursion on the shorter side & loop (with new indexes) on the longer
if ((r-beg)<(end-l))
{
QuickSort(list, beg, r);
beg=l;
}
else
{
QuickSort(list, l, end);
end=r;
}
}
}
快速排序也可以在少量堆疊的幫助下迭代實現。這裡有一個使用隨機選擇樞紐元素的簡單版本。
typedef long type; /* array type */
#define MAX 64 /* stack size for max 2^(64/2) array elements */
void quicksort_iterative(type array[], unsigned len) {
unsigned left = 0, stack[MAX], pos = 0, seed = rand();
for ( ; ; ) { /* outer loop */
for (; left+1 < len; len++) { /* sort left to len-1 */
if (pos == MAX) len = stack[pos = 0]; /* stack overflow, reset */
type pivot = array[left+seed%(len-left)]; /* pick random pivot */
seed = seed*69069+1; /* next pseudorandom number */
stack[pos++] = len; /* sort right part later */
for (unsigned right = left-1; ; ) { /* inner loop: partitioning */
while (array[++right] < pivot); /* look for greater element */
while (pivot < array[--len]); /* look for smaller element */
if (right >= len) break; /* partition point found? */
type temp = array[right];
array[right] = array[len]; /* the only swap */
array[len] = temp;
} /* partitioned, continue left part */
}
if (pos == 0) break; /* stack empty? */
left = len; /* left to right is sorted */
len = stack[--pos]; /* get next range to sort */
}
}
樞紐元素的偽隨機選擇確保在所有輸入條件下（遞增、遞減順序、相等元素）都能以O(n log n) 的效率進行排序。所需的堆疊大小小於2·log2(n)個條目（約99.9%的機率）。如果有限的堆疊溢位，排序將簡單地重新開始。
這是一個基於STL的通用快速排序版本。
請注意，此實現使用最後一個迭代器的內容，並且不適合作為std::[whatever]sort的替換。
#include <functional>
#include <algorithm>
#include <iterator>
template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
if( first != last ) {
BidirectionalIterator left = first;
BidirectionalIterator right = last;
BidirectionalIterator pivot = left++;
while( left != right ) {
if( cmp( *left, *pivot ) ) {
++left;
} else {
while( (left != right) && cmp( *pivot, *right ) )
--right;
std::iter_swap( left, right );
}
}
--left;
std::iter_swap( pivot, left );
quick_sort( first, left, cmp );
quick_sort( right, last, cmp );
}
}
template< typename BidirectionalIterator >
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
quick_sort( first, last,
std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
);
}
這是一個比核心實現部分中的版本更短的版本，它利用了標準庫的partition()函式。
#include <algorithm>
#include <iterator>
#include <functional>
using namespace std;
template <typename T>
void sort(T begin, T end) {
if (begin != end) {
T middle = partition (begin, end, bind2nd(
less<typename iterator_traits<T>::value_type>(), *begin));
sort (begin, middle);
// sort (max(begin + 1, middle), end);
T new_middle = begin;
sort (++new_middle, end);
}
}
以下C#實現使用了C#的功能方面。
public IEnumerable<T> Quicksort<T>(List<T> v, IComparer<T> comparer)
{
if (v.Count < 2)
return v;
T pivot = v[v.Count / 2];
return Quicksort(v.Where(x => comparer.Compare(x, pivot) < 0), comparer)
.Concat(new T[] { pivot })
.Concat(Quicksort(v.Where(x => comparer.Compare(x, pivot) > 0), comparer));
}
由於使用了分割槽，所以速度更快。
public IEnumerable<T> Quicksort(IEnumerable<T> v, Comparer<T> compare)
{
if (!v.Any())
return Enumerable.Empty<T>();
T pivot = v.First();
// partition
Stack<T> lowers = new Stack<T>(), greaters = new Stack<T>();
foreach (T item in v.Skip(1)) // skip the pivot
(compare(item, pivot) < 0 ? lowers : greaters).Push(item);
return Quicksort(lowers, compare)
.Concat(new T[] { pivot })
.Concat(Quicksort(greaters, compare));
}
以下示例使用linq過濾列表。
private void Quicksort<T>(T[] v, int left, int right, IComparer<T> comparer)
{
if (right - left > 1)
{
var mid = (left + right) / 2;
T pivot = v[mid];
T[] aux = new T[right - left + 1];
Array.Copy(v, left, aux, 0, aux.Length);
var vv = aux.Where(x => comparer.Compare(x, pivot) < 0)
.Concat( new T[] {pivot} )
.Concat(aux.Where(x => comparer.Compare(x, pivot) > 0)).ToArray();
Array.Copy(vv, 0, v, left, vv.Length);
Quicksort(v, left, mid, comparer);
Quicksort(v, mid + 1, right, comparer);
}
}
以下C#實現使用隨機樞紐。
static class Quicksort
{
private static void Swap<T>(T[] array, int left, int right)
{
var temp = array[right];
array[right] = array[left];
array[left] = temp;
}
public static void Sort<T>(T[] array, IComparer<T> comparer = null)
{
Sort(array, 0, array.Length - 1, comparer);
}
public static void Sort<T>(T[] array, int startIndex, int endIndex, IComparer<T> comparer = null)
{
if (comparer == null)
comparer = Comparer<T>.Default;
int left = startIndex;
int right = endIndex;
int pivot = startIndex;
startIndex++;
while (endIndex >= startIndex)
{
if (comparer.Compare(array[startIndex], array[pivot]) >= 0 && comparer.Compare(array[endIndex], array[pivot]) < 0)
Swap(array, startIndex, endIndex);
else if (comparer.Compare(array[startIndex], array[pivot]) >= 0)
endIndex--;
else if (comparer.Compare(array[endIndex], array[pivot]) < 0)
startIndex++;
else
{
endIndex--;
startIndex++;
}
}
Swap(array, pivot, endIndex);
pivot = endIndex;
if (pivot > left)
Sort(array, left, pivot);
if (right > pivot + 1)
Sort(array, pivot + 1, right);
}
}
Common Lisp
[編輯 | 編輯原始碼](defun partition (fun array)
(list (remove-if-not fun array) (remove-if fun array)))
(defun sort (array)
(if (null array) nil
(let ((part (partition (lambda (x) (< x (car array))) (cdr array))))
(append (sort (car part)) (cons (car array) (sort (cadr part)))))))
基於在rosettacode.org上釋出的C程式碼
void sort(T)(T arr) {
if (arr.length > 1) {
quickSort(arr.ptr, arr.ptr + (arr.length - 1));
}
}
void quickSort(T)(T *left, T *right) {
if (right > left) {
T pivot = left[(right - left) / 2];
T* r = right, l = left;
do {
while (*l < pivot) l++;
while (*r > pivot) r--;
if (l <= r) swap(*l++, *r--);
} while (l <= r);
quickSort(left, r);
quickSort(l, right);
}
}
//D2 version,working with almost any kind of iterator(called range in the D community)not only array
void quickSort(T)(T iter)
if(hasLength!T && isRandomAccessRange!T && hasSlicing!T){
if(iter.length<=1)return;//there is nothing to sort
auto pivot = iter[iter.length/2];
size_t r = iter.length, l = 0;
do {
while (iter[l] < pivot) l++;
while (iter[r] > pivot) r--;
if (l <= r) swap(iter[l++], iter[r--]);
} while (l <= r);
quickSort(iter[0 .. r]);
quickSort(iter[l .. $]);
}
此示例使用快速排序對字串進行排序。
注意：這可以被認為是糟糕的程式碼，因為它非常慢。
procedure QuickSort(const AList: TStrings; const AStart, AEnd: Integer);
procedure Swap(const AIdx1, AIdx2: Integer);
var
Tmp: string;
begin
Tmp := AList[AIdx1];
AList[AIdx1] := AList[AIdx2];
AList[AIdx2] := Tmp;
end;
var
Left: Integer;
Pivot: string;
Right: Integer;
begin
if AStart >= AEnd then
Exit;
Pivot := AList[AStart];
Left := AStart + 1;
Right := AEnd;
while Left < Right do
begin
if AList[Left] < Pivot then
Inc(Left)
else
begin
Swap(Left, Right);
Dec(Right);
end;
end;
Dec(Left);
Swap(Left, AStart);
Dec(Left);
QuickSort(AList, AStart, Left);
QuickSort(AList, Right, AEnd);
end;
此實現對整數陣列進行排序。
procedure QSort(var A: array of Integer);
procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var Lo, Hi, Mid, T: Integer;
begin
Lo := iLo;
Hi := iHi;
Mid := A[(Lo + Hi) div 2];
repeat
while A[Lo] < Mid do
Inc(Lo);
while A[Hi] > Mid do
Dec(Hi);
if Lo <= Hi then begin
T := A[Lo];
A[Lo] := A[Hi];
A[Hi] := T;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then
QuickSort(A, iLo, Hi);
if Lo < iHi then
QuickSort(A, Lo, iHi);
end;
begin
QuickSort(A, Low(A), High(A));
end;
此略微修改後的實現對記錄陣列進行排序。這比之前的實現快大約8倍。注意：這僅是快速排序，可以透過處理簡單情況（比較兩個值）或在較小範圍內實現氣泡排序或希爾排序來獲得更快的速度。
type
TCustomRecord = record
Key: WideString;
foo1:Int64;
foo2:TDatetime;
foo3:Extended;
end;
TCustomArray = array of TCustomRecord;
procedure QuickSort(var A: TCustomArray; L, R: Integer; var tmp: TCustomRecord);
var
OrigL,
OrigR: Integer;
Pivot: WideString;
GoodPivot,
SortPartitions: Boolean;
begin
if L<R then begin
Pivot:=A[L+Random(R-L)].Key;
OrigL:=L; //saving original bounds
OrigR:=R;
repeat
L:=OrigL; //restoring original bounds if we
R:=OrigR; //have chosen a bad pivot value
while L<R do begin
while (L<R) and (A[L].Key<Pivot) do Inc(L);
while (L<R) and (A[R].Key>=Pivot) do Dec(R);
if (L<R) then begin
tmp:=A[L];
A[L]:=A[R];
A[R]:=tmp;
Dec(R);
Inc(L);
end;
end;
if A[L].Key>=Pivot then Dec(L); //has we managed to choose
GoodPivot:=L>=OrigL; //a good pivot value?
SortPartitions:=True; //if so, then sort on
if not GoodPivot then begin //bad luck, the pivot is the smallest one in our range
GoodPivot:=True; //let's presume that all the values are equal to pivot
SortPartitions:=False; //then no need to sort it
for R := OrigL to OrigR do if A[R].Key<>Pivot then begin //we have at least one different value than our pivot
Pivot:=A[R].Key; //so this will be our new pivot
GoodPivot:=False; //we have to start again sorting this range
Break;
end;
end;
until GoodPivot;
if SortPartitions then begin
QuickSort(A, OrigL, L, tmp);
QuickSort(A, L+1, OrigR, tmp);
end;
end;
end;
以下Elixir程式碼對實現任何型別專案的Enumerable協議的集合進行排序，這些專案可以使用<運算子進行比較。
defmodule QSort do
def sort([]), do: []
def sort([pivot | rest]) do
{smaller, bigger} = Enum.partition(rest, &(&1 < pivot))
sort(smaller) ++ [pivot] ++ sort(bigger)
end
end
以下Erlang程式碼對任何型別專案的列表進行排序。
qsort([]) -> [];
qsort([Pivot|Rest]) ->
qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).
let rec qsort = function
hd :: tl ->
let less, greater = List.partition ((>=) hd) tl
List.concat [qsort less; [hd]; qsort greater]
| _ -> []
func QSort(data []int) {
if len(data) < 2 {
return
}
pivot := data[0]
l, r := 1, len(data) - 1
for l <= r {
for l <= r && data[l] <= pivot {
l ++
}
for r >= l && data[r] >= pivot {
r --
}
if l < r {
data[l], data[r] = data[r], data[l]
}
}
if r > 0 {
data[0], data[r] = data[r], data[0]
qsort(data[0:r])
}
qsort(data[l:])
}
static def quicksort(v) {
if (!v || v.size <= 1) return v
def (less, more) = v[1..-1].split { it <= v[0] }
quicksort(less) + v[0] + quicksort(more)
}
核心實現部分中的Haskell程式碼幾乎不言自明，但可能會效率低下，因為它兩次遍歷列表“rest”，每次遍歷都對應一個列表推導式。一個聰明的實現可以執行最佳化來防止這種低效，但這並不是語言的要求。以下實現沒有上述低效，因為它使用了一個分割槽函式，確保我們只遍歷`xs`一次
import Data.List (partition)
sort:: (Ord a) => [a] -> [a]
sort [] = []
sort (x:xs) = sort less ++ [x] ++ sort greatereq
where (less,greatereq) = partition (< x) xs
另一個版本
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (pivot:tail) = quicksort less ++ [pivot] ++ quicksort greater
where less = [y | y <- tail, y < pivot]
greater = [y | y <- tail, y >= pivot]
一個更短的版本
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
一個相當快的版本，它從末尾構建列表，使得使用(++)可以接受，它只遍歷較低部分的列表，並將它們新增到較高和相等列表的頭部。一個缺點是它需要對整個列表進行排序，對於惰性來說不是很好
qsort xs = qsort' xs []
qsort' [] end = end
qsort' (x:xs) end = qsort' lower (equal ++ qsort' higher end)
where (lower, equal, higher) = partit x xs ([],[x],[])
partit s [] part = part
partit s (x:xs) (l,e,h)
|x < s = partit s xs (x:l, e, h)
|x > s = partit s xs (l, e, x:h)
|otherwise = partit s xs (l, x:e, h)
核心實現部分中的J示例極其簡潔，難以理解。此實現來自J詞典，不那麼晦澀
sel=: adverb def 'x. # ['
quicksort=: verb define
if. 1 >: #y. do. y.
else.
(quicksort y. <sel e),(y. =sel e),quicksort y. >sel e=.y.{~?#y.
end.
)
以下示例使用Java 8的功能特性
import java.util.*;
import java.util.function.*;
import java.util.stream.Stream;
import static com.google.common.collect.Iterables.concat;
import static java.lang.System.out;
import static java.util.Arrays.asList;
import static java.util.stream.Collectors.partitioningBy;
import static org.assertj.core.util.Lists.newArrayList;
public <T> List<T> qs(List<T> l, BiPredicate<T, T> isLower) {
if (l.size() < 2) {
return l;
} else {
T x = l.get(0);
Stream<T> xs = l.stream().skip(1);
Map<Boolean, List<T>> part = xs.collect(partitioningBy(item -> isLower.test(item, x)));
List<T> lowers = part.get(true);
List<T> highers = part.get(false);
return newArrayList(concat(qs(lowers, isLower), asList(x), qs(highers, isLower)));
}
}
這是一個對數字ArrayList進行排序的Java示例實現。
import java.util.ArrayList;
import java.util.Random;
public class QuickSort {
public static final int NUMBERS_TO_SORT = 25;
public QuickSort() {
}
public static void main(String[] args) {
ArrayList<Integer> numbers = new ArrayList<Integer>();
Random rand = new Random();
for (int i = 0; i < NUMBERS_TO_SORT; i++)
numbers.add(rand.nextInt(NUMBERS_TO_SORT + 1));
for (int number : numbers)
System.out.print(number + " ");
System.out.println("\nBefore quick sort\n\n");
for (int number : quicksort(numbers))
System.out.print(number + " ");
System.out.println("\nAfter quick sort\n\n");
}
public static ArrayList<Integer> quicksort(ArrayList<Integer> numbers) {
if (numbers.size() <= 1)
return numbers;
int pivot = numbers.size() / 2;
ArrayList<Integer> lesser = new ArrayList<Integer>();
ArrayList<Integer> greater = new ArrayList<Integer>();
int sameAsPivot = 0;
for (int number : numbers) {
if (number > numbers.get(pivot))
greater.add(number);
else if (number < numbers.get(pivot))
lesser.add(number);
else
sameAsPivot++;
}
lesser = quicksort(lesser);
for (int i = 0; i < sameAsPivot; i++)
lesser.add(numbers.get(pivot));
greater = quicksort(greater);
ArrayList<Integer> sorted = new ArrayList<Integer>();
for (int number : lesser)
sorted.add(number);
for (int number: greater)
sorted.add(number);
return sorted;
}
}
以下Java實現使用隨機選擇的樞紐。類似於上面的Erlang解決方案，使用者提供的Template:Javadoc:SE確定陣列元素的部分排序
import java.util.Comparator;
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private static void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) {
int index = begin + RND.nextInt(end - begin + 1);
E pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public static <E> void sort(E[] array, Comparator<? super E> cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}
隨著J2SE 5.0的出現，您可以使用引數化型別來避免傳遞上面使用的Comparator。
import java.util.Arrays;
import java.util.Random;
public class QuickSort {
public static final Random RND = new Random();
private static void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private static <E extends Comparable<? super E>> int partition(E[] array, int begin, int end) {
int index = begin + RND.nextInt(end - begin + 1);
E pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++i) {
if (array[i].compareTo(pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private static <E extends Comparable<? super E>> int void qsort(E[] array, int begin, int end) {
if (end > begin) {
int index = partition(array, begin, end);
qsort(array, begin, index - 1);
qsort(array, index + 1, end);
}
}
public static <E extends Comparable<? super E>> int void sort(E[] array) {
qsort(array, 0, array.length - 1);
}
// Example uses
public static void main(String[] args) {
Integer[] l1 = { 5, 1024, 1, 88, 0, 1024 };
System.out.println("l1 start:" + Arrays.toString(l1));
QuickSort.sort(l1);
System.out.println("l1 sorted:" + Arrays.toString(l1));
String[] l2 = { "gamma", "beta", "alpha", "zoolander" };
System.out.println("l2 start:" + Arrays.toString(l2));
QuickSort.sort(l2);
System.out.println("l2 sorted:" + Arrays.toString(l2));
}
}
另一個實現。
import java.util.*;
public class QuickSort
{
public static void main(String[] args)
{
/* Data to be sorted */
List<Integer> data = createRandomData();
/* Generate a random permutation of the data.
* This sometimes improves the performance of QuickSort
*/
Collections.shuffle(data);
/* Call quick sort */
List<Integer> sorted = quickSort(data);
/* Print sorted data to the standard output */
System.out.println(sorted);
}
private static final Random rand = new Random();
/* Add data to be sorted to the list */
public static List<Integer> createRandomData()
{
int max = 1000000;
int len = 1000;
List<Integer> list = new ArrayList<Integer>();
for(int i=0; i<len; i++)
{
/* You can add any type that implements
* the Comparable interface */
list.add(Integer.valueOf(rand.nextInt(max)));
}
return list;
}
public static <E extends Comparable<? super E>> List<E> quickSort(List<E> data)
{
List<E> sorted = new ArrayList<E>();
rQuickSort(data, sorted);
return sorted;
}
/**
* A recursive implementation of QuickSort. Pivot selection
* is random. The algorithm is stable.
*/
public static <E extends Comparable<? super E>> void rQuickSort(List<E> data, List<E> sorted)
{
if(data.size() == 1)
{
sorted.add(data.iterator().next());
return;
}
if(data.size() == 0)
{
return;
}
/* choose the pivot randomly */
int pivot = rand.nextInt(data.size());
E pivotI = data.get(pivot);
List<E> fatPivot = new ArrayList<E>();
List<E> left = new ArrayList<E>();
List<E> right = new ArrayList<E>();
/* partition data */
for(E next : data)
{
int compare = pivotI.compareTo(next);
if(compare < 0)
{
right.add(next);
}
else if(compare > 0)
{
left.add(next);
}
else
{
fatPivot.add(next);
}
}
rQuickSort(left, sorted);
sorted.addAll(fatPivot);
rQuickSort(right, sorted);
}
}
這是一個使用遞迴的示例，就像Groovy實現一樣
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class Quicksort {
@SuppressWarnings("unchecked")
public static <E extends Comparable<? super E>> List<E>[] split(List<E> v) {
List<E>[] results = (List<E>[])new List[] { new LinkedList<E>(), new LinkedList<E>() };
Iterator<E> it = v.iterator();
E pivot = it.next();
while (it.hasNext()) {
E x = it.next();
if (x.compareTo(pivot) < 0) results[0].add(x);
else results[1].add(x);
}
return results;
}
public static <E extends Comparable<? super E>> List<E> quicksort(List<E> v) {
if (v == null || v.size() <= 1) return v;
final List<E> result = new LinkedList<E>();
final List<E>[] lists = split(v);
result.addAll(quicksort(lists[0]));
result.add(v.get(0));
result.addAll(quicksort(lists[1]));
return result;
}
}
JavaScript
[編輯 | 編輯原始碼]function qsort(a) {
if (a.length <= 1) return a; //< the array is already sorted at this point (e.g. [1] or [])
var left = []
var right = []
var pivot = a.shift(); //a separate `var` declaration must be used for each variable to avoid polluting global scope
while (a.length) a[0] < pivot ? left.push(a.shift()) : right.push(a.shift());
return qsort(left).concat(pivot).concat(qsort(right));
}
這是另一個使用宣告式程式設計的JavaScript實現，它不會改變輸入。
let quicksort=xs=>{
if (xs.length <= 1) return xs
var l = []
var r = []
var pivot = xs[xs.length-1] //< note that quicksort can commonly be made more performant by choosing a better pivot
xs.slice(0,-1).forEach(x => x < pivot ? l.push(x) : r.push(x)) //iterates over all the elements except the pivot, then pushes onto the appropriate list
return quicksort(l).concat([pivot], quicksort(r))
}
'''DEFINE''' sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .Mathematica
[編輯 | 編輯原始碼]這是一個函式式風格的實現
QSort[{}] := {}
QSort[{h_, t___}] :=
Join[QSort[Select[{t}, # < h &]], {h}, QSort[Select[{t}, # >= h &]]]
這是一個測試驅動程式，它應該產生True
OrderedQ[QSort[Table[Random[Integer, {1, 10000}], {i, 1, 10000}]]]
function [y]=quicksort(x)
% Uses quicksort to sort an array. Two dimensional arrays are sorted column-wise.
[n,m]=size(x);
if(m>1)
y=x;
for j=1:m
y(:,j)=quicksort(x(:,j));
end
return;
end
% The trivial cases
if(n<=1);y=x;return;end;
if(n==2)
if(x(1)>x(2))
x=[x(2); x(1)];
end
y=x;
return;
end
% The non-trivial case
% Find a pivot, and divide the array into two parts.
% All elements of the first part are less than the
% pivot, and the elements of the other part are greater
% than or equal to the pivot.
m=fix(n/2);
pivot=x(m);
ltIndices=find(x<pivot); % Indices of all elements less than pivot.
if(isempty(ltIndices)) % This happens when pivot is miniumum of all elements.
ind=find(x>pivot); % Find the indices of elements greater than pivot.
if(isempty(ind));y= x;return;end; % This happens when all elements are the same.
pivot=x(ind(1)); % Use new pivot.
ltIndices=find(x<pivot);
end
% Now find the indices of all elements not less than pivot.
% Since the pivot is an element of the array,
% geIndices cannot be empty.
geIndices=find(x>=pivot);
% Recursively sort the two parts of the array and concatenate
% the sorted parts.
y= [QuickSort(x(ltIndices));QuickSort(x(geIndices))];
sort [] = []
sort (pivot:rest) = sort [ y | y <- rest; y <= pivot ]
++ [pivot] ++
sort [ y | y <- rest; y > pivot ]
(* quicksort_r recurses down the list partitioning it into elements smaller than the pivot and others.
it then combines the lists at the end with the pivot in the middle.
It can be generalised to take a comparison function and thus remove the "int" type restriction.
It could also be generalised to use a Cons() function instead of the :: abbreviation allowing for
other sorts of lists.
*)
fun quicksort [] = []
| quicksort (p::lst) =
let fun quicksort_r pivot ([], front, back) = (quicksort front) @ [pivot] @ (quicksort back)
| quicksort_r pivot (x::xs, front, back) =
if x < pivot then
quicksort_r pivot (xs, x::front, back)
else
quicksort_r pivot (xs, front, x::back)
in
quicksort_r p (lst, [], [])
end
;
(* val quicksort = fn : int list -> int list *)
let rec sort = function
[] -> []
| pivot :: rest ->
let left, right = List.partition (( > ) pivot) rest in
sort left @ pivot :: sort right
sub qsort {
return () unless @_;
(qsort(grep { $_ < $_[0] } @_[$1..#_]), $_[0],
qsort(grep { $_ >= $_[0] } @_[$1..#_]))
}
或者
sub qsort {
@_ or return ();
my $p = shift;
(qsort(grep $_ < $p, @_), $p,
qsort(grep $_ >= $p, @_))
}
或者
sub qsort {
return if not @_;
my ($head, @tail) = @_;
return (qsort(grep { $_ < $head } @tail), $head,
qsort(grep { $_ >= $head} @tail))
}
multi quicksort () { () }
multi quicksort (*$x, *@xs) {
my @pre = @xs.grep:{ $_ < $x };
my @post = @xs.grep:{ $_ >= $x };
(@pre.quicksort, $x, @post.quicksort);
}
function quick_sort(sequence x)
--
-- put x into ascending order using recursive quick sort
--
integer n, last, mid
object xi, midval
n = length(x)
if n<2 then
return x -- already sorted (trivial case)
end if
mid = floor((n+1)/2)
midval = x[mid]
x[mid] = x[1]
last = 1
for i=2 to n do
xi = x[i]
if xi<midval then
last += 1
x[i] = x[last]
x[last] = xi
end if
end for
return quick_sort(x[2..last]) & {midval} & quick_sort(x[last+1..n])
end function
?quick_sort({5,"oranges","and",3,"apples"})
function quicksort($array) {
if(count($array) < 2) return $array;
$left = $right = array();
reset($array);
$pivot_key = key($array);
$pivot = array_shift($array);
foreach($array as $k => $v) {
if($v < $pivot)
$left[$k] = $v;
else
$right[$k] = $v;
}
return array_merge(quicksort($left), array($pivot_key => $pivot), quicksort($right));
}
使用array_filter和連續的數字鍵
function quicksort($array) {
if (count($array) <= 1) {
return $array;
}
$pivot_value = array_shift($array);
return array_merge(
quicksort(array_filter($array, function ($v) use($pivot_value) {return $v < $pivot_value;})),
array($pivot_value),
quicksort($higher = array_filter($array, function ($v) use($pivot_value) {return $v >= $pivot_value;}))
);
}
這是一個就地演算法，其效能優於上述實現。當然，在實際使用中，請使用PHP的原生排序函式。
// Quick sort between $start and $last indexes of array $a (inplace implementation)
function quickSort(&$a, $start = 0, $last = null) {
// Init
$wall = $start;
$last = is_null($last) ? count($a) - 1 : $last;
// Nothing to sort
if($last - $start < 1) {
return;
}
// Moving median value to the back to avoid bad performance when sorting an already sorted array
switchValues($a, (int) (($start + $last) / 2), $last);
// Splitting the array according to comparisons with the last value
for ($i = $start; $i < $last; $i++) {
if ($a[$i] < $a[$last]) {
switchValues($a, $i, $wall);
$wall++;
}
}
// Placing last value between the two split arrays
switchValues($a, $wall, $last);
// Sorting left of the wall
quickSort($a, $start, $wall - 1);
// Sorting right of the wall
quickSort($a, $wall + 1, $last);
}
// Switch two values identified by keys $i1 and $i2 of $a
function switchValues(&$a, $i1, $i2) {
if ($i1 !== $i2) {
$temp = $a[$i1];
$a[$i1] = $a[$i2];
$a[$i2] = $temp;
}
}
function printArray($a) {
echo '[' . implode(', ', $a). ']' . PHP_EOL;
}
// Generate array with random values
$arr = [];
$size = 1000000;
for ($i = 0; $i < $size; $i++) {
$arr[] = (int) (rand() / (1000000000 / $size));
}
// Measuring function's performance
$t1 = microtime(true);
quickSort($arr);
$t2 = microtime(true);
// Printing stats
// printArray($arr);
$t = round(($t2 - $t1) * 1000 * 1000) / 1000;
echo PHP_EOL . "Sorted $size elements in {$t}ms" . PHP_EOL;
核心實現部分中的版本簡潔明瞭，並且由於它使用了尾遞迴，因此效率很高。這是另一個版本
partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
( X @< Pivot ->
Smalls = [X|Rest],
partition(Xs, Pivot, Rest, Bigs)
; Bigs = [X|Rest],
partition(Xs, Pivot, Smalls, Rest)
).
quicksort([]) --> [].
quicksort([X|Xs]) -->
{ partition(Xs, X, Smaller, Bigger) },
quicksort(Smaller), [X], quicksort(Bigger).
使用列表推導式
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]])
使用原地分割槽和隨機樞紐選擇
import random
def _doquicksort(values, left, right):
"""Quick sort"""
def partition(values, left, right, pivotidx):
"""In place partitioning from left to right using the element at
pivotidx as the pivot. Returns the new pivot position."""
pivot = values[pivotidx]
# swap pivot and the last element
values[right], values[pivotidx] = values[pivotidx], values[right]
storeidx = left
for idx in range(left, right):
if values[idx] < pivot:
values[idx], values[storeidx] = values[storeidx], values[idx]
storeidx += 1
# move pivot to the proper place
values[storeidx], values[right] = values[right], values[storeidx]
return storeidx
if right > left:
# random pivot
pivotidx = random.randint(left, right)
pivotidx = partition(values, left, right, pivotidx)
_doquicksort(values, left, pivotidx)
_doquicksort(values, pivotidx + 1, right)
return values
def quicksort(mylist):
return _doquicksort(mylist, 0, len(mylist) - 1)
以上方法比下面的原地排序花費時間更長，後者僅將樞紐值以上的元素交換到左邊，將樞紐值以下的元素交換到右邊，而不是之前的方法，之前的方法會重新交換已經在樞紐值以下交換過的元素，從而使交換次數加倍。
然而，兩種原地排序都比佔用記憶體的列表推導式版本慢，而列表推導式版本本身比內建的 sorted() 函式慢 10 倍。
下面的版本沒有透過選擇隨機樞紐元素或三個元素的中位數作為樞紐元素來避免排序輸入不良的問題。
def qsinplace(a, l, r):
if l >= r:
return
pivot_idx = l
old_r = r
pivot = a[l]
l += 1
while True:
# manual check, does it work when l=pivot_idx, r=l+1 for a[l] <= a[r], and for a[l] > a[r] ?
while a[r] > pivot:
r -= 1
if l >= r:
break
while l < r and a[l] <= pivot:
l += 1
#pre-conditions to swap: l == r, or a[l] > pivot from 2nd loop, and a[r] <= pivot from 1st loop
a[l], a[r] = a[r], a[l]
a[pivot_idx], a[r] = a[r], a[pivot_idx]
qsinplace(a, pivot_idx, r)
qsinplace(a, r + 1, old_r)
#driver test
l=[i for i in xrange(0,100000) ]
import random
import time
t1 = time.time()
random.shuffle(l)
t2 = time.time()
print "took ", t2 - t1, " time to shuffle ", len(l)
print l
ll = len(l)
t1 = time.time()
# quick sort
qsinplace(l,0, ll-1)
t2 = time.time()
print "took ", t2 - t1, " time to qsinplace", len(l)
class QuickSort
def self.sort!(keys)
quick(keys,0,keys.size-1)
end
private
def self.quick(keys, left, right)
if left < right
pivot = partition(keys, left, right)
quick(keys, left, pivot-1)
quick(keys, pivot+1, right)
end
keys
end
def self.partition(keys, left, right)
x = keys[right]
i = left-1
for j in left..right-1
if keys[j] <= x
i += 1
keys[i], keys[j] = keys[j], keys[i]
end
end
keys[i+1], keys[right] = keys[right], keys[i+1]
i+1
end
end
使用閉包
def quicksort(list)
return list if list.length <= 1
pivot = list.shift
left, right = list.partition { |el| el < pivot }
quicksort(left) + [pivot] + quicksort(right)
end
使用閉包，但使用隨機樞紐
def quicksort(list)
return list if list.length <= 1
pivot = list.shuffle.shift
left, right = list.partition { |el| el < pivot }
quicksort(left).concat(quicksort(right))
end
def qsort(l: List[Int]): List[Int] = {
l match {
case List() => l
case _ => qsort(for(x <- l.tail if x < l.head) yield x) ::: List(l.head) ::: qsort(for(x <-1.tail if x >= l.head) yield x)
}
}
或更短的版本
def qsort: List[Int] => List[Int] = {
case Nil => Nil
case pivot :: tail =>
val (smaller, rest) = tail.partition(_ < pivot)
qsort(smaller) ::: pivot :: qsort(rest)
}
這使用了SRFI 1 和 SRFI 8。它避免了冗餘遍歷列表：它在一個遍歷中使用樞紐進行分割槽，而不是兩個，並且它避免了複製整個列表以追加它們，而是僅在輸出列表的尾部新增元素。
(define (quicksort list elt<)
(let qsort ((list list) (tail '()))
(if (null-list? list)
tail
(let ((pivot (car list)))
(receive (smaller larger)
(partition (lambda (x) (elt< x pivot))
(cdr list))
(qsort smaller (cons pivot (qsort larger tail))))))))
(define filter
{(A --> boolean) --> (list A) --> (list A)}
_ [] -> []
T? [A | B] -> (append [A] (filter T? B)) where (T? A)
T? [_|B] -> (filter T? B)
)
(define q-sort
{(list number) --> (list number)}
[] -> []
[A | B] -> (append (q-sort (filter (> A) [A|B]))
[A]
(q-sort (filter (< A) [A|B]))))
雖然許多其他指令碼語言（例如 Perl、Python、Ruby）都內建了庫排序例程，但 POSIX shell 通常沒有。
以下是根據上面Applescript程式碼改編的，並在 bash 偵錯程式[1]中使用。它已在bash、zsh和Korn shell（ksh）上進行了測試。
# Sort global array, $list, starting from $1 to up to $2. 0 is
# returned if everything went okay, and nonzero if there was an error.
# We use the recursive quicksort of Tony Hoare with inline array
# swapping to partition the array. The partition item is the middle
# array item. String comparison is used. The sort is not stable.
# It is necessary to use "function" keyword in order not to inherit
# variables being defined via typset, which solves the instability
# problem here.This is specified in the manual page of ksh.
function sort_list() {
(($# != 2)) && return 1
typeset -i left=$1
((left < 0)) || (( 0 == ${#list[@]})) && return 2
typeset -i right=$2
((right >= ${#list[@]})) && return 3
typeset -i i=$left; typeset -i j=$right
typeset -i mid; ((mid= (left+right) / 2))
typeset partition_item; partition_item="${list[$mid]}"
typeset temp
while ((j > i)) ; do
while [[ "${list[$i]}" < "$partition_item" ]] ; do
((i++))
done
while [[ "${list[$j]}" > "$partition_item" ]] ; do
((j--))
done
if ((i <= j)) ; then
temp="${list[$i]}"; list[$i]="${list[$j]}"; list[$j]="$temp"
((i++))
((j--))
fi
done
((left < j)) && sort_list $left $j
((right > i)) && sort_list $i $right
return $?
}
if [[ $0 == *sort.sh ]] ; then
[[ -n $ZSH_VERSION ]] && setopt ksharrays
typeset -a list
list=()
sort_list -1 0
typeset -p list
list=('one')
typeset -p list
sort_list 0 0
typeset -p list
list=('one' 'two' 'three')
sort_list 0 2
typeset -p list
list=(4 3 2 1)
sort_list 0 3
typeset -p list
fi
Standard ML
[編輯 | 編輯原始碼]下面的示例——雖然不如核心實現部分中的程式碼段通用，因為它不接受謂詞引數——力求更接近其他函式式語言中的實現。在兩個示例中使用List.partition使實現能夠僅對每個呼叫遍歷列表一次，從而減少演算法的常數因子。
fun qsort [] = []
| qsort (h::t) = let val (left, right) = List.partition (fn x => x < h) t
in qsort left @ h :: qsort right
end;
替換謂詞非常簡單
fun qsort pred [] = []
| qsort pred (h::t) = let val (left, right) = List.partition (fn x => pred (x, h)) t
in qsort pred left @ h :: qsort pred right
end;
一個更簡潔的版本，犧牲了List.partition的效率，類似於其他函式式語言中的列表推導式版本
fun qsort [] = []
| qsort (h::t) = qsort (List.filter (fn x => x < h) t) @ h :: qsort (List.filter (fn x => x >= h) t);
func qsort(var array: [Int]) -> [Int] {
if array.isEmpty { return [] }
let pivot = array.removeAtIndex(0)
var left = array.filter { $0 < pivot }
var right = array.filter { $0 >= pivot }
return qsort(left) + [pivot] + qsort(right)
}
Visual Basic
[編輯 | 編輯原始碼]Option Explicit
' a position, which is *hopefully* never used:
Public Const N_POS = -2147483648#
Public Sub Swap(ByRef Data() As Variant, _
Index1 As Long, _
Index2 As Long)
If Index1 <> Index2 Then
Dim tmp As Variant
If IsObject(Data(Index1)) Then
Set tmp = Data(Index1)
Else
tmp = Data(Index1)
End If
If IsObject(Data(Index2)) Then
Set Data(Index1) = Data(Index2)
Else
Data(Index1) = Data(Index2)
End If
If IsObject(tmp) Then
Set Data(Index2) = tmp
Else
Data(Index2) = tmp
End If
Set tmp = Nothing
End If
End Sub
Public Sub QuickSort(ByRef Data() As Variant, _
Optional ByVal Lower As Long = N_POS, _
Optional ByVal Upper As Long = N_POS)
If Lower = N_POS Then
Lower = LBound(Data)
End If
If Upper = N_POS Then
Upper = UBound(Data)
End If
If Lower < Upper Then
Dim Right As Long
Dim Left As Long
Left = Lower + 1
Right = Upper + 1
Do While Left < Right
If Data(Left) <= Data(Lower) Then
Left = Left + 1
Else
Right = Right - 1
Swap Data, Left, Right
End If
Loop
Left = Left - 1
Swap Data, Lower, Left
QuickSort Data, Lower, Left - 1
QuickSort Data, Right, Upper
End If
End Sub
另一個實現
Function Quicksort(ByRef aData() As Long) As Long()
Dim lPivot As Long
Dim aLesser() As Long
Dim aPivotList() As Long
Dim aBigger() As Long
Dim i As Long
Dim count As Long
Dim ret() As Long
On Error Resume Next
count = UBound(aData)
If Err Then
Exit Function
ElseIf count = 0 Then
Quicksort = aData
Exit Function
End If
On Error GoTo 0
Randomize
lPivot = aData(Int(Rnd * count))
For i = 0 To count
If aData(i) < lPivot Then AddTo aData(i), aLesser
If aData(i) = lPivot Then AddTo aData(i), aPivotList
If aData(i) > lPivot Then AddTo aData(i), aBigger
Next
aLesser = Quicksort(aLesser)
aPivotList = aPivotList
aBigger = Quicksort(aBigger)
ret = JoinLists(aLesser, aPivotList, aBigger)
Quicksort = ret
End Function
Sub AddTo(ByVal lData As Long, ByRef aWhere() As Long)
Dim count As Long
On Error Resume Next
count = UBound(aWhere) + 1
ReDim Preserve aWhere(count)
aWhere(count) = lData
On Error GoTo 0
End Sub
Function JoinLists(ByRef Arr1() As Long, ByRef Arr2() As Long, ByRef Arr3() As Long) As Long()
Dim count1 As Long
Dim count2 As Long
Dim count3 As Long
Dim i As Long
Dim ret() As Long
Dim cnt As Long
On Error Resume Next
Err.Clear
count1 = UBound(Arr1)
If Err Then count1 = -1
Err.Clear
count2 = UBound(Arr2)
If Err Then count2 = -1
Err.Clear
count3 = UBound(Arr3)
If Err Then count3 = -1
Err.Clear
On Error GoTo 0
ReDim ret(count1 + (count2 + 1) + (count3 + 1))
For i = 0 To count1
ret(i) = Arr1(i)
Next
For i = count1 + 1 To (count2 + 1) + count1
ret(i) = Arr2(i - count1 - 1)
Next
For i = count2 + 1 + count1 + 1 To (count3 + 1) + (count2 + 1) + count1
ret(i) = Arr3(i - count2 - 1 - count1 - 1)
Next
JoinLists = ret
End Function
要將其通用化，只需將型別更改為 Variant。
<p:declare-step xmlns:p="http://www.w3.org/ns/xproc" xmlns:c="http://www.w3.org/ns/xproc-step" xmlns:ix="http://www.innovimax.fr/ns" version="1.0">
<p:input port="source">
<p:inline exclude-inline-prefixes="#all">
<root>
<doc>03</doc>
<doc>04</doc>
<doc>07</doc>
<doc>06</doc>
<doc>02</doc>
<doc>01</doc>
<doc>08</doc>
<doc>10</doc>
<doc>09</doc>
<doc>05</doc>
<doc>03</doc>
<doc>04</doc>
<doc>07</doc>
<doc>06</doc>
<doc>02</doc>
<doc>01</doc>
<doc>08</doc>
<doc>10</doc>
<doc>09</doc>
<doc>05</doc>
<doc>03</doc>
<doc>04</doc>
<doc>07</doc>
<doc>06</doc>
<doc>02</doc>
<doc>01</doc>
<doc>08</doc>
<doc>10</doc>
<doc>09</doc>
<doc>05</doc>
<doc>03</doc>
<doc>04</doc>
<doc>07</doc>
<doc>06</doc>
<doc>02</doc>
<doc>01</doc>
<doc>08</doc>
<doc>10</doc>
<doc>09</doc>
<doc>05</doc>
<doc>03</doc>
<doc>04</doc>
<doc>07</doc>
<doc>06</doc>
<doc>02</doc>
<doc>01</doc>
<doc>08</doc>
<doc>10</doc>
<doc>09</doc>
<doc>05</doc>
<doc>03</doc>
<doc>04</doc>
<doc>07</doc>
<doc>06</doc>
<doc>02</doc>
<doc>01</doc>
<doc>08</doc>
<doc>10</doc>
<doc>09</doc>
<doc>05</doc>
</root>
</p:inline>
</p:input>
<p:output port="result"/>
<p:declare-step type="ix:sort" name="sort">
<p:documentation>
<p>XProc QuickSort implementation</p>
<p>Copyright (C) 2010 Mohamed ZERGAOUI Innovimax</p>
<p>This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.</p>
<p>This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.</p>
<p>You should have received a copy of the GNU General Public License
along with this program. If not, see
http://www.gnu.org/licenses/.</p>
</p:documentation>
<p:input port="source" sequence="true"/>
<p:output port="result" sequence="true"/>
<p:option name="key" required="true"/>
<p:count limit="2"/>
<p:choose>
<p:when test="number(.) le 1">
<p:identity>
<p:input port="source">
<p:pipe port="source" step="sort"/>
</p:input>
</p:identity>
</p:when>
<p:otherwise>
<p:split-sequence test="position() = 1" name="split">
<p:input port="source">
<p:pipe port="source" step="sort"/>
</p:input>
</p:split-sequence>
<p:filter name="filter">
<p:with-option name="select" select="$key">
<p:empty/>
</p:with-option>
</p:filter>
<p:group>
<p:variable name="pivot-key" select=".">
<p:pipe port="result" step="filter"/>
</p:variable>
<p:split-sequence name="split-pivot">
<p:input port="source">
<p:pipe port="not-matched" step="split"/>
</p:input>
<p:with-option name="test" select="concat($key, ' <= ',
$pivot-key)"/>
</p:split-sequence>
<ix:sort name="less">
<p:with-option name="key" select="$key">
<p:empty/>
</p:with-option>
<p:input port="source">
<p:pipe port="matched" step="split-pivot"/>
</p:input>
</ix:sort>
<ix:sort name="greater">
<p:with-option name="key" select="$key">
<p:empty/>
</p:with-option>
<p:input port="source">
<p:pipe port="not-matched" step="split-pivot"/>
</p:input>
</ix:sort>
<p:identity>
<p:input port="source">
<p:pipe port="result" step="less"/>
<p:pipe port="matched" step="split"/>
<p:pipe port="result" step="greater"/>
</p:input>
</p:identity>
</p:group>
</p:otherwise>
</p:choose>
</p:declare-step>
<p:for-each>
<p:iteration-source select="/root/doc"/>
<p:identity/>
</p:for-each>
<ix:sort key="/doc"/>
<p:wrap-sequence wrapper="root"/>
</p:declare-step>
Zilog Z80000 彙編
[編輯 | 編輯原始碼]此實現使用 z80 彙編程式碼。該處理器非常古老，因此它基本上是一個暫存器-堆疊遞迴雜耍技巧。更多關於它以及作者的評論此處。它採用暫存器對 BC 和 HL，它們指向要排序的列表中一個位元組元素的起始和結束記憶體位置。在此過程中，所有暫存器都填充了“垃圾”資料，因此需要將其推入堆疊以儲存。指令碼大約 44 位元組長，並且沒有樞紐最佳化程式碼。
;
; Usage: bc->first, de->last,
; call qsort
; Destroys: abcdefhl
;
qsort ld hl,0
push hl
qsloop ld h,b
ld l,c
or a
sbc hl,de
jp c,next1 ;loop until lo<hi
pop bc
ld a,b
or c
ret z ;bottom of stack
pop de
jp qsloop
next1 push de ;save hi,lo
push bc
ld a,(bc) ;pivot
ld h,a
dec bc
inc de
fleft inc bc ;do i++ while cur<piv
ld a,(bc)
cp h
jp c,fleft
fright dec de ;do i-- while cur>piv
ld a,(de)
ld l,a
ld a,h
cp l
jp c,fright
push hl ;save pivot
ld h,d ;exit if lo>hi
ld l,e
or a
sbc hl,bc
jp c,next2
ld a,(bc) ;swap (bc),(de)
ld h,a
ld a,(de)
ld (bc),a
ld a,h
ld (de),a
pop hl ;restore pivot
jp fleft
next2 pop hl ;restore pivot
pop hl ;pop lo
push bc ;stack=left-hi
ld b,h
ld c,l ;bc=lo,de=right
jp qsloop
TorqueScript
[編輯 | 編輯原始碼]這是使用 Torque 遊戲構建器（又名 TorqueScript）中的指令碼實現的快速排序。
// Sorts unordered set %uSet, which must be of the class SimSet.
function Quicksort(%uSet)
{
%less = new SimSet();
%pivots = new SimSet();
%greater = new SimSet();
if(%uSet.getCount() <= 1)
return %uSet;
%pivotVal = %uSet.getObject(getRandom(0, %uSet.getCount()-1)).myValue;
for(%i = 0; %i < %uSet.getCount(); %i ++)
{
// A new SimObject must be created in order to store it in a SimSet.
%valObj = new SimObject(val)
{
myValue = %uSet.getObject(%i).myValue;
};
if(%pivotVal > %valObj.myValue)
%less.add(%valObj);
else if(%pivotVal == %valObj.myValue)
%pivots.add(%valObj);
else //if(%pivotVal < %valObj.myValue)
%greater.add(%valObj);
}
return qConcatenate(Quicksort(%less), %pivots, Quicksort(%greater));
}
function qConcatenate(%less, %equal, %greater)
{
%all = new SimSet();
// Concatenate the three arrays, adding them to the SimSet one at a time.
for(%i = 0; %i < %less.getCount(); %i ++)
{
%all.add(%less.getObject(%i));
}
for(%i = 0; %i < %equal.getCount(); %i ++)
{
%all.add(%equal.getObject(%i));
}
for(%i = 0; %i < %greater.getCount(); %i ++)
{
%all.add(%greater.getObject(%i));
}
return %all;
}
FORTRAN 90/95
[編輯 | 編輯原始碼]此FORTRAN 90/95 中的快速排序實現是非遞迴的，並選擇三個元素的中位數（列表的第一個、最後一個和中間元素）作為樞紐元素。它還使用插入排序對少於 10 個元素的列表進行排序。
此快速排序實現緊密遵循可在FORTRAN 90/95 GPL 庫AFNL中找到的實現。
! ***********************************
! *
Subroutine Qsort(X, Ipt)
! *
! ***********************************
! * Sort Array X(:) in ascendent order
! * If present Ipt, a pointer with the
! * changes is returned in Ipt.
! ***********************************
Type Limits
Integer :: Ileft, Iright
End Type Limits
! For a list with Isw number of elements or
! less use Insrt
Integer, Parameter :: Isw = 10
Real (kind=4), Intent (inout) :: X(:)
Integer, Intent (out), Optional :: Ipt(:)
Integer :: I, Ipvn, Ileft, Iright, ISpos, ISmax
Integer, Allocatable :: IIpt(:)
Type (Limits), Allocatable :: Stack(:)
Allocate(Stack(Size(X)))
Stack(:)%Ileft = 0
If (Present(Ipt)) Then
Forall (I=1:Size(Ipt)) Ipt(I) = I
! Iniitialize the stack
Ispos = 1
Ismax = 1
Stack(ISpos)%Ileft = 1
Stack(ISpos)%Iright = Size(X)
Do While (Stack(ISpos)%Ileft /= 0)
Ileft = Stack(ISPos)%Ileft
Iright = Stack(ISPos)%Iright
If (Iright-Ileft <= Isw) Then
CALL InsrtLC(X, Ipt, Ileft,Iright)
ISpos = ISPos + 1
Else
Ipvn = ChoosePiv(X, Ileft, Iright)
Ipvn = Partition(X, Ileft, Iright, Ipvn, Ipt)
Stack(ISmax+1)%Ileft = Ileft
Stack(ISmax+1) %Iright = Ipvn-1
Stack(ISmax+2)%Ileft = Ipvn + 1
Stack(ISmax+2)%Iright = Iright
ISpos = ISpos + 1
ISmax = ISmax + 2
End If
End Do
Else
! Iniitialize the stack
Ispos = 1
Ismax = 1
Stack(ISpos)%Ileft = 1
Stack(ISpos)%Iright = Size(X)
Allocate(IIpt(10))
Do While (Stack(ISpos)%Ileft /= 0)
! Write(*,*)Ispos, ISmax
Ileft = Stack(ISPos)%Ileft
Iright = Stack(ISPos)%Iright
If (Iright-Ileft <= Isw) Then
CALL InsrtLC(X, IIpt, Ileft, Iright)
ISpos = ISPos + 1
Else
Ipvn = ChoosePiv(X, Ileft, Iright)
Ipvn = Partition(X, Ileft, Iright, Ipvn)
Stack(ISmax+1)%Ileft = Ileft
Stack(ISmax+1) %Iright = Ipvn-1
Stack(ISmax+2)%Ileft = Ipvn + 1
Stack(ISmax+2)%Iright = Iright
ISpos = ISpos + 1
ISmax = ISmax + 2
End If
End Do
Deallocate(IIpt)
End If
Deallocate(Stack)
Return
CONTAINS
! ***********************************
Integer Function ChoosePiv(XX, IIleft, IIright) Result (IIpv)
! ***********************************
! * Choose a Pivot element from XX(Ileft:Iright)
! * for Qsort. This routine chooses the median
! * of the first, last and mid element of the
! * list.
! ***********************************
Real (kind=4), Intent (in) :: XX(:)
Integer, Intent (in) :: IIleft, IIright
Real (kind=4) :: XXcp(3)
Integer :: IIpt(3), IImd
IImd = Int((IIleft+IIright)/2)
XXcp(1) = XX(IIleft)
XXcp(2) = XX(IImd)
XXcp(3) = XX(IIright)
IIpt = (/1,2,3/)
CALL InsrtLC(XXcp, IIpt, 1, 3)
Select Case (IIpt(2))
Case (1)
IIpv = IIleft
Case (2)
IIpv = IImd
Case (3)
IIpv = IIright
End Select
Return
End Function ChoosePiv
! ***********************************
Subroutine InsrtLC(XX, IIpt, IIl, IIr)
! ***********************************
! * Perform an insertion sort of the list
! * XX(:) between index values IIl and IIr.
! * IIpt(:) returns the permutations
! * made to sort.
! ***********************************
Real (kind=4), Intent (inout) :: XX(:)
Integer, Intent (inout) :: IIpt(:)
Integer, Intent (in) :: IIl, IIr
Real (kind=4) :: RRtmp
Integer :: II, JJ, IItmp
Do II = IIl+1, IIr
RRtmp = XX(II)
Do JJ = II-1, 1, -1
If (RRtmp < XX(JJ)) Then
XX(JJ+1) = XX(JJ)
CALL Swap_IN(IIpt, JJ, JJ+1)
Else
Exit
End If
End Do
XX(JJ+1) = RRtmp
End Do
Return
End Subroutine InsrtLC
End Subroutine Qsort
! ***********************************
! *
Integer Function Partition(X, Ileft, Iright, Ipv, Ipt) Result (Ipvfn)
! *
! ***********************************
! * This routine arranges the array X
! * between the index values Ileft and Iright
! * positioning elements smallers than
! * X(Ipv) at the left and the others
! * at the right.
! * Internal routine used by Qsort.
! ***********************************
Real (kind=4), Intent (inout) :: X(:)
Integer, Intent (in) :: Ileft, Iright, Ipv
Integer, Intent (inout), Optional :: Ipt(:)
Real (kind=4) :: Rpv
Integer :: I
Rpv = X(Ipv)
CALL Swap(X, Ipv, Iright)
If (Present(Ipt)) CALL Swap_IN(Ipt, Ipv, Iright)
Ipvfn = Ileft
If (Present(Ipt)) Then
Do I = Ileft, Iright-1
If (X(I) <= Rpv) Then
CALL Swap(X, I, Ipvfn)
CALL Swap_IN(Ipt, I, Ipvfn)
Ipvfn = Ipvfn + 1
End If
End Do
Else
Do I = Ileft, Iright-1
If (X(I) <= Rpv) Then
CALL Swap(X, I, Ipvfn)
Ipvfn = Ipvfn + 1
End If
End Do
End If
CALL Swap(X, Ipvfn, Iright)
If (Present(Ipt)) CALL Swap_IN(Ipt, Ipvfn, Iright)
Return
End Function Partition
! ***********************************
! *
Subroutine Swap(X, I, J)
! *
! ***********************************
! * Swaps elements I and J of array X(:).
! ***********************************
Real (kind=4), Intent (inout) :: X(:)
Integer, Intent (in) :: I, J
Real (kind=4) :: Itmp
Itmp = X(I)
X(I) = X(J)
X(J) = Itmp
Return
End Subroutine Swap
! ***********************************
! *
Subroutine Swap_IN(X, I, J)
! *
! ***********************************
! * Swaps elements I and J of array X(:).
! ***********************************
Integer, Intent (inout) :: X(:)
Integer, Intent (in) :: I, J
Integer :: Itmp
Itmp = X(I)
X(I) = X(J)
X(J) = Itmp
Return
End Subroutine Swap_IN
const maxA = 1000;
type TElem = integer;
TArray = array[1..maxA]of TElem;
(* This version of quick sort can be found in Turbo Pascal examples *)
procedure quicksort(var A:TArray;l,r:integer);
var i,j:integer;
x,w:TElem;
begin
i := l;
j := r;
x := A[(l + r) div 2];
repeat
while A[i] < x do i := i + 1;
while x < A[j] do j := j - 1;
if i <= j then
begin
w := A[i];
A[i] := A[j];
A[j] := w;
i := i + 1;
j := j - 1;
end;
until i > j;
if l < j then quicksort(A,l,j);
if i < r then quicksort(A,i,r);
end;
另一個帶有提取的分割槽函式的過程
const maxA = 1000;
maxS = 2000;
type TElem = integer;
TArray = array[1..maxA]of TElem;
TStackArray = array[1..maxS]of integer;
function HoarePartition(var A:TArray;p,r:integer):integer;
var i,j:integer;
x,t:TElem;
begin
x := A[p];
i := p - 1;
j := r + 1;
repeat
repeat
j := j - 1;
until A[j] <= x;
repeat
i := i + 1;
until A[i] >= x;
if i < j then
begin
t := A[i];
A[i] := A[j];
A[j] := t;
end;
until i >= j;
HoarePartition := j;
end;
function LomutoPartition(var A:TArray;p,r:integer):integer;
var i,j:integer;
x,t:TElem;
begin
x := A[r];
i := p - 1;
for j := p to r do
if A[j] <= x then
begin
i := i + 1;
t := A[i];
A[i] := A[j];
A[j] := t;
end;
if i < r then
LomutoPartition := i
else
LomutoPartition := i - 1;
end;
(*Recursive version of quick sort*)
procedure quickSort(var A:TArray;p,r:integer);
var q:integer;
begin
if p < r then
begin
q := HoarePartition(A,p,r);
quickSort(A,p,q);
quickSort(A,q + 1,r);
end;
end;
(*Iterative version of quick sort*)
procedure quickSort(var A:TArray;n:integer);
var p,q,r:integer;
s:TStackArray;
top:integer;
begin
top := 0;
if n > 1 then
begin
top := top + 2;
s[top] := n;
s[top - 1] := 1;
while top <> 0 do
begin
r := s[top];
p := s[top - 1];
top := top - 2;
while(p < r)do
begin
q := HoarePartition(A,p,r);
if q - p + 1 < r - q then
begin
top := top + 2;
s[top] := r;
s[top - 1] := q + 1;
r := q;
end
else
begin
top := top + 2;
s[top] := q;
s[top - 1] := p;
p = q + 1;
end;
end;
end;
end;
end;