Quick Sort
Methodology
採用divide and conquer，
- Pick a pivot
Partition
Reorder the array so that the values less than pivot come before the pivot, and the value larger than pivot come after pivot
Recursively apply the above step to the subarray
(until the size of subarray is 1)
Time Complexity
Average
O(n log n)
Worst Case
O(n^2)
The worst case can be improved by randomly picking the pivot.
Space Complexity
Auxiliary Space
O(n log n)
In-place method requires O(1) space Recursive requires O(log n) stacks
Algorithm
public void QuickSort(int[] data, int left, int right) {
if(left>=right) {
return;
}
int pivot = data[right];
int pos = left;
for(int i=left; i<=right; i++) {
if(data[i] < pivot) {
swap(data[i], data[pos]);
pos++;
}
}
swap(data[right], data[pos]);
QuickSort(data, left, pos-1);
QuickSort(data, pos+1, right);
}