快速排序（二）
December 9, 2021在〈快速排序法（一）〉談到，如果不使用新數列來收集小於 S 與大於 S 的數，那麼就得在原數列上處理數的交換（swap）問題，這時軸的選擇、子數列的區段與交換方式等，會影響排序的速度。
解法思路
〈快速排序法（一）〉是將最左邊元素設為軸，也可以選定中間的元素作為軸，同時由左而右及由右至左分出子數列：
尚未處理的數列會在中間被逐步消化完畢，原本選定的 S 會被分至子數列之中：
接下來對左邊子數列與右邊子數列進行相同動作，直到排序完成。
演算法名書《Introduction to Algorithms》以最右邊（或最左邊）的數為軸，將數列分為小於 s、大於 s 與未處理的部份：
在排序的過程中，i 與 j 會不斷地往右進行比較與交換，最後數列會變為以下狀態：
然後將 s 置於中間，接下來以相同步驟對左右數列進行排序：
一個實際例子的演算如下所示：
程式實作：數列中間為軸
#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]
