1.原地排序，不稳定的，时间复杂度O(nlogn)，尽管最坏情况下是n^2，即每次选的partition都是边界值，但这种情况几乎不会发生。
思想：数据x前边的都比它小，后边的都比它大
不稳定情况的例子，比如有两个3，选择的轴心是前面的3，那么在对比时后面的3会跑到前面。
2.快排中调用的partition函数 可以有多种选择形式，意在选出一个较好的轴心x。此处列出选用尾节点a[right]作为轴心，如果随机选取只要将其与a[right]交换位置，
再调用该partition函数即可。
hoare-partition的思想是：j从后往前找比x小的，i是从前往后找比x大的，如果找到了但i<j就交换二者继续找，最后j的位置就是轴心，能够很好地代表中间性
public static void quickSort(int[] array,int left,int right){//递归,此处right=lenght-1;left=0 int q; if(left<right){ q=partition(array,left,right); quickSort(array,left,q-1); quickSort(array, q+1, right); } } public static int partition(int[] array,int left,int right){//筛选基准 //基于随机位置的partition，先选取随机位置index->a[index]和a[right]交换位置，然后在调用此partition int x=array[right];//以末尾元素为基准（或以首元素为基准) int i=left-1; for(int j=left;j<right;j++){ if(array[j]<=x){ i++;//注意 先i++再交换a[j]和a[i] int temp=array[j]; array[j]=array[i]; array[i]=temp; } } int t=array[i+1];//i+1的位置是尾元素的位置，交换二者 array[i+1]=array[right]; array[right]=t; return i+1;//x的位置 } public static int hoarePartition(int[] array,int left,int right){//原始的划分方法 //参数right=len-1; int x=array[left];//x为首个元素 int i=left; int j=right; while(true){ for(;i<right&&array[j]>=x;j--);//j从后往前找，找到比x小的位置 for(;j>left&&array[i]<=x;i++);//i从前往后找，找到比x大的位置 if(i<j){//i处是比x大的，j处是比x小的，二者交换位置，继续重复两个for int temp=array[i]; array[i]=array[j]; array[j]=temp; }else{//找到的位置i=j 就说明该位置是合适的划分位置 //array[j]=x;//这句是当采用非递归快排时用到的，如果采用递归快排则不需要这句****** return j; } } }3.非递归快排：借助栈来完成，调用hoare-partition（返回轴心j之前，a[j]=x 相当于排序部分，而在快排函数里入栈出栈的是下标）
记住入栈出栈的顺序，入栈时：先左后右，则出栈时先右后左
public static int hoarePartition(int[] array,int left,int right){//原始的划分方法 //参数right=len-1; int x=array[left];//x为首个元素 int i=left; int j=right; while(true){ for(;i<right&&array[j]>=x;j--);//j从后往前找，找到比x小的位置 for(;j>left&&array[i]<=x;i++);//i从前往后找，找到比x大的位置 if(i<j){//i处是比x大的，j处是比x小的，二者交换位置，继续重复两个for int temp=array[i]; array[i]=array[j]; array[j]=temp; }else{//找到的位置i=j 就说明该位置是合适的划分位置 array[j]=x;//这句是当采用非递归快排时用到的，如果采用递归快排则不需要这句****** return j; } } } public static void quickSort2(int[] array){//非递归快排 if(array==null||array.length==1) return; Stack<Integer> s=new Stack();//存放开始于结束索引 s.push(0);//注意向将左指针入栈，下面出栈时先出的是right s.push(array.length-1); while(!s.isEmpty()){ int right=s.pop();//上面入栈是先左指针后右指针，则出栈先右指针后左指针 int left=s.pop(); if(right<=left) continue;//如果最大索引《=左边索引说明结束 int i=partition(array, left, right);//选出轴心 if(left<i-1){ s.push(left);//先左后右 s.push(i-1); } if(i+1<right){ s.push(i+1);//先左后右 s.push(right); } } }