快速排序（Java）
快速排序算法思想：
（1）输入的数据信息：输入一个待排序的数组a[n]，利用QuickSort算法实现此数组的排序任务。
（2）快速排序的思想：找待排序数组a[n]中a[0]或者a[n-1]作为参考flag，例如找flag=a[n-1]，然后两个指针一个从left=0开始向右索引，一个指针从right=n-2开始向左索引，left指针寻找大于flag的元素，right指针寻找小于flag的元素，如果都找不到，则left++或right--，继续索引，当left>=right时，终止此循环，然后把flag与此时left指针索引的元素交换，最后输出left，实现数据分割，即left指针左边的数据元素小于flag，left指针右边的数据元素大于flag。
（3）递归实现算法：输入待排序的数组a[n]和需要对此数组排序的索引范围（left，right），因为我们不可能独立把数组分成两部分，所以实现的方式就是在原数组上进行处理，利用交换实现空间复杂度不变。
快速排序Java编程：
public class QuickSortTest {
public static void QuickSort(int[] arr, int left, int right){
if(left < right){
int medium = Partition(arr, left, right);
QuickSort(arr, left, medium-1);
QuickSort(arr, medium+1, right);
}
}
public static int Partition(int[] arr, int left, int right){
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot)
right--;
if (left < right)
arr[left++] = arr[right];
while (left < right && arr[left] <= pivot)
left++;
if (left < right)
arr[right--] = arr[left];
}
arr[left] = pivot;
return left;
}
public static void main(String[] args) {
int[] arr = {6,9,8,6,4,3,9,10,52,82,12,36,14};
int left = 0;
int right = arr.length - 1;
QuickSort(arr,left,right);
for(int i : arr){
System.out.print(i);
System.out.print(' ');
}
}
}
输出结果：3 4 6 6 8 9 9 10 12 14 36 52 82
快速排序的递归算法本质上就是一个二叉树的先序遍历过程，先处理当前根节点，然后依次处理左右部分（左子树和右子树）。
将快速排序递归算法转换为非递归相当于将二叉树先序遍历递归算法转为非递归算法。
时间复杂度和空间复杂度计算
1.时间复杂度：
①问题描述
快速排序将规模为n的问题分解为2个子问题，每个子问题的规模为n/2，每个子问题继续递归实现重复操作。
②公式定义：
T(n) = 2T(n/2) + f(n) = 2T(n/2) + O(n)
公式说明：T(n)表示总的时间复杂度，T(n/2)为分一次得到的子问题的时间复杂度，f(n)表示执行一次分裂需要做多少次操作，快速排序左右索引依次向中间走，总共需要遍历n次，所以f(n) = O(n)。
③求解T(n)的方法：
首先理解一个数组通过二分法对半分，一直到每一个数据都被分开隔离需要多少次？
答案：2^k = n，所以 k = lgn （以2为底的对数）
④生成函数法求解T(n)
T(n)=2T(n/2)+n
=2[2T(n/4)+n/2]+n = 4T(n/4) + 2n
=4[2T(n/8)+n/4]+2n = 8T(n/8) + 3n
=16T(n/16)+4n
=……
=(2^k) * T(n/(2^k)) + kn
=(2^lgn) * T(n/(2^lgn)) + nlgn
=nT(1)+nlgn
2.空间复杂度
①问题描述
a. 借用的辅助空间的大小
b. 递归时压入栈的数据所占用的空间。
②最坏情况：完全逆序
待续
