描述
实现快速排序算法分析
随机选择待排序数组中一个元素为中心轴，将所有小于中心轴的元素移到左边，大于中心轴的元素移到右边，然后对中心轴左边和右边按照以上步骤递归下去，直至有序。
中心轴的选择很重要，比较好的情况就是恰好选择的元素就是数组的中位数，这时候递归树相对平衡，递归树的高也就是栈的深度，树越平衡，消耗的栈空间越少，最坏情况，即待排序数组逆序，可以演化为冒泡排序，且空间复杂度O(n)。时间复杂度O(nlogn)，空间复杂度O(logn)
public class Solution {
public void quickSort(int[] arr, int left, int right) {
int pivotIndex = partition(arr, left, right);
if(left < pivotIndex - 1)
quickSort(arr, left, pivotIndex - 1);
if(right > pivotIndex)
quickSort(arr, pivotIndex, right);
}
public int partition(int[] arr, int left, int right) {
int pivot = arr[(left+right)/2];
while(left <= right) {
while(arr[left] < pivot)
++ left;
while(arr[right] > pivot)
-- right;
if(left <= right) {
swap(arr, left, right);
++ left;
-- right;
}
}
return left;
}
public void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
