快速排序
- 原理:
- 实现:
- partition
- hoare法:
- 实现:
- 挖坑法:
- 实现:
- 前后遍历:
- 实现:
- 非递归实现:
原理:
1、从待排序区间中选择一个数,作为基准值(pivot);
2、Partition:遍历整个待排序区间,将小于等于基准值放在基准值左边,将大于等于基准值的放在基准值右边;
3、采用分治思想,对左右两个区间相同方式处理,直到区间长度为1,代表有序,或者区间长度为0,代表没有数据。
实现:
当我们看见使用相同的方式处理,应该很快想到需要使用递归,但是使用递归,我们需要划定区间,所以需要quickRange,(至于partition方法如何实现,我们暂时不考虑)
java">public class QuickSort {
public static void quick(int[] array) {
quickRange(array, 0, array.length - 1);
}
private static void quickRange(int[] array, int from, int to) {
int size = to - from + 1;
if (size <= 1) {
return;
}
int pivotIndex = partition(array, from, to);
quickRange(array, from, pivotIndex - 1);
quickRange(array, pivotIndex + 1, to);
}
}
partition
那么我们如何实现partition的方法呢,如何将基准值左边都比基准值小,基准值右边都比基准值大呢?
hoare法:
找到一个基准值(习惯性找第一个),然后从区间前后开始,当左边比基准值小,就继续,直到找到一个比基准值大的元素停下来。右边也是直到找到比基准值小的元素停下来,然后交换两个位置,继续走…直到最后,再将基准值和中间位置交换。
实现:
java"> private static int partition(long[] array, int from, int to) {
int left = from;
int right = to;
long poivt = array[from];
while (left < right) {
while (left < right && array[right] >= poivt) {
right--;
}
while (left < right && array[left] <= poivt) {
left++;
}
//交换
Swap.swap(array, left, right);
}
Swap.swap(array, left, from);
return left;
}
挖坑法:
原理和Hoare法基本一致,唯一不同的就是,不进行交换,而是直接进行赋值(就想挖坑+填坑)
实现:
java"> private static int partition(long[] array, int from, int to) {
int left = from;
int right = to;
long pivot = array[left];
while (left<right){
while (left<right&&array[right]>=pivot){
right--;
}
array[left] = array[right];
while (left<right&&array[left]<=pivot){
left++;
}
array[right] = array[left];
}
array[left] = pivot;
return left;
}
前后遍历:
选定一个基准值,从前到后遍历无序区间,如果遇到比基准值小的,则将比基准值小的区间后面加上一个。
实现:
java">
private static int partition3(long[] array, int from, int to) {
long pivot = array[from];
int s = from + 1;
for (int i = from + 1; i <= to; i++) {
if (array[i] < pivot) {
Swap.swap(array, i, s);
s++;
}
}
Swap.swap(array, s - 1, from);
return s - 1;
}
非递归实现:
原理还是先处理基准值左边,在处理基准值右边,我们借助栈实现非递归过程:
java">public static void quickSort(long[] array) {
Stack<Integer> stack = new Stack<>();
stack.push(array.length - 1);
stack.push(0);
while (!stack.isEmpty()) {
int left = stack.pop();
int right = stack.pop();
if (left >= right) {
continue;
}
int pivotIndex = partition(array,left,right);
stack.push(right);
stack.push(pivotIndex+1);
stack.push(pivotIndex-1);
stack.push(left);
}
}