# 快速排序（二）

December 9, 2021

## 程式實作：數列中間為軸

``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}

void quickSort(int[], int, int);

int main(void) {
srand(time(NULL));

int number[MAX] = {0};

printf("排序前：");
int i;
for(i = 0; i < MAX; i++) {
number[i] = rand() % 100;
printf("%d ", number[i]);
}

quickSort(number, 0, MAX-1);

printf("\n排序後：");
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);

printf("\n");

return 0;
}

void quickSort(int number[], int left, int right) {
if(left < right) {
int s = number[(left+right)/2];
int i = left - 1;
int j = right + 1;

while(1) {
while(number[++i] < s) ;  // 向右找
while(number[--j] > s) ;  // 向左找
if(i >= j)
break;
SWAP(number[i], number[j]);
}

quickSort(number, left, i-1);   // 對左邊進行遞迴
quickSort(number, j+1, right);  // 對右邊進行遞迴
}
}
``````
``````public class Sort {
public static void quick(int[] number) {
sort(number, 0, number.length-1);
}

private static void sort(int[] number, int left, int right) {
if(left < right) {
int s = number[(left+right)/2];
int i = left - 1;
int j = right + 1;

while(true) {
// 向右找
while(number[++i] < s) ;
// 向左找
while(number[--j] > s) ;
if(i >= j)
break;
swap(number, i, j);
}

sort(number, left, i-1);   // 對左邊進行遞迴
sort(number, j+1, right);  // 對右邊進行遞迴
}
}

private static void swap(int[] number, int i, int j) {
int t = number[i];
number[i] = number[j];
number[j] = t;
}
}
``````
``````def sort(number):
realsort(number, 0, len(number) - 1)

def realsort(number, left, right):
if left < right:
s = number[(left + right) // 2]
i = left - 1
j = right + 1
while True:
while True:
i += 1
if number[i] >= s:
break
while True:
j -= 1
if number[j] <= s:
break
if i >= j:
break
number[i], number[j] = number[j], number[i]
realsort(number, left, i - 1)
realsort(number, j + 1, right)
``````
``````object Sort {
def quick(number: Array[Int]) {
sort(number, 0, number.length - 1)
}

private def sort(number: Array[Int], left: Int, right: Int) {
if(left < right) {
val s = number((left + right) / 2)
var i = left - 1
var j = right + 1
do {
do i += 1 while(number(i) < s)
do j -= 1 while(number(j) > s)
} while(if(i >= j) false else {swap(number, i, j); true})
sort(number, left, i - 1)
sort(number, j + 1, right)
}
}

private def swap(number: Array[Int], i: Int, j: Int) {
val t = number(i)
number(i) = number(j)
number(j) = t
}
}
``````
``````def sort(number)
realsort(number, 0, number.length - 1)
end

def realsort(number, left, right)
if left < right
s = number[(left + right) / 2]
i = left - 1
j = right + 1
while true
while true
i += 1
if number[i] >= s
break
end
end
while true
j -= 1
if number[j] <= s
break
end
end
if i >= j
break
end
number[i], number[j] = number[j], number[i]
end
realsort(number, left, j - 1)
realsort(number, j + 1, right)
end
end
``````
``````function sort(number) {
function realsort(number, left, right) {
if(left < right) {
let s = number[Math.floor((left + right) / 2)];
let i = left - 1;
let j = right + 1;
while(true) {
while(true) {
i += 1;
if(number[i] >= s) {
break;
}
}
while(true) {
j -= 1;
if(number[j] <= s) {
break;
}
}
if(i >= j) {
break;
}
[number[i], number[j]] = [number[j], number[i]]
}
realsort(number, left, i - 1);
realsort(number, j + 1, right);
}
}

realsort(number, 0, number.length - 1);
}

let number = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11];
sort(number);
console.log(number);
``````
``````slice start stop xs = take (stop - start) (drop start xs)

quickSort lt compare =
if null lt then []
else
let leng = length lt
pivot = leng `div` 2
x = lt !! pivot
xs = (slice 0 pivot lt) ++ (slice (pivot + 1) leng lt)
before = filter (not . (compare x)) xs
after = filter (compare x) xs
in (quickSort before compare) ++ [x] ++ (quickSort after compare)

main = sequence [print \$ quickSort xs (<),
print \$ quickSort xs (>)]
where xs = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11]
``````

## 程式實作：數列右邊為軸

``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}

int partition(int[], int, int);
void quickSort(int[], int, int);

int main(void) {
srand(time(NULL));

int number[MAX] = {0};

printf("排序前：");
int i;
for(i = 0; i < MAX; i++) {
number[i] = rand() % 100;
printf("%d ", number[i]);
}

quickSort(number, 0, MAX-1);

printf("\n排序後：");
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);

printf("\n");

return 0;
}

int partition(int number[], int left, int right) {
int i = left - 1;
int j;
for(j = left; j < right; j++) {
if(number[j] <= number[right]) {
i++;
SWAP(number[i], number[j]);
}
}

SWAP(number[i+1], number[right]);
return i+1;
}

void quickSort(int number[], int left, int right) {
if(left < right) {
int q = partition(number, left, right);
quickSort(number, left, q-1);
quickSort(number, q+1, right);
}
}
``````
``````public class Sort {
public static void quick(int[] number) {
sort(number, 0, number.length-1);
}

private static void sort(int[] number, int left, int right) {
if(left < right) {
int q = partition(number, left, right);
sort(number, left, q-1);
sort(number, q+1, right);
}

}

private static int partition(int number[], int left, int right) {
int i = left - 1;
for(int j = left; j < right; j++) {
if(number[j] <= number[right]) {
i++;
swap(number, i, j);
}
}
swap(number, i+1, right);
return i+1;
}

private static void swap(int[] number, int i, int j) {
int t = number[i];
number[i] = number[j];
number[j] = t;
}
}
``````
``````def sort(lst):
if len(lst) <= 1:
return lst
pivot = lst.pop(0)
before = [i for i in lst if i < pivot]
after = [i for i in lst if i >= pivot]
return sort(before) + [pivot] + sort(after)
``````
``````object Sort {
def quick(list: List[Int]): List[Int] = {
list match {
case Nil => Nil
case x::xs =>
val (before,after) = xs partition (_ < x)
quick(before) ++ (x :: quick(after))
}
}
}
``````
``````class Array
def comprehend(&block)
return self if block.nil?
self.collect(&block).compact
end
end

def quick(lst)
case
when lst.length <= 1
lst
when pivot = lst.shift
before = lst.comprehend { |i| i if i < pivot}
after = lst.comprehend { |i| i if i >= pivot}
quick(before) + [pivot] + quick(after)
end
end
``````
``````function sort(lst) {
if(lst.length <= 1){
return lst;
}
let pivot = lst.pop()
let before = lst.filter(i => i < pivot);
let after = lst.filter(i => i >= pivot);
return sort(before).concat([pivot]).concat(sort(after));
}

let number = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11];
console.log(sort(number));
``````
``````quickSort lt compare =
if null lt then []
else
let xs = init lt
x = last lt
before = filter (not . (compare x)) xs
after = filter (compare x) xs
in (quickSort before compare) ++ [x] ++ (quickSort after compare)

main = sequence [print \$ quickSort xs (<),
print \$ quickSort xs (>)]
where xs = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11]
``````