# 算法实现/排序/快速排序

## ActionScript

```public function qSort(arr:Array):void
{
quickSort(arr, 0, arr.length - 1);
}

private function quickSort(data:Array, left:int, right:int):void
{
var temp:Number = data[left];
var p:int = left;
var i:int = left, j:int = right;

while (i <= j)
{
while (data[j] >= temp && j >= p)
j--;
if (j >= p)
{
data[p] = data[j];
p = j;
}

while (data[i] <= temp && i <= p)
i++;
if (i <= p)
{
data[p] = data[i];
p = i;
}
}
data[p] = temp;
if (p - left > 1)
{
quickSort(data, left, p - 1);
}
if (right - p > 1)
{
quickSort(data, p + 1, right);
}
}
```

## C

```typedef struct _Range {
int start, end;
} Range;

Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}

void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}

void quick_sort(int arr[], const int len) {
if (len <= 0)
return; // 避免len等於負值時引發段錯誤（Segment Fault）
// r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點
int left = range.start, right = range.end;
do {
while (arr[left] < mid) ++left;   // 檢測基準點左側是否符合要求
while (arr[right] > mid) --right; //檢測基準點右側是否符合要求
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;               // 移動指針以繼續
}
} while (left <= right);
if (range.start < right) r[p++] = new_Range(range.start, right);
if (range.end > left) r[p++] = new_Range(left, range.end);
}
}
```

```void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}

void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else{
left++;
swap(&arr[left], &arr[end]);
}
if (left)
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}

void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
```

## C++

```sort(a,a + n);// 排序a[0]-a[n-1]的所有数.
```

```// 参考：http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/
struct Range {
int start, end;
Range(int s = 0, int e = 0) {
start = s, end = e;
}
};
template <typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能
void quick_sort(T arr[], const int len) {
if (len <= 0)
return; // 避免len等於負值時宣告堆疊陣列當機
// r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素
Range r[len];
int p = 0;
r[p++] = Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
T mid = arr[range.end];
int left = range.start, right = range.end - 1;
while (left < right) {
while (arr[left] < mid && left < right) left++;
while (arr[right] >= mid && left < right) right--;
std::swap(arr[left], arr[right]);
}
if (arr[left] >= arr[range.end])
std::swap(arr[left], arr[range.end]);
else
left++;
r[p++] = Range(range.start, left - 1);
r[p++] = Range(left + 1, range.end);
}
}
```

```template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {
if (start >= end)
return;
T mid = arr[end];
int left = start, right = end - 1;
while (left < right) { //在整个范围内搜寻比枢纽元值小或大的元素，然后将左侧元素与右侧元素交换
while (arr[left] < mid && left < right) //试图在左侧找到一个比枢纽元更大的元素
left++;
while (arr[right] >= mid && left < right) //试图在右侧找到一个比枢纽元更小的元素
right--;
std::swap(arr[left], arr[right]); //交换元素
}
if (arr[left] >= arr[end])
std::swap(arr[left], arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
template <typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能
void quick_sort(T arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
```

## C#

```        public static bool QuickSort(ref int[] arr, int left = 0, int right = -1)
{
if (right == -1)
{
right = arr.Length - 1;
}
if ((right >= 0 && left >= right)|| right > arr.Length - 1)
{
return true;
}
int container = arr[left];
int leftContainer = left;
int rightContainer = right;

while (left < right)
{
while (left < right && arr[right] >= container)
{
right--;
}
arr[left++] = arr[right];

while (left < right && arr[left] <= container)
{
left++;
}
arr[right--] = arr[left];
}
arr[left] = container;

return QuickSort(ref arr, leftContainer, left - 1) & QuickSort(ref arr, right + 1, rightContainer);
}
```

## Common Lisp

```(defun filter-< (lst pivot)
(remove-if-not (lambda (x)
(< x pivot)) lst))

(defun quick-sort (lst)
(if (null (cdr lst)) lst
(let ((pivot (car lst))
(else (cdr lst)))
(append
(quick-sort (filter-< else pivot))
(list pivot)
(quick-sort (set-difference
else
(filter-< else pivot)))))))
```

## Erlang

