维基教科书

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

< 算法实现 | 排序

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([]) -> [];
qsort([Head|Rest]) ->
	qsort([X || X <-Rest, X<Head]) ++ [Head] ++ qsort([X || X <-Rest, X>=Head]).

%% @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]
	head, tail := 0, len(data)-1
	for i := 1; i <= tail; {
		if data[i] > mid {
			data[i], data[tail] = data[tail], data[i]
			tail--
		} else {
			data[i], data[head] = data[head], data[i]
			head++
			i++
		}
	}
	qsort(data[:head])
	qsort(data[head+1:])
}

Haskell

编辑
参见：Haskell/高阶函数和Currying
  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, 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);
        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
检索自“https://zh.wikibooks.org/w/index.php?title=算法实现/排序/快速排序&oldid=135888”