import java.util.Arrays;
public class QuickSort {
int[] data;
public void quicksort(int[] nums) {
if (nums == null || nums.length == 0) return;
data = nums;
sort(0, nums.length - 1);
}
private void sort(int left, int right) {
if (right <= left) return;
int pivot = partition(left, right);
sort(left, pivot - 1);
sort(pivot + 1, right);
}
/** * put all the numbers that are smaller than pivot to the left * **/ int partition(int left, int right) {
int pivot = data[right];
int startIndex = left;
for (int i = left; i < right; i++) {
//all the nums on the left of startIndex are smaller than pivot
//the number at startIndex is >= pivot if (data[i] < pivot) {
swap(startIndex++, i);
}
}
// put the pivot to the right position
swap(startIndex, right);
return startIndex;
}
void swap(int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void main(String[] args) {
QuickSort qs = new QuickSort();
int[] a = {200,30, 18,16,9,5,200};
qs.quicksort(a);
System.out.println(Arrays.toString(a));
}
}
Comments
Post a Comment