```qsort([]) -> [];

%% @doc 快排假装优化版（这个版本测试比第一个更慢，具体原因大家可以思考下）
sort_2([X | L]) ->
{L1, L2} = sort_2_helper(L, X),
sort_2(L1) ++ [X] ++ sort_2(L2);
sort_2([]) -> [].

sort_2_helper(L, X) -> sort_2_helper(L, X, {[], []}).

sort_2_helper([Y | L], X, {L1, L2}) when Y =< X -> sort_2_helper(L, X, {[Y | L1], L2});
sort_2_helper([Y | L], X, {L1, L2}) -> sort_2_helper(L, X, {L1, [Y | L2]});
sort_2_helper([], _X, {L1, L2}) -> {L1, L2}.
```

## Go

```func qsort(data []int) {
if len(data) <= 1 {
return
}
mid := data[0]
for i := 1; i <= tail; {
if data[i] > mid {
data[i], data[tail] = data[tail], data[i]
tail--
} else {
i++
}
}
}
```

```  sort :: (Ord a) = > [a] -> [a]

sort [] = []
sort (pivot:rest) = sort [y | y <- rest, y < pivot]
++ [pivot] ++
sort [y | y <- rest, y >=pivot]
```

## Java

```public class Application {

public static void qSort(int[] arr, int head, int tail) {
if (head >= tail || arr == null || arr.length <= 1) {
return;
}
int i = head, j = tail, pivot = arr[(head + tail) / 2];
while (i <= j) {
while (arr[i] < pivot) {
++i;
}
while (arr[j] > pivot) {
--j;
}
if (i < j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
++i;
--j;
} else if (i == j) {
++i;
}
}
qSort(arr, i, tail);
}

public static void main(String[] args) {
int[] arr = new int[]{1, 4, 8, 2, 55, 3, 4, 8, 6, 4, 0, 11, 34, 90, 23, 54, 77, 9, 2, 9, 4, 10};
qSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
```

## JavaScript

```Array.prototype.quickSort = function() {
const l = this.length
if(l < 2) return this
const basic = this[0], left = [], right = []
for(let i = 1; i < l; i++) {
const iv = this[i]
iv > basic && right.push(iv) // to avoid repeatly element.
iv < basic && left.push(iv)
}
return [...left.quickSort(), basic, ...right.quickSort()]
}
const arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
const ascendArr = arr.quickSort()
```

```const sort = (x, ...xs) => {
const sortAgain = f => arr => {
const res = arr.filter(f)
return res.length > 0 ? sort(...res) : []
}

return xs.length === 0
? [x]
: [...sortAgain(v => v < x)(xs), x, ...sortAgain(v => v > x)(xs)]
}
const arr = [7, 2, 6, 1, 2, 8, 4, 9, 0, 9, 7, 5, 4, 2]
const ascendArr = sort(...arr)
```

## Joy

```DEFINE sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .
```

## Matlab

```function sortedArray = quickSort(array)
if numel(array) <= 1
sortedArray = array;
return
end
pivot = array(end);
array(end) = [];
less = array( array <= pivot );
greater = array( array > pivot );
sortedArray = [quickSort(less) pivot quickSort(greater)];
end
```

## Pascal

```procedure quickSort(var a: array of integer; l, r: Integer);
var i,j,x:integer;
begin
if l>=r then exit;
i:=l;j:=r;x:=a[i];
while i<=j do
begin
while (i<j) and (a[j]>x) do dec(j);
if i<j then begin
a[i]:=a[j];
inc(i);
end;
while (i<j) and (a[i]<x) do inc(i);
if i<j then begin
a[j]:=a[i];
dec(j);
end;
a[i]:=x;
quicksort(a,l,i-1);
quicksort(a,i+1,r);
end;
end;
```

```procedure quicksort(var a: array of integer; l,r:integer);
var i,j,x,t:integer;
begin
i:=l; j:=r; x:=a[(l+r) div 2];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if i<=j then
begin
t:=a[i]; a[i]:=a[j]; a[j]:=t;
inc(i); dec(j);
end;
until i>j;
if i<r then quicksort(a,i,r);
if l<j then quicksort(a,l,j);
end;
```

## Perl

```sub qsort {
return () unless @_;
(qsort(grep { \$_ < \$_[0]  } @_[1..\$#_]),   \$_[0],
qsort(grep { \$_ >= \$_[0] } @_[1..\$#_]));
}
```

## Python原地排序版本

