QuickSort(A, P, r)
{
if(p<r) then {
q = partion(A, P, r);
QuickSort(A, P, q-1);
QuickSort(A, q+1, r);
}
}
Partition(A, P, r)
{
x=A[r];
i=P-1;
for j=p to (r-1) do {
if(A[j]<= x) then {
i=i+1;
SWAP(A[i], A[j]);
return(i+1);
}
eg.
2, 8, 7, 1, 3, 5, 6, 4 實施 quick sort
"i"th: p-1, p,................., r array: nil, 2, 8, 7, 1, 3, 5, 6, 4 i為p-1 j為p j往前走，發現比array[r](i.e.4)還小的值，就把i+1然後做交換，當j走到r-1的時候，把array[r]跟array[i+1]交換 flow: 2, 8, 7, 1, 3, 5, 6, 4 2, 8, 7, 1, 3, 5, 6, 4 2, 1, 7, 8, 3, 5, 6, 4 2, 1, 3, 8, 7, 5, 6, 4 2, 1, 3, 4, 7, 5, 6, 8
⭐️ 5, 5, 5, 5, 5*
這個數列在DS中，是最佳解，不過在Algo中是最糟解
👉O(n²)
