1. 划分
划分是快速排序的根本机制。划分就是 将一个数组按照指定的值，划分为两部分。左侧小于指定值，右侧大于指定值。
思路：定义一个枢纽值，将指针定位到数组的两侧，相向移动。左侧指针遇到 应在右侧部分的项（即：数据项的值大于枢纽值）时停止，右侧指针遇到 应在左侧部分的项（即：数据项的值小于枢纽值）时停止，交换两个项的位置，重复这一过程，直至两个指针交错而过。
实现：
package com.test; /** * 划分 * @author xurongsheng * @date 2017年4月12日 下午3:29:00 * */ public class Partition { private long[] target;//待排序数据 public Partition(){ } public Partition(int maxLength){ target = new long[maxLength]; } public void setTargetValue(int index,long value){ target[index] = value; } public long getTargetValue(int index){ return target[index]; } public void display(){ System.out.print("A="); for (int i = 0; i < target.length; i++) { System.out.print(target[i]+" "); } System.out.println(" "); } /** * 划分 * 比较次数：N+1 或 N+2 * 交换次数：N/2 * 时间复杂度: O(N) * @author xurongsheng * @date 2017年4月12日 下午3:30:59 * @param left 数组的最左侧 * @param right 数组的最右侧 * @param pivot 枢纽值 */ public int partition(int left,int right,long pivot){ int leftPtr = left - 1; //左侧指针 int rightPtr = right + 1; //右侧指针 while(true){ while(leftPtr < right && target[++leftPtr] < pivot){ //左侧指针向右移动，直至遇到 值 <枢纽值的项 ; } while(rightptr> left && target[--rightPtr] > pivot){ //右侧指针向左移动，直至遇到 值>枢纽值的项 ; } if(leftPtr >= rightPtr){ //左侧指针 越过了 右侧指针，结束 break; }else{ swap(leftPtr,rightPtr); } } return leftPtr; } /** * 交换两个位置上的值 * @author xurongsheng * @date 2017年4月13日 下午2:50:29 * @param left * @param right */ public void swap(int left,int right){ long temp; temp = target[left]; target[left] = target[right]; target[right] = temp; } public static void main(String[] args) { int maxSize = 10; Partition p = new Partition(maxSize); for (int i = 0; i < maxSize; i++) { long n = (long) (Math.random()*199); p.setTargetValue(i,n); } p.display(); long pivot = 99; System.out.print("枢纽值:"+pivot); int pivotIndex = p.partition(0, p.target.length-1, pivot); System.out.println(",枢纽所在位置:"+pivotIndex); p.display(); } }
效率：
划分的时间复杂度为O（N） ，对于每一次的划分，都会有 N+1 或者 N+2次的比较。最多会有 N/2次的交换。
2. 快速排序
思路：将数组的最后一项作为枢纽值，进行划分，划分完后的 左右两部分，分别递归执行 划分。最终将实现排序
实现：
package com.test; /** * 快速排序 * @author xurongsheng * @date 2017年4月13日 下午2:58:27 * */ public class QuickSort { private long[] target;//待排序数据 public QuickSort(){ } public QuickSort(int maxLength){ target = new long[maxLength]; } public void setTargetValue(int index,long value){ target[index] = value; } public long getTargetValue(int index){ return target[index]; } public void display(){ System.out.print("A="); for (int i = 0; i < target.length; i++) { System.out.print(target[i]+" "); } System.out.println(" "); } /** * 快速排序 * 时间复杂度 * @author xurongsheng * @date 2017年4月13日 下午3:13:13 */ public void quickSort(){ recQuickSort(0,target.length-1); } public void recQuickSort(int left,int right){ if(right-left <= 0){ return; }else{ long pivot = target[right]; //最后一项作为 枢纽值 int pivotIndex = partition(left,right,pivot);// 划分并返回枢纽值的最终位置 recQuickSort(left,pivotIndex-1);//将左侧 递归划分 recQuickSort(pivotIndex+1,right);//将右侧 递归划分 } } public int partition(int left,int right,long pivot){ int leftPtr = left - 1; //左侧指针 int rightPtr = right; //右侧指针[由于将最后一项作为了枢纽值,所以指针无需再右移] while(true){ while(target[++leftPtr] < pivot){ //左侧指针向右移动，直至遇到 值 <枢纽值的项 ; } while(rightptr> 0 && target[--rightPtr] > pivot){ //右侧指针向左移动，直至遇到 值>枢纽值的项 ; } if(leftPtr >= rightPtr){ //左侧指针 越过了 右侧指针，结束 break; }else{ swap(leftPtr,rightPtr); } } swap(leftPtr,right); //将枢纽值与 划分后的右侧数组首项交换位置 return leftPtr; } /** * 交换两个位置上的值 * @author xurongsheng * @date 2017年4月13日 下午2:50:29 * @param left * @param right */ public void swap(int left,int right){ long temp; temp = target[left]; target[left] = target[right]; target[right] = temp; } public static void main(String[] args) { int maxSize = 16; QuickSort qs = new QuickSort(maxSize); for (int i = 0; i < maxSize; i++) { long n = (long) (Math.random()*99); qs.setTargetValue(i,n); } qs.display(); qs.quickSort(); qs.display(); } } 效率： 快速排序的时间复杂度依赖于 枢纽的选择。理想状态下，枢纽的值应当是被排序数据项的中间值。 快速排序 在最好的情况下的时间复杂度为 O（N*logN），最坏情况下的时间复杂度为 O（N²），平均的时间复杂度为 O（N*logN）另一种实现：
package com.test; /** * 快速排序[切割版] * @author xurongsheng * @date 2017年4月13日 下午4:22:09 * */ public class quickSort2 { private long[] target;//待排序数据 public quickSort2(){ } public quickSort2(int maxLength){ target = new long[maxLength]; } public void setTargetValue(int index,long value){ target[index] = value; } public long getTargetValue(int index){ return target[index]; } public void display(){ System.out.print("A="); for (int i = 0; i < target.length; i++) { System.out.print(target[i]+" "); } System.out.println(" "); } /** * 快速排序 * 时间复杂度 * @author xurongsheng * @date 2017年4月13日 下午3:13:13 */ public void quickSort(){ recQuickSort(0,target.length-1); } public void recQuickSort(int left,int right){ int size = right-left+1; if(size < 10){ //数据项小于10个时,执行插入排序 insertionSort(left, right); }else{ long pivot = medianOf3(left, right); //最左项、中间项、最右项，取中值作为 枢纽值 int pivotIndex = partition(left,right,pivot);// 划分并返回枢纽值的最终位置 recQuickSort(left,pivotIndex-1);//将左侧 递归划分 recQuickSort(pivotIndex+1,right);//将右侧 递归划分 } } public long medianOf3(int left,int right){ //将数组的最左侧的项、中间项、最右侧的项，排序 int center = (left + right) / 2; if(target[left] > target[center]){ swap(left,center); } if(target[left] > target[right]){ swap(left,right); } if(target[center] > target[right]){ swap(center,right); } //中间项即为 枢纽值，将至置换到右侧 swap(center,right-1); return target[right-1]; } /** * 插入排序 * @author xurongsheng * @date 2017年4月13日 下午4:41:08 * @param left * @param right */ public void insertionSort(int left,int right){ int in,out; for(out = left+1; out<=right; out++){ long temp = target[out]; in = out; while(in>left && target[in-1] >= temp){ target[in] = target[in-1]; --in; } target[in] = temp; } } public int partition(int left,int right,long pivot){ int leftPtr = left - 1; //左侧指针 int rightPtr = right; //右侧指针[由于将最后一项作为了枢纽值,所以指针无需再右移] while(true){ while(target[++leftPtr] < pivot){ //左侧指针向右移动，直至遇到 值 <枢纽值的项 ; } while(rightptr> 0 && target[--rightPtr] > pivot){ //右侧指针向左移动，直至遇到 值>枢纽值的项 ; } if(leftPtr >= rightPtr){ //左侧指针 越过了 右侧指针，结束 break; }else{ swap(leftPtr,rightPtr); } } swap(leftPtr,right); //将枢纽值与 划分后的右侧数组首项交换位置 return leftPtr; } /** * 交换两个位置上的值 * @author xurongsheng * @date 2017年4月13日 下午2:50:29 * @param left * @param right */ public void swap(int left,int right){ long temp; temp = target[left]; target[left] = target[right]; target[right] = temp; } public static void main(String[] args) { int maxSize = 16; quickSort2 qs = new quickSort2(maxSize); for (int i = 0; i < maxSize; i++) { long n = (long) (Math.random()*99); qs.setTargetValue(i,n); } qs.display(); qs.quickSort(); qs.display(); } }
说明：由于 枢纽的值对于排序的效率影响很大，为了避免出现最右侧的值偏小或者偏大的情况，可以去数组的第一个、最后一个、中间一个，从中选出中间值的项作为枢纽。方法medianOf3 就是选取中间值。这又带来另一个问题，三数据项取中的办法，首先要求数组的项数起码要大于3. 一个可行的办法是 小于3项的 手动排序. 3 就作为了 切割点，将排序方法分为了 手动排序和快速排序两种。 对于小于切割点的小数据，还可以用插入排序来处理。这样效率更高些，切割点也可以设置的高些，建议是9
