クイックソートQuick Sort
4915 ワード
自分で書いたコードを記録してください.2つのpartitionの方法をそれぞれ記録した.
public class QuickSort {
public static void quickSort(int[] nums, int start, int end) {
if(start >= end) {
return;
}
int pivot = partition2(nums, start, end);
quickSort(nums, start, pivot - 1);
quickSort(nums, pivot + 1, end);
}
public static int partition(int[] nums, int start, int end) {
int pivot = start;
for(int i = start + 1; i <= end; i++) {
if(nums[i] <= nums[start]) {
pivot++;
int temp = nums[pivot];
nums[pivot] = nums[i];
nums[i] = temp;
}
}
int temp = nums[pivot];
nums[pivot] = nums[start];
nums[start] = temp;
return pivot;
}
// better partition method
public static int partition2(int[] nums, int start, int end) {
int pivot = start, i = start + 1, j = end;
while(i < j) {
while(i <= end && nums[i] <= nums[pivot]) {
i++;
}
while(nums[j] >nums[pivot]) {
j--;
}
if(i >= j) {
break;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
i--;
int temp = nums[i];
nums[i] = nums[pivot];
nums[pivot] = temp;
return i;
}
public static void main(String[] args) {
int[] nums = new int[]{13, 6, 9, 1, 19, -21, 5};
quickSort(nums, 0, nums.length - 1);
System.out.println(nums);
}
}