排序算法中很重要的快速排序
递归实现方式
递归实现方式的不同在于分区函数的不同
public static void quickSort(int[] arr, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
//分区函数获取基准元素位置
int pivotIndex = singleParition(arr, startIndex, endIndex);
//分治递归
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
- 双向循环指针式，原理是利用左右指针分别维护较大数以及较小数区间
private static int partition(int[] arr, int startIndex, int endIndex) {
int pivot = arr[startIndex]; //使用第一个值作为基准值
int left = startIndex; //左指针
int right = endIndex; //右指针
//当两指针不重合时循环
while (left != right) {
//当右指针大于基准值的时候指针左移
while (left < right && arr[right] > pivot) {
right--;
}
//当左指针小于基准值的时候指针右移
while (left < right && arr[left] <= pivot) {
left++;
}
//交换左右指针
if (left < right) {
swap(arr, left, right);
}
}
//交换基准元素值和左/右指针
arr[startIndex] = arr[left];
arr[left] = pivot;
return left;
}
- 单项循环指针式，使用单指针来区分较大和较小区域
//单边循环分边函数,从小到大依次遍历，若小于基准值，则mark指针向右移动，
//并且让移动后的mark指针当前遍历值互换，最后遍历结束互换mark和基准指针值，并返回mark指针位置
private static int singleParition(int[] arr, int startIndex, int endIndex) {
int pivot = arr[startIndex];
int mark = startIndex;
for (int i = startIndex; i <= endIndex; i++) {
//若值比基准指针小则mark指针左移然后和该值交换
if (arr[i] < pivot) {
swap(arr, i, ++mark);
}
}
//交换mark指针的基准值
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}
非递归实现方式
非递归实现方式主要借用了栈的数据结构，来完成递归操作，这里的分区函数和递归的一致
public static void nonRecursiveQuickSort(int[] arr, int startIndex, int endIndex) {
//初始化栈
Stack<Map<String, Integer>> quickSortStack = new Stack<>();
HashMap<String, Integer> paramMap = Maps.newHashMap();
paramMap.put("startIndex", startIndex);
paramMap.put("endIndex", endIndex);
quickSortStack.push(paramMap);
//栈不空
while (!quickSortStack.isEmpty()) {
Map<String, Integer> map = quickSortStack.pop();
//从Map中获取对应属性值来获取基准点
int pivot = singleParition(arr, map.get("startIndex"), map.get("endIndex"));
if (map.get("startIndex") < pivot - 1) {
//入栈模拟调用递归方法
HashMap<String, Integer> left = Maps.newHashMap();
left.put("startIndex", map.get("startIndex"));
left.put("endIndex", pivot - 1);
quickSortStack.push(left);
}
if (map.get("endIndex") > pivot + 1) {
HashMap<String, Integer> right = Maps.newHashMap();
right.put("endIndex", map.get("endIndex"));
right.put("startIndex", pivot + 1);
quickSortStack.push(right);
}
}
}
