算法实现/排序/快速排序
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;