题目：对于一个int数组，请编写一个快速排序算法，对数组元素排序。给定一个int数组A及数组的大小n，请返回排序后的数组。测试样例：[1,2,3,5,2,3],6 [1,2,2,3,3,5]
思路：
快速排序是使用二分思想，通过递归来实现排序的。对于一个数组，它先随机选择一个元素A将数组分成两个部分，将小于元素A的元素放到数组的A的左边，将大于A的元素放到A的右边，然后再对左右两侧的子数组分别进行递归的分割排序，递归的边界条件是当最终分割得到的数组只有一个元素，即被元素A分割得到的某个数组大小是1，那么这个大小为1的数组就直接就是结果，不用再进行递归了，对于元素数目多于1的数组继续进行分割递归排序。快速排序的关键①随机元素的选取，直接决定了排序的复杂度，但是通常选取数组的中间元素作为分界元素；②已知数组array和其中的分界元素array[k]，如何将数组中小于等于array[k]的元素放在其左边而将大于array[k]的元素放在其右边？这里采取的策略是，创建一个抽象的小于等于区间{}。先将array[k]与数组的最后一个元素array[length-1]进行交换，使得分界元素位于最后面，然后假设初始的小于等于array[k]的数组smallArray[]在array[0]位置的左侧，初始为空，即为{}；然后使用两个指针p1,p2对数组array[]和smallArray[]进行遍历，p1初始值是0，p2初始值是-1，将array[p1]与array[k]=A进行比较，如果array[p1]>A,那么p2保持不变，p1++，表示这个元素大于A，不能放入到左侧的{}中；如果array[p1]<A，那么说明A元素小于分界值A，可以放入到左侧的{}中，此时将p2++，表示{}要开始容纳一个元素，然后将array[p2]与array[p1]进行交换，此时得到{0}5641723；然后再p1++即开始遍历下一个元素，即当遇到一个元素array[p1]<A时总是先对p2进行p2++，再将其array[p2]与array[p1]进行交换，再对p1进行p1++。即快速排序也是基于交换的，需要进行nlogn次交换。
快速排序的时间复杂度O(nlogn)，空间复杂度O(1)，不稳定。
采用该思路失败的代码：
import java.util.*;
//快速排序：借助二分法的思想，使用递归，选定中间元素，将小于该值的元素放到左边，大于等于的放到右边
public class QuickSort {
public int[]quickSort(int[] A, int n) {
//特殊输入
if(A==null||A.length<=0)return A;
//调用递归方法进行二分和元素的移动，完成排序
this.adjust(A,0,A.length-1);
return A;
}
//写一个递归的分割方法，将数组二分，然后以此元素为界将数组进行移动，小于等于的位于左边，大于等于的位于右边
/*public voiddivide(int[] array,int start,int end){
//递归一定要写终止的边界条件
if(start==end)return;
//找任意一个元素作为分界点，但是通常选择中间元素作为分界点
int middle=(start+end)/2;
//对当前的数组根据中间点进行分界，使得小于等于的位于左边，大于的位于右边
this.adjust(array,start,end);
//继续对2个子数组进行二分
this.divide(array,start,middle);
this.divide(array,middle+1,end);
//调用adjust()方法将[start,end]范围内的数组以middle为界进行移动使之按照大小位于2边
this.adjust(array,start,end);
}
*/
//写一个方法adjust(),将[start,end]范围内的元素按照中间值分成2个部分并调整大小，小于等于的在左，大的在右
public voidadjust(int[] array,int start,int end){
//递归一定要写终止的边界条件，这里的边界条件是需要分界的数组只有一个元素
if(start==end)return;
//显然分界元素是middle
intmiddle=(start+end)/2;
//核心逻辑，将小于middle的元素放到左边，大于middle的元素放到右边
//①先将分界元素与最后的元素交换使得分界元素位于最后面
this.swap(array,middle,end);
//②设置指针p指向抽象的小于等于middle的数组smallArray{}456123;指针i用来遍历原始数组array，每次调整都是从0开始进行遍历调整
int p=start-1;
for(inti=start;i<=end;i++){
if(array[i]<=array[end]){
//如果元素i小于分界元素,那么就与小于等于数组区间{}的下一个元素进行交换
swap(array,++p,i);
}
}
/*
③本次调整结束，小于等于array[middle]值的元素全部位于数组的前列，大于的位于后面，注意，middle只是位置上面的中间，并不是大小的中间值（中位数）,于是调整后的数组原来的分界值并不在中间位置，只是确保该值前面的都是小于该值的，该值后面的都是大于该值的而已。于是在此之后要继续对分界后的2个子数组进行分界排序，即对2个子数组调用递归过程。注意此时的2个子数组的分界位置是调整后的分界值所在的新位置，即上面循环过后的p的位置。于是对[start,p]和[p+1,end]进行调整
*///假设执行adjust()方法后就完成了调整功能，即将[start,end]范围的元素进行了分界，不要考虑递归细节
this.adjust(array,start,p);
this.adjust(array,p+1,end);
}
//专门写一个辅助函数用来交换数组中的2个元素
public voidswap(int[] array,int p1,int p2){
inttemp=array[p1];
array[p1]=array[p2];
array[p2]=temp;
}
}
对于快速排序，换成这种思路：
快速排序和归并排序一样，都采用分治的思想，先分再合，写一个divide(array,start,end)方法来对数组array中从start到end范围的数组进行分界；显然需要递归的划分数组，要想递归的划分数组需要求得分界元素，于是在递归调用divide()之前，写一个分界函数partition()来确定[start,end]范围的分界值—将数组元素进行分界—返回分界后分界元素位于的新的位置p1。即在divide()方法中通过先调用partitiom()方法返回分界后的新的分界元素下标mid然后递归的调用divide(start，mid)；divide(mid+1,end)来进行新的分界。
即核心的逻辑是写一个partition(A，start，end)方法，选择以中间位置的元素作为分界点，middle=(start+end)/2，先将这个元素与最后的元素array[end]交换位置，使得该分界元素位于数组的末尾，然后将小于等于分界值的元素移动到数组的前面，将大于等于分界值的元素移动到数组的后面部分，使用的交换策略是设置2个指针p1,p2分别从数组的start和end-1开始进行遍历，p1逐步向后面移动，将元素逐个与分界值进行比较，如果小于分界值就不交换，直接p1++，直到遇到array[p1]>=分界值为止；p2从数组的end-1开始向前遍历，如果array[p2]>分界值则不交换，p2--，直到array[p2]<=分界值为止，此时array[p1]<=分界值；array[p2]>=分界值；此时将array[p1]与array[p2]进行交换，依次进行，直到p1>=p2，即p1和p2交错时停止，此时p1所在位置是第一个大于等于分界值的元素，将array[p1]与分界值array[end]进行交换，此时完成一轮分割，于是小于等于分界值的元素都在前面部分，大于等于分界值的元素都在后面部分，分界值的新的下标是p1,即此时[start,end]数组的分界值在p1位置（注意，这里采取的交换策略中，对于左边的指针p1，认为大于等于分界值的元素都应该移到右边；对于右边的指针p2，认为小于等于分界值的元素都应该移动到左边，即都包含等于的情况，这样可以使得结果均衡，避免出现最坏情况。）在完成了这一轮的分界之后，应该对分界后的2个子数组进行递归的分界，即已经得到了分界值p1，于是对于[start,p1]和[p1+1,end]要分别调用partition()方法进行分界。
与归并排序不同的是，归并排序是先递归调用divide(),再调用非递归方法merge()方法进行合并；
this.divide(array,tempArray,start,middle);
this.divide(array,tempArray,middle+1,end);
this.merge(array,tempArray,start,end);
快速排序是先调用非递归方法partition()确定分界值，再递归调用divide()进行进一步分界。
int mid = partition(A, start, end);
quick(A, start , mid);
quick(A, mid+1, end);
注意对于递归方法，一定要有递归结束的边界条件。
注意：快速排序非常容易出错，不仅要理解，对于易出错的点还要记住解决方案，直接按照规范的操作来，不要随便写，直接避免出错就行了。
①例如如果对于区间[6,7]进行快排，那么(6+7)/2=6；p1=6,p2=6,将44与44进行交换，之后p1=7,p2=5,结束循环，将array[p1]与array[end]进行交换，即array[end]与array[end]自身进行交换。相当于没有交换，于是程序陷入死循环，死递归最终出现栈溢出的错误。
这里快速排序采用的分组方式其实很简单，不需要找到之间元素后与最后的元素进行交换，在对i、j进行遍历交换最后再将最后的元素更换回来并记录分界点新的位置。采用的分组策略是这样的：partition(array,start,end)方法用于对数组array中[start,end]区间内的元素进行分界，注意partition()方法不是递归方法，它先找到[start,end]数组中间位置的元素值，注意时值middleValue，不需要将其与最后的元素交换，然后使用2个指针从头和尾开始向后和向前进行遍历，这里指针可以直接使用start和end，比较的逻辑还是一样的，如果array[start]<middleValue则start继续向后移动，如果array[end]>middleValue则end继续向前移动，当遇到array[end]<=middleValue，array[start]>=middleValue时将array[start]与array[end]交换然后start++，end--；直到start>=end即交错时结束交换并返回此时的start值到quick()方法中进行继续的分界，此时这个返回的start作为待分界数组的分界点，之后分别对2个子数组进行分界即可，但是这里千万千万注意，有一个麻烦的细节，在得到int middle=this.partition(array,start,end)即数组的分界点后，通过递归调用quick()方法对两个子数组进行分界，此时采取的分界方式是[start,middle-1]和[middle,end即为：
this.quick(array, start, middle-1);
this.quick(array, middle , end);
为什么不是用：
this.quick(array, start, middle);
this.quick(array, middle+1 , end);
进行分界：如果使用[start,middle]和[middle+1,end]进行分界，那么存在一种情况：对于quick(0,2)即
对于[0][1][2]3个元素，是顺序排列的，交换时在start=end=1之后start=2，end=0；此时返回的middle=2，即以[2]作为数组[0,2]的分界，相当于没有进行分界，于是递归调用quick(array,0,2)一直陷入死循环，死递归，最终导致栈溢出。而采用[start,middle-1]和[middle,end]可以避免这个问题。记住这个问题直接避免即可。
quick()是一个递归方法，它的结束的边界条件还是if(start>=end) return;
总结：快速排序方法逻辑还是很清楚直接的，和归并排序一样，需要写2个方法，quickSort(array,n)是调用者方法；写一个quick(array,start,end)方法，这是一个递归方法，用来计算intmiddle=partition(array,start,end);即数组[start,end]的分界点；然后递归调用quick(start,middle-1)方法和quick(array,middle,end)方法来对子数组进行分界；关键是写一个partition(array,start,end)方法，用来先找位置中间值middleVlaue，然后将数组元素分界到middleValue的2边，然后返回新的分界点位置，即start的位置，将其返回到quick()方法中作为int middle即数组分界的分界点。
import java.util.*;
//快速排序，使用分治思想，通过递归来分割地解决问题，关键是返回分界之后分界点的位置，以便进行下一次的递归分界
public class QuickSort {
public int[] quickSort(int[] A, int n) {
//特殊输入
if(A==null||A.length<=0) return A;
//调用一个递归的quick()方法来实现快速排序
this.quick(A,0,A.length-1);
return A;
}
//写一个递归方法quick()通过递归调用自己来不断分割给定的区间,假设执行quick(array,start,end)方法后数组就完成排序
public voidquick(int[] array,int start,int end){
//递归方法一定要有递归结束的边界条件,本题结束的边界条件是要分割的区域只有一个元素
if(start>=end)return;
//调用partition()方法来对[start,end]范围的数组进行分界，并返回分界元素的位置下标
intmiddle=this.partition(array,start,end);
//递归调用divide()方法对已经得到的2个子数组进行分界，假设调用divide()方法后数组就可以对该范围完成分界
//if (middle > start + 1) {不需要写，递归终止条件已经可以终止递归
this.quick(array,start, middle-1);
//}
//if(middle<end) {不需要写，递归终止条件已经可以终止递归
this.quick(array,middle, end);
//}
}
//核心方法partition()，用来对[start,end]范围的数组进行分界并且返回分界值的新下标
public intpartition(int[] array,int start,int end){
//先找出分界值
int middleValue=array[(start+end)/2];
//以start，end作为2个指针，分别从数组的开头和结尾向后和向前遍历数组，符合交换条件时就进行交换，不符合就继续移动，直到2个指针交错或者重合（重合时交换与不交换等价，于是是否包含=号不影响结果）
while(start<=end){
//当数组有序排列时是start和end移动可能导致越界，但可以在后面交换条件时再进行判断
while(array[start]<middleValue){
start++;
}
while(array[end]>middleValue){
end--;
}
//可以防止越界的情况
if(start<=end){
//交换2个元素的位置
this.swap(array,start,end);
start++;
end--;
}
}
//start是大于等于分界值的第一个元素，下一次就在以此分界点形成的2个子数组中进行递归分界
return start;
}
//辅助函数，专门用来交换数组中的2个元素
public voidswap(int[] array,int p1,int p2){
inttemp=array[p1];
array[p1]=array[p2];
array[p2]=temp;
}
}
3.堆排序
所谓堆就是优先队列，就是先进先出的队列，即两端开口的序列。先将数组建立成为大小为n的大根堆，堆顶是最大的元素，将堆顶元素与堆末尾的元素进行交换，并让这个最大元素脱离数组，再对剩下的堆进行排序，通过对堆进行调整，使得最大元素调整到堆顶的位置，然后再将堆顶元素与最后的元素进行交换。
4.希尔排序（shell排序）
希尔排序是插入排序的改良版本，插入排序中前面是有序序列，每次将元素array[i]插入到前面有序序列中的合适位置，直接插入排序在插入时是逐个与前面的元素进行比较，即比较的步长为1，而希尔排序中，步长是一个逐渐变小的过程，对于数组6 5 3 1 8 7 2 4。例如第一次插入时步长为3，于是对于下标为0，1，2的元素不需要排序，从i=3即第4个元素开始进行插入，此时比较array[3]与array[0]的大小，如果array[3]<array[0],那么就将array[3]与array[0]进行交换，说明array[3]应该插入到前面去，然后i++在比较array[4]与array[1]的大小，进行相同的交换……例如对于i=7的最后一个元素，它先与array[4]=8进行交换，此时array[4]=4，然后再与array[4-3=1]=5进行比较交换，于是array[1]=4，再往前就越界了。即对于某一个步长k，在遍历元素时总是与array[i-k]，array[i-2*k]，array[i-3*k]进行比较和交换，即在步长k的情况下，对于一个元素array[i]，只需要考虑array[i-k]，array[i-2*3]，array[i-3*k]，array[i-4*k]……（直到向前越界）
这个序列即可，即抽取这几个元素组成一个新的当前待排序的子序列数组。比较大小决定是否进行交换，注意，一个元素array[i]要与之前的所有元素进行比较和交换，直到再往前跳跃时越界，不能仅仅比较和交换1次。对于步长k=3遍历比较交换完成后对k进行调整，通常是k--；按照相同的过程进行遍历比较交换，此时从元素i=k=2进行向前的比较，前面的2个元素不用考虑顺序，比较array[i-2]，array[i-2*2]，array[i-3*2]……直到向前越界。不管步长的大小如何调整，最终步长k一定要调整为k=1，即对所有元素进行逐一比较交换，使得整个数组完全有序。当步长k=1时的排序就是一个直接插入排序，直接插入排序其实和任意步长k的插入排序思想都是一样的，就是逐个比较array[i-k]，array[i-2*k]，array[i-3*k]，进行比较交换，只是当步长为k=1时的交换就是两个相邻元素之间的交换，前面插入排序中所将的将array[i]插入到前面有序序列中的j位置，其实就是通过对array[i-1],array[i-2],array[i-3]……逐一进行比较交换得到的，并不是找到位置后再将目标位置后面的元素统一向后移动一位，即还是基于比较交换的。
希尔排序进行了好几轮的插入排序，看似麻烦，但是当k值较大时，排序的粒度较粗，交换的元素较少，当k逐渐减小时，当前数组已经排序的程度逐渐提高，需要进行交换的次数变少，当最后k=1时只需要对很少的几个元素进行交换即可。根据统计规律可以得出结论，当步长k选择恰当时可以使得时间复杂度减少，最优时间复杂度为O(n)，最劣时间复杂度为O(n^2)，平均的时间复杂度为O(n^1.5)，空间复杂度为O(1).
其实对于冒泡排序、插入排序、选择排序、归并排序、希尔排序、堆排序、快速排序，都是基于元素交换来实现的。
在写代码时，步长总是从int feet=length/2开始，逐步减小为一半（常识，除以2用>>来实现），直到feet>0不再满足，即最后一次遍历的步长总是1；对于每一个步长feet，从i=feet（注意对于步长为1时就从第2个元素即i=1，因为总是与前面的元素进行比较，开始遍历数组）开始遍历数组，对于每个i，比较array[i]与array[i-feet]、array[i-feet-feet]（直到向前越界）进行比较。如果array[i]<前面某个元素就与它进行交换，直到找到在该步长数组中的合理的位置，即希尔排序是步长为feet的插入排序，插入的原理是不变的。希尔排序程序中有3层循环，最内层是对于元素array[i]遍历前面的元素找到合适的插入位置；中间层循环时对每个元素进行遍历和向前插入，外层循环时feet的遍历，由于feet是有限的，所以外层循环复杂度是常数C而不是n,对于内层的2层循环，最坏情形复杂度为O(n^2)，即等于直接插入排序，但是一般复杂度为O(n^1.5)。在写代码时对于不同步长feet的遍历可以使用for循环、while循环也可以使用递归，显然这里使用的是尾递归，很容易的，就是while循环的递归形式而已。
importjava.util.*;
//希尔排序，对步长feet进行循环或者递归地缩短，直到收敛为步长为1的直接插入排序
publicclass ShellSort{
public int[] shellSort(int[] A, int n){
//特殊输入
if (A == null || A.length<= 0)
return A;
//调用递归方法(尾递归)sort()来完成希尔排序
//注意习惯，题目中的数组通常以A给出，而自己喜欢用array表示数组，因此在调用函数时要记住传入的是A
sort(A, A.length >> 1);
//记得要返回排序后的结果
return A;
}
//写一个排序方法sort(array,feet)用来使用步长feet对数组进行插入排序，内部调用的方法最好写成private方法
private void sort(int[] array, intfeet) {
//递归一定要有停止递归的边间条件
if (feet <= 0)
return;
//按照步长feet对数组array进行插入排序
//初始位置为i=feet;初始的比较位置是index=index-feet
for (int i = feet; i <array.length; i++) {
// 要与前一个元素进行比较需要设置一个指针index,总是比较2个相邻的元素array[index]和array[index-feet],第一个元素是array[i]
int index = i;
//如果index-feet<0说明index不要再往前交换了，本元素已经找到了合适的位置，停止循环
while (index - feet>= 0) {
if(array[index] < array[index - feet]) {
//如果后一个元素比前一个元素要小，应该交换元素
this.swap(array,index, index - feet);
index-= feet;
} else {
// 注意，还要有else,如果后面的元素大于等于前面的元素，不需要交换，说明元素array[index]之前已经找到合适的位置于是不需要再往前遍历了，结束本元素array[i]的插入，开始下一个i的向前插入
break;
}
}
}
// 本步长的插入结束，此时需要更换步长feet，再次进行插入，于是递归调用sort()传入新的步长即可
this.sort(array, feet>> 1);
}
//写一个辅助函数用来交换2个元素
private void swap(int[] array, int p1,int p2) {
int temp = array[p1];
array[p1] = array[p2];
array[p2] = temp;
}
}