Quick Sort
核心:快排是一种采用分治思想的排序算法,大致分为三个步骤。
- 定基准——首先随机选择一个元素最为基准
- 划分区——所有比基准小的元素置于基准左侧,比基准大的元素置于右侧
- 递归调用——递归地调用此切分过程
Java
public static void quickSort(int[] array) {
quickSort1(array, 0, array.length - 1);
}
public static void quickSort1(int[] nums, int start, int end) {
if(start>=end) return;
int pivot = end;
int left = start;
int right = end-1;
while (left <= right) {
if (nums[left] > nums[pivot]) {
swap(nums, left, right);
right--;
} else {
left++;
}
}
swap(nums, left, pivot);
quickSort1(nums, start, left-1);
quickSort1(nums, left+1, end);
}
public static void swap(int[] nums, int a, int b) {
int tmp = nums[a];
nums[a] = nums[b];
nums[b] = tmp;
}