下面来一些各种姿势的快速排序测试（代码来自维基百科）
C:
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++;
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);
}
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, head, j);
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);
String out = "";
for (int digit : arr) {
out += (digit + ",");
}
System.out.println(out);
}
}
Python:
def quicksort(lst, lo, hi):
if lo < hi:
p = partition(lst, lo, hi)
quicksort(lst, lo, p)
quicksort(lst, p+1, hi)
return
def partition(lst, lo, hi):
pivot = lst[hi-1]
i = lo - 1
for j in range(lo, hi):
if lst[j] < pivot:
i += 1
lst[i], lst[j] = lst[j], lst[i]
if lst[hi-1] < lst[i+1]:
lst[i+1], lst[hi-1] = lst[hi-1], lst[i+1]
return i+1
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));
}
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)))))))
JavaScript:
Array.prototype.quick_sort = function() {
var len = this.length;
if (len <= 1)
return this.slice(0);
var left = [];
var right = [];
var mid = [this[0]];
for (var i = 1; i < len; i++)
if (this[i] < mid[0])
left.push(this[i]);
else
right.push(this[i]);
return left.quick_sort().concat(mid.concat(right.quick_sort()));
};
var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quick_sort();
for (i = 0; i < arr.length; i++)
document.body.innerHTML += arr[i] + " ";
document.body.innerHTML += "<br>";
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