快速排序的简单分析

快速排序有很多版本,这里给出一种基础版本和一种典型加强版本,即三数取中版本.

基础版本

public class QuickSort { public static void quickSort(int[] a) { quickSort(a,0,a.length-1) } private static void quickSort(int[] a, int left, int right) { if (left >= right) { return; } int CUTOFF = partition(a, left, right,right); quickSort(a, left, CUTOFF - 1); quickSort(a, CUTOFF + 1, right); } private static int partition(int[] a, int left,int right,int pivot){ int leftPtr=left-1; int rightPtr=right; int pivotVal = a[pivot]; while (true) { while(a[++leftPtr]<pivotVal){} while(rightPtr>0&&a[--rightPtr]>pivotVal){} if (leftPtr >= rightPtr) { break; } else { exchange(a,leftPtr, rightPtr); } } exchange(a,leftPtr,right); return leftPtr; } private static void exchange(int[] a ,int x, int y) { int tmp = a[x]; a[x] = a[y]; a[y]=tmp; } }

三数取中

public class QuickSort_median3 { public static void quickSort(int[] a) { quickSort(a, 0, a.length - 1); } private static void quickSort(int[] a, int left, int right) { int size=right-left+1; if (size <= 3) { manualSort(a,left, right); return; } int median=median3(a,left,right); int CUTOFF = partition(a, left, right, median); quickSort(a, left, CUTOFF - 1); quickSort(a, CUTOFF + 1, right); } private static void manualSort(int[] a,int left, int right) { int size=right-left+1; if (size <= 1) { return; } if (size == 2) { if (a[left] > a[right]) { exchange(a, left, right); } } else { if (a[left] > a[right - 1]) { exchange(a, left, right - 1); } if ((a[left] > right)) { exchange(a, left, right); } if (a[right - 1] > right) { exchange(a,a[right - 1], a[right]); } } } private static int partition(int[] a, int left, int right, int pivot) { int leftPtr=left; int rightPtr=right-1; int pivotVal = a[pivot]; while (true) { while(a[++leftPtr]<pivotVal){} while(a[--rightPtr]>pivotVal){} if (leftPtr >= rightPtr) { break; } else { exchange(a,leftPtr,rightPtr); } } exchange(a,leftPtr,right-1); return leftPtr; } private static int median3(int[] a,int left, int right){ int center = (left + right) / 2; if (a[left] > a[center]) { exchange(a, left, center); } if (a[left] > a[right]) { exchange(a, left, right); } if (a[center] > a[right]) { exchange(a, center, right); } exchange(a,center,right-1); return right-1; } private static void exchange(int[] a ,int x, int y) { int tmp = a[x]; a[x] = a[y]; a[y]=tmp; } }

快速排序的难点不在于理解,而在于代码实现. 核心步骤是: 1. 指定某个值, 2. 把数组中所有小于这个数的数放在左边 3. 把数组中所有大于这个数的数放在右边 4. 对于左边的数组重复步骤12345 5. 对于右边的数组重复步骤12345

而在代码中有很多细节需要注意.

基础版快排

首先要有一个驱动程序,穿入一左一右两个指针

public static void quickSort(int[] a) { quickSort(a,0,a.length-1);//快排驱动,传入位置. }

直接选取最右的位置的值作为枢纽,写出快排框架:

private static void quickSort(int[] a, int left, int right) { if (left >= right) { return; } int CUTOFF = partition(a, left, right,right);//以最右位为枢纽. quickSort(a, left, CUTOFF - 1); quickSort(a, CUTOFF + 1, right); }

注意,此段程序为递归程序,所以参数必须为可变的.不能再内部指定left,right. 合格的递归应有恰当的跳出条件.左指针大于右指针的时候需要结束递归. 事实上partition方法承担了大部分任务.它负责内部的跳跃交换,最后返回归位后的枢纽位置.最后一个参数是初始枢纽,直接给为right. partition(a, left, right,right) 左递归,右递归.

quickSort(a, left, CUTOFF - 1); quickSort(a, CUTOFF + 1, right);

接下来是分割程序.分割承担了内部的跳跃任务,细节不太容易准确写对.

private static int partition(int[] a, int left,int right,int pivot){ int leftPtr=left-1;//由于下面的代码是先右移再判断,为了保证左边从第一个开始判断,故左指针提前向左多移动一位, int rightPtr=right;//虽然右指针是先左移再判断,但是由于最右是被选取的枢纽,所以无需参与.直接从right-1开始向左即可. int pivotVal = a[pivot]; while (true) { while(a[++leftPtr]<pivotVal){}//左指针与枢纽比较,尽可能右移.由于是先右移再比较,所以最后落在大于等于枢纽值的位置上.一定不会右越界,因为最右是枢纽. while(rightPtr>0&&a[--rightPtr]>pivotVal){}//右指针与枢纽比较,尽可能左移.由于先左移后比较,故只要right>0即可保证right-1>=0,不会左越界.最后落在小于等于pivot的位置. if (leftPtr >= rightPtr) { break; } else { exchange(a,leftPtr, rightPtr);//交换左右. } } exchange(a,leftPtr,right);//枢纽归位. return leftPtr; }

三数取中版快排

三数分割法在选取枢纽的环节做了优化,使平均效率更高.虽然代码量有所增加,但是反而使分割环节的细节好记了一些.

在基础版中,选取枢纽的方法是直接任命right.而如果right并非约等于中值而是约等于最大值或最小值,将会有最差O(N^2)的时间复杂度.而三数分割法大大降低了这样的可能性. 三数取中过程:

private static int median3(int[] a,int left, int right){ int center = (left + right) / 2;//算出中间位置 //将三个位置排序.此处正面影响了分割过程.使得两端的值无需参与比较,一定是左<=枢纽<=右. if (a[left] > a[center]) { exchange(a, left, center); } if (a[left] > a[right]) { exchange(a, left, right); } if (a[center] > a[right]) { exchange(a, center, right); } exchange(a,center,right-1);//最后把枢纽值置于倒数第二个位置. return right-1;//返回枢纽位置. }

分割过程:

private static int partition(int[] a, int left, int right, int pivot) { int leftPtr=left; int rightPtr=right-1; int pivotVal = a[pivot]; while (true) { while(a[++leftPtr]<pivotVal){} while(a[--rightPtr]>pivotVal){} if (leftPtr >= rightPtr) { break; } else { exchange(a,leftPtr,rightPtr); } } exchange(a,leftPtr,right-1); return leftPtr; }

与基础版类似,但是由于最左,最右,右倒2都已经被占据且排好序,故在指定比较指针的时候要稍稍改变.另外,由于左右两端都已经left<=pivotVal<=right,所以内部while循环时无需再判断边界,一定不会越界.

当数值小于等于3的时候,为了效率要求,我们单独为3个数写出排序.

private static void manualSort(int[] a,int left, int right) { int size=right-left+1; if (size <= 1) { return; } if (size == 2) { if (a[left] > a[right]) { exchange(a, left, right); } } else { if (a[left] > a[right - 1]) { exchange(a, left, right - 1); } if ((a[left] > right)) { exchange(a, left, right); } if (a[right - 1] > right) { exchange(a,a[right - 1], a[right]); } } }