```def quick_sort(alist, first, last):
if first >= last:
return
mid_value = alist[first]
low = first
high = last
while low < high:
while low < high and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]
while low < high and alist[low] < mid_value:
low += 1
alist[high] = alist[low]
alist[low] = mid_value
quick_sort(alist, first, low-1)
quick_sort(alist, low+1, last)

numbers = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
quick_sort(numbers，0，len(numbers)-1)
assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```

## Python3

```def quick_sort(l):
if not l:
return l
return quick_sort(
[x for x in l[1:] if x < l[0]]
) + [l[0]] + quick_sort(
[x for x in l[1:] if x >= l[0]]
)
```

## PHP

```function quick_sort(\$arr) {
\$len = count(\$arr);

if (\$len <= 1)
return \$arr;

\$left = \$right = array();
\$mid_value = \$arr[0];

for (\$i = 1; \$i < \$len; \$i++)
if (\$arr[\$i] < \$mid_value)
\$left[] = \$arr[\$i];
else
\$right[] = \$arr[\$i];

return array_merge(quick_sort(\$left), (array)\$mid_value, quick_sort(\$right));
}
```

```function quick_sort(\$arr) {
\$len = count(\$arr);

if (\$len <= 1)
return \$arr;

\$left = \$right = array();
\$mid_index = \$len>>1;
\$mid_value = \$arr[\$mid_index];

for (\$i = 0; \$i < \$len; \$i++) {
if (\$i == \$mid_index)
continue;

if (\$arr[\$i] < \$mid_value)
\$left[] = \$arr[\$i];
else
\$right[] = \$arr[\$i];
}

return array_merge(quick_sort(\$left), (array)\$mid_value, quick_sort(\$right));
}

\$arr = array(21, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70);
\$arr = quick_sort(\$arr);
for (\$i = 0; \$i < count(\$arr); \$i++) {
echo \$arr[\$i] . ' ';
}
```

## Prolog

```split(H, [A|X], [A|Y], Z) :-
order(A, H), split(H, X, Y, Z).
split(H, [A|X], Y, [A|Z]) :-
not(order(A, H)), split(H, X, Y, Z).
split(_, [], [], []).

quicksort([], X, X).

quicksort([H|T], S, X) :-
split(H, T, A, B),
quicksort(A, S, [H|Y]),
quicksort(B, Y, X).
```

## Rust

```fn quick_sort<T: Ord + Copy>(data: &mut [T]) {
let len = data.len();
if len < 2 {
return;
}
let end = len - 1;

let mut cur = 0;
for i in 0..end {
if data[i] < data[end] {
data.swap(cur, i);
cur += 1;
}
}
data.swap(cur, end);

if cur > 1 {
quick_sort(&mut data[0..cur]);
}
if cur + 1 < len {
quick_sort(&mut data[cur + 1..len]);
}
}
```

## Ruby

```def quick_sort(array)
return array if array.size < 2
left, right = array[1..-1].partition { |y| y <= array.first }
quick_sort(left) + [array.first] + quick_sort(right)
end
```

## scheme

```#lang racket

;;快速排序
(define quick-sort
(λ (s)
(if (< (length s) 2)
s
(append
(quick-sort
(filter
(λ (e)
(< e (last s)))
s))
(filter
(λ (e)
(= e (last s)))
s)
(quick-sort
(filter
(λ (e)
(> e (last s)))
s))))))
```

## Standard ML

This example demonstrates the use of an arbitrary predicate in a functional language.

```fun quicksort lt lst =
let val rec sort =
fn [] => []
| (x::xs) =>
let
val (left,right) = List.partition (fn y => lt (y, x)) xs
in sort left @ x :: sort right
end
in sort lst
end
```

## VB.Net

```Public Shared Sub Sort(numbers As Integer())
Sort(numbers, 0, numbers.Length - 1)
End Sub

Private Shared Sub Sort(numbers As Integer(), left As Integer, right As Integer)
If left < right Then
Dim middle As Integer = numbers((left + right) \ 2)
Dim i As Integer = left - 1
Dim j As Integer = right + 1
While True
Do
i+=1
Loop While numbers(i) <= middle

Do
j-=1
Loop While numbers(j) >= middle

If i >= j Then
Exit While
End If

Swap(numbers, i, j)
End While

Sort(numbers, left, i - 1)
Sort(numbers, j + 1, right)
End If
End Sub

Private Shared Sub Swap(numbers As Integer(), i As Integer, j As Integer)
Dim number As Integer = numbers(i)
numbers(i) = numbers(j)
numbers(j) = number
End Sub
```