DualPivotSort源码jdk1.8阅读笔记

超、凢脫俗 2021-12-19 00:23 248阅读 0赞

java中给基本类型的数据排序使用的具体实现。它针对每种基本类型都做了实现，实现的方式有稍微的差异，  
但是思路都是相同的，所以这里只挑了int类型的排序来看。

public class Arrays { 	
    
    	/** * Sorts the specified array into ascending numerical order. * 将指定的数组按照自然顺序升序进行排序 * * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm * offers O(n log(n)) performance on many data sets that cause other * quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations. * * 实现笔记：这个排序算法是一个双轴快速排序，是三位大神(Vladimir Yaroslavskiy, * Jon Bentley, and JoshuaBloch)实现的。在许多特别数据集中，其它的快排算法的 * 效率降级为二次性能O(n^2),而这个算法都将能提供了O(nlog(n))的排序性能， * 这个算法的速度效率要优于传统单轴快速排序。 * * * * @param a the array to be sorted * 需要排序的数组 */
    	public static void sort(int[] a) { 
            DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
        }	
    }

/** * This class implements the Dual-Pivot Quicksort algorithm by * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm * offers O(n log(n)) performance on many data sets that cause other * quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations. * * 这个类由三位大神实现了双轴快速排序算法。算法提供了O(nlog(n))的排序性能 * 这个算法的速度效率要优于传统单轴快速排序。 * * All exposed methods are package-private, designed to be invoked * from public methods (in class Arrays) after performing any * necessary array bounds checks and expanding parameters into the * required forms. * * 这个类的方法都被封装了，可以在Arrays类中调用。 * 会进行必要的边界检测以及扩展参数到需要的形式 * * 三个作者 * @author Vladimir Yaroslavskiy * @author Jon Bentley * @author Josh Bloch * * 版本 jdk1.7后出现 * @version 2011.02.11 m765.827.12i:5\7pm * @since 1.7 */	
    final class DualPivotQuicksort { 	
    	
    	/** * Prevents instantiation. * 私有化构造方法，保护这个类不被实例化 */
        private DualPivotQuicksort() { }
    
        /* * Tuning parameters. * 协调参数 */
    
        /** * The maximum number of runs in merge sort. * 合并子列最大数量：待合并的序列的最大数量 * */
        private static final int MAX_RUN_COUNT = 67;
    
        /** * The maximum length of run in merge sort. * 合并子列最大长度：待合并的序列的最大长度 * */
        private static final int MAX_RUN_LENGTH = 33;
    
        /** * If the length of an array to be sorted is less than this * constant, Quicksort is used in preference to merge sort. * * 快速排序阀值：如果待排序数组的长度小于这个值， * 优先使用快速排序而不是归并排序 * */
        private static final int QUICKSORT_THRESHOLD = 286;
    
        /** * If the length of an array to be sorted is less than this * constant, insertion sort is used in preference to Quicksort. * * 插入排序阀值：如果待排序数组的长度小于这个值， * 优先考虑插入排序，而不是快速排序 * */
        private static final int INSERTION_SORT_THRESHOLD = 47;
    
        /** * If the length of a byte array to be sorted is greater than this * constant, counting sort is used in preference to inserti on sort. * * byte数组计数排序阀值：如果待排序的byte数组长度大于这个值 * 优先使用计数排序，而不是插入排序 * */
        private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
    
        /** * If the length of a short or char array to be sorted is greater * than this constant, counting sort is used in preference to Quicksort. * * short&char数组计数排序阀值：如果待排序的数组是short 或 char类型的 * 且数组长度大于这个值，将优先使用计数排序，而不是插入排序 * */
        private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
    
    	/** * 长度 >= 286 ==> 归并排序 * 47<= 长度 < 286 ==> 快速排序 * 长度 < 47 ==> 插入排序 * * 特别的： * byte数组长度大于29、short或char数组长度大于3200 ==> 计数排序 */
    	
    	
        /* * Sorting methods for seven primitive types. * 七种基本数据类型的排序方法 */
    
    
    
    	/** * Sorts the specified range of the array using the given * workspace array slice if possible for merging * * 如果可以进行归并，使用给定的工作数组片对数组 * 指定范围进行排序 * * * * @param a the array to be sorted * 待排序数组 * @param left the index of the first element, inclusive, to be sorted * 待排序数组指定范围的起始(左)索引(包括) * @param right the index of the last element, inclusive, to be sorted * 待排序数组指定范围的结束(右)索引(包括) * @param work a workspace array (slice) * 工作数组 * @param workBase origin of usable space in work array * 工作数组要使用的起始值 * @param workLen usable size of work array * 工作数组要使用的长度 */
     
    	static void sort(int[] a, int left, int right,
                         int[] work, int workBase, int workLen) { 
            // Use Quicksort on small arrays
    		// 对于小数组(长度小于286)直接使用快排
            if (right - left < QUICKSORT_THRESHOLD) { 
                sort(a, left, right, true);
                return;
            }
    
    		// 数组长度大于等于286时的处理方法
            /* * Index run[i] is the start of i-th run * (ascending or descending sequence). * * run[i] 意味着第i个有序数列开始的位置(升序或者降序) */
            int[] run = new int[MAX_RUN_COUNT + 1];
            int count = 0; run[0] = left;
    
            // Check if the array is nearly sorted
    		// 检查数组是不是已经接近有序状态
            for (int k = left; k < right; run[count] = k) { 
                if (a[k] < a[k + 1]) {  // ascending 升序
                    while (++k <= right && a[k - 1] <= a[k]);
                } else if (a[k] > a[k + 1]) {  // descending 降序
                    while (++k <= right && a[k - 1] >= a[k]);
    				//如果是降序的，找出k之后，把数列倒置
                    for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { 
                        int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                    }
                } else {  // equal 相等
                    for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { 
    					// 数列中有至少MAX_RUN_LENGTH的数据相等的时候，直接使用快排。
                        if (--m == 0) { 
                            sort(a, left, right, true);
                            return;
                        }
                    }
                }
    			
    
                /* * The array is not highly structured, * use Quicksort instead of merge sort. * * 数组并非高度有序，使用快速排序,因为数组中有序数列的个数超过了MAX_RUN_COUNT */
                if (++count == MAX_RUN_COUNT) { 
                    sort(a, left, right, true);
                    return;
                }
            }
    
            // Check special cases 检查特殊情况
            // Implementation note: variable "right" is increased by 1. 
            if (run[count] == right++) {  // The last run contains one element 最后一个有序数列只有最后一个元素
                run[++count] = right; // 那给最后一个元素的后面加一个哨兵
            } else if (count == 1) {  // The array is already sorted
    			// 整个数组中只有一个有序数列，说明数组已经有序啦，不需要排序了
                return;
            }
    
            // Determine alternation base for merge
    		// n不断翻倍直到不小于count,odd在0,1间不断交替
            byte odd = 0;
            for (int n = 1; (n <<= 1) < count; odd ^= 1);
    		//循环结束后,如果n是2的奇数次幂,odd==0, 如果n是2的偶数数次幂,odd==1
    		
    
            // Use or create temporary array b for merging 使用或者创建一个临时数组b用于合并
            int[] b;                 // temp array; alternates with a 临时数组,和a交换？
            int ao, bo;              // array offsets from 'left' 对应数组到left的距离
            int blen = right - left; // space needed for b 数组b所需要的空间(数组长度)
            if (work == null || workLen < blen || workBase + blen > work.length) { 
                work = new int[blen];
                workBase = 0;
            }
            if (odd == 0) { 
                System.arraycopy(a, left, work, workBase, blen);
                b = a;
                bo = 0;
                a = work;
                ao = workBase - left;
            } else { 
                b = work;
                ao = 0;
                bo = workBase - left;
            }
    
            // Merging 合并
    		// 最外层循环，直到count为1，也就是栈中待合并的序列只有一个的时候，标志合并成功
            // a 作原始数组，b 作目标数组
    		// count是待合并序列数量,last是合并后的第last个序列
            for (int last; count > 1; count = last){ 
    			
    			// 中层循环,遍历数组，将相邻的两个升序序列进行合并
    			// 循环一次后待合并的数组将减半
    			// k= 0 1 2 3 4 5 6 
    			// index= 0 3 5 7 9 11 12 
    			// -> last= 0 1 2 3
    			// lastindex= 0 5 9 12 
    			// last last+1 k==(last+2) 步长为2
    			// 这里的k,last,count都是run数组的索引
                for (int k = (last = 0) + 2; k <= count; k += 2) { 
    				// 内层循环
    				// 合并run[k-2] 与 run[k-1]两个序列
                    
    				
    				// 合并后,run数组重新赋值
    				// 把合并之后的数列向前推动
                    run[++last] = hi;
                }
    			
    			// 如果栈的长度为奇数，那么把最后落单的有序数列copy过对面
                if ((count & 1) != 0) { 
                    for (int i = right, lo = run[count - 1]; --i >= lo;
                        b[i + bo] = a[i + ao]
                    );
                    run[++last] = right;
                }
    			// 临时数组，与原始数组对调，保持a做原始数组，b 做目标数组
                int[] t = a; a = b; b = t;
                int o = ao; ao = bo; bo = o;
            }
        }
    	
    	
    	/** * Sorts the specified range of the array by Dual-Pivot Quicksort. * 对待排序数组指定范围进行双轴快速排序 * * @param a the array to be sorted * 待排序数组 * @param left the index of the first element, inclusive, to be sorted * 待排序数组指定范围的起始(左)索引(包括) * @param right the index of the last element, inclusive, to be sorted * 待排序数组指定范围的结束(右)索引(包括) * @param leftmost indicates if this part is the leftmost in the range * 说明指定的范围是否在数组的最左边 * */
        private static void sort(int[] a, int left, int right, boolean leftmost) { 
            int length = right - left + 1;
    
            // Use insertion sort on tiny arrays
    		// 小数组(length<47)使用插入排序
            if (length < INSERTION_SORT_THRESHOLD) { 
                if (leftmost) { 
                    /* * Traditional (without sentinel) insertion sort, * optimized for server VM, is used in case of * the leftmost part. * * 经典的插入排序，不带哨兵。对虚拟机作了优化，在leftmost情况下使用 * */
    				//i,j同时从起始位置开始，一次外循环后i,j同时自增
                    for (int i = left, j = i; i < right; j = ++i) { 
    					//获取当前要插入的元素a[i+1]
    					//这里不会越界,要排序的范围包含right,而循环条件是i<right
    					//因此a[i+1]将恰好可以取到最后一个元素a[right]
                        int ai = a[i + 1];
    					//插入比较,将要当前要插入的元素a[i+1]依次和
    					//前面的元素a[j]进行比较,找到要插入的位置以及进行移位
    					//直到找到第一个不大于ai的元素
                        while (ai < a[j]) { 
    						//还没找到,将比较的a[j]元素向右移动一个位置
                            a[j + 1] = a[j];
    						//如果找到起始位置了仍然没有找到,跳出循环
    						//在此处跳出循环后,j=left-1
                            if (j-- == left) { 
                                break;
                            }
                        }
    					//将要插入的元素插入到找到的位置：第一个不大于ai的元素后面
    					//如果没有找到,ai将插入到起始位置即left位置
                        a[j + 1] = ai;
                    }
                } else { 
    				//在leftmost=false情况下使用
                    /* * Skip the longest ascending sequence. * 首先跳过数组中开头的升序序列 */
    				 
    				
                    do { 
    					//左界大于等于右界表示数组已经是全部升序状态
    					//直接返回即可
                        if (left >= right) { 
                            return;
                        }
                    } while (a[++left] >= a[left - 1]);
    				//当不是升序了就跳出循环
    				
    				/* *等价代码 while(true){ if (left >= right) { return; } //a[left+1]这里不会越界 if(a[left+1] < a[left]){ break; } left++; } */
    				
    				
                    /* * Every element from adjoining part plays the role * of sentinel, therefore this allows us to avoid the * left range check on each iteration. Moreover, we use * the more optimized algorithm, so called pair insertion * sort, which is faster (in the context of Quicksort) * than traditional implementation of insertion sort. * * 这里我们使用了更加高效算法,称为成对插入排序方法 * 它将快于传统的插入排序(在快排算法中) * 因为这个分支执行的条件是左边是有元素的 * 所以可以直接从left开始往前查找。 */
    				
    				// 初始化k为左边界
    				// 每次循环开始是left先自增后,再判断是否达到右边界
    				// 每次循环结束后left会再次自增,然后将k同步到left的值
    				// 因此每次循环后k和left都会以 step=2 递增
                    for (int k = left; ++left <= right; k = ++left) { 
    					// 这里有 left==k+1
    					// 初始化a1为前值, a2为后一个值
    					// 这两个值都是要当次循环待插入排序的值
    					// 一次循环插入2个值,所以叫成对插入排序方法
                        int a1 = a[k], a2 = a[left];
    					
    					// 如果前值小于后值 交换它们,保证a1>=a2
                        if (a1 < a2) { 
                            a2 = a1; a1 = a[left];
                        }
    					
    					// 插入a1代码部分,因为a1是大于等于a2的,所以大于a1的值必然大于a2
    					// 这样就能直接把a[k]右移2位而不会出现乱序
                        while (a1 < a[--k]) { 
                            a[k + 2] = a[k];
                        }
    					// 插入a1插入到对应位置:第一个不大于a1的元素后2位
    					// 这里进行了k值小处理,处理后k在a1插入后的位置前面
                        a[++k + 1] = a1;
    					
    					// 插入a2代码部分
    					// a2将从a1前2个位置开始比较进行插入排序
    					// 因为a1后面的值已经大于a1了也将必然大于a2,前面确保a1>=a2发挥了作用
                        while (a2 < a[--k]) { 
                            a[k + 1] = a[k];
                        }
                        a[k + 1] = a2;
                    }
    				
    				// 尾界处理: 因为是以步长为2进行插入排序的
    				// 最后一个元素可能未进行排序
    				// 这里将尾巴进行一次插入排序
                    int last = a[right];
    				
                    while (last < a[--right]) { 
                        a[right + 1] = a[right];
                    }
                    a[right + 1] = last;
                }
    			//成对插入排序方法结束
                return;
            }//插入排序代码段结束
    		
    		// 数组长度大于等于47,这里开始使用快排
    		
            // Inexpensive approximation of length / 7
    		// length / 7 的一种低复杂度的实现, 近似值(length * 9 / 64 + 1)
    		// 这个值用来确定轴位置
            int seventh = (length >> 3) + (length >> 6) + 1;
    
            /* * Sort five evenly spaced elements around (and including) the * center element in the range. These elements will be used for * pivot selection as described below. The choice for spacing * these elements was empirically determined to work well on * a wide variety of inputs. */
    		// 对5段靠近中间位置的数列排序，这些元素最终会被用来做轴(下面会讲)
            // 他们的选定是根据大量数据积累经验确定的
    		
    		// e3是中间值,其余4值都是根据中间值和seventh确定
    		// 可以发现这五个index都是基于数组中间索引均衡分布的
            int e3 = (left + right) >>> 1; // The midpoint
            int e2 = e3 - seventh;
            int e1 = e2 - seventh;
            int e4 = e3 + seventh;
            int e5 = e4 + seventh;
    
            // 对以上index对应的5个元素进行插入排序,这里是手写的排序,没有for循环
    		// 插入e2
            if (a[e2] < a[e1]) {  int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
    		// 插入e3
            if (a[e3] < a[e2]) {  int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
                if (t < a[e1]) {  a[e2] = a[e1]; a[e1] = t; }
            }
    		// 插入e4
            if (a[e4] < a[e3]) {  int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
                if (t < a[e2]) {  a[e3] = a[e2]; a[e2] = t;
                    if (t < a[e1]) {  a[e2] = a[e1]; a[e1] = t; }
                }
            }
    		// 插入e5
            if (a[e5] < a[e4]) {  int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
                if (t < a[e3]) {  a[e4] = a[e3]; a[e3] = t;
                    if (t < a[e2]) {  a[e3] = a[e2]; a[e2] = t;
                        if (t < a[e1]) {  a[e2] = a[e1]; a[e1] = t; }
                    }
                }
            }
    
            // Pointer 指针 (这里说的指针并不是C++中的指针,就是一个标记索引的变量)
            int less  = left;  // The index of the first element of center part 中区部分起始指针 
            int great = right; // The index before the first element of right part 右区部分前驱指针,待扫描区的结束指针
    		
    		// 如果五元素(已排序)均不相等,使用双轴快排算法
            if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) { 
                /* * Use the second and fourth of the five sorted elements as pivots. * These values are inexpensive approximations of the first and * second terciles of the array. Note that pivot1 <= pivot2. * * 使用5个元素中的2，4两个位置作为枢轴，他们两个大致处在数组三分位的位置上。 * * 需要注意的是pivot1 <= pivot2 第一个轴的不大于第二个轴(因为之前已经手动排序了) */
    			 
    			// 定义两个轴,并进行赋值
                int pivot1 = a[e2];
                int pivot2 = a[e4];
    
                /* * The first and the last elements to be sorted are moved to the * locations formerly occupied by the pivots. When partitioning * is complete, the pivots are swapped back into their final * positions, and excluded from subsequent sorting. * * 第一个和最后一个元素被放到两个轴所在的位置。当阶段性的分段结束后 * 他们会被分配到最终的位置并从子排序阶段排除 */
                a[e2] = a[left];
                a[e4] = a[right];
    
                /* * Skip elements, which are less or greater than pivot values. * (less great指针)跳过一些队首的小于pivot1的值，跳过队尾的大于pivot2的值 * 注意这里是前置++和--,这意味着必定跳过left和right */
                while (a[++less] < pivot1);
                while (a[--great] > pivot2);
    
                /* * Partitioning: 分割数组 * 将按照以下图示及说明分割数组:将?区部分元素按要求移动到对应的区域中:left/ center/ right -part * * 左区部分 中区部分 ?区部分 右区部分 * left part center part right part * +--------------------------------------------------------------+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | * +--------------------------------------------------------------+ * ^ ^ ^ * | | | * less k+ great * * Invariants: 恒成立表达式(注意开区间,闭区间) * * all in (left, less) < pivot1 左区部分恒小于pivot1 * pivot1 <= all in [less, k) <= pivot2 中区部分介于pivot1和pivot2之间 * all in (great, right) > pivot2 右区部分恒大于pivot2 * * * Pointer k is the first index of ?-part. * 指针k是 ?区部分 的起始索引值, great指针是终止索引值 */
    			 
    			// 外层循环
                outer:
    			// 初始化指针k,从less开始扫描到great
    			// 这里的外循环就是扫描 ?区部分 ,将?区部分元素移动三大区域中
    			// 每一次外循环后 ?区部分 都会缩小,期间需要调整less k great指针
    			// 当外循环结束,?区部分将完全消失,此时数组中的所有待排元素均分区完毕
                for (int k = less - 1; ++k <= great; ) { 
    				// 取出ak
                    int ak = a[k];
                    if (ak < pivot1) {  // Move a[k] to left part 
    					// 如果ak小于pivot1, 按照图示要求,我们将ak移至左区部分
    					// 就是将a[k]和a[less]互换位置,然后调整less指针即可
                        a[k] = a[less];
                        /* * Here and below we use "a[i] = b; i++;" instead * of "a[i++] = b;" due to performance issue. * * 这里使用"a[i] = b; i++;"的效率要好过'a[i++] = b'. !(why?) * */
    					// 由于左区部分新增一位元素,less指针右移一位
                        a[less] = ak;
                        ++less;
                    } else if (ak > pivot2) {  // Move a[k] to right part
    					// 如果ak大于pivot2, 按照图示要求,我们将ak移至右区部分
    					
    					// 右区部分指针在满足要求情况下尝试性左移
                        while (a[great] > pivot2) { 
    						// 如果右区指针恰好能够前移到与k指针位置,表示前扫描和后扫描会合
    						// 表示数组分割已经完成,直接跳出外层循环
                            if (great-- == k) { 
                                break outer;
                            }
                        }
    					
    					
                        if (a[great] < pivot1) {  // a[great] <= pivot2
    						// great指针值不仅小于pivot2还小于pivot1时
    						// 将great指针值移动到less处,less指针值移动到k处,k指针值移动到great处
    						// 这里左区增加了一个元素,less指针右移一位
                            a[k] = a[less];
                            a[less] = a[great];
                            ++less;
                        } else {  // pivot1 <= a[great] <= pivot2 
    						// 直接交换ak和a[great]
                            a[k] = a[great];
                        }
                        /* * Here and below we use "a[i] = b; i--;" instead * of "a[i--] = b;" due to performance issue. */
    					// 由于右区部分新增一位元素,great指针左移一位
                        a[great] = ak;
                        --great;
                    }
                }// 分割阶段结束出来的位置,上一个outer结束的位置
    			// 此出数组中的所有待排元素均分区完毕
    			
                // Swap pivots into their final positions
    			// 把两个放在外面的轴放回他们应该在的位置上 
    			// 把pivot1放在less指针的前一个位置,pivot2放在great指针的后一个位置
    			// 把对应的两个位置的原数据放到头和尾,因为头和尾之前已经被取出来放到初始轴所在位置上
    			// 因此不会导致数据丢失,分区的状态也依然能够保证
                a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
                a[right] = a[great + 1]; a[great + 1] = pivot2;
    
                // Sort left and right parts recursively, excluding known pivots
    			// 把左区部分和右区部分递归排序,不包含轴
                sort(a, left, less - 2, leftmost);
                sort(a, great + 2, right, false);
    			
    			
                /* * If center part is too large (comprises > 4/7 of the array), * swap internal pivot values to ends. * 如果中心区域太大，超过数组长度的 4/7。就先进行预处理，再参与递归排序。 * 预处理的方法是把等于pivot1的元素统一放到左边，等于pivot2的元素统一 * 放到右边,最终产生一个不包含pivot1和pivot2的数列，再拿去参与快排中的递归。 */
                if (less < e1 && e5 < great) { 
                    /* * Skip elements, which are equal to pivot values. * 跳过一些队首的等于pivot1的值，跳过队尾等于pivot2的值 */
                    while (a[less] == pivot1) { 
                        ++less;
                    }
    
                    while (a[great] == pivot2) { 
                        --great;
                    }
    
                    /* * Partitioning: 分割数组 * * left part center part right part * +----------------------------------------------------------+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | * +----------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (*, less) == pivot1 * pivot1 < all in [less, k) < pivot2 * all in (great, *) == pivot2 * * Pointer k is the first index of ?-part. */
                    outer:
                    for (int k = less - 1; ++k <= great; ) { 
                        int ak = a[k];
                        if (ak == pivot1) {  // Move a[k] to left part
                            a[k] = a[less];
                            a[less] = ak;
                            ++less;
                        } else if (ak == pivot2) {  // Move a[k] to right part
                            while (a[great] == pivot2) { 
                                if (great-- == k) { 
                                    break outer;
                                }
                            }
                            if (a[great] == pivot1) {  // a[great] < pivot2
                                a[k] = a[less];
                                /* * Even though a[great] equals to pivot1, the * assignment a[less] = pivot1 may be incorrect, * if a[great] and pivot1 are floating-point zeros * of different signs. Therefore in float and * double sorting methods we have to use more * accurate assignment a[less] = a[great]. */
                                a[less] = pivot1;
                                ++less;
                            } else {  // pivot1 < a[great] < pivot2
                                a[k] = a[great];
                            }
                            a[great] = ak;
                            --great;
                        }
                    }
                }// outer结束的位置 
    
                // Sort center part recursively
    			// 中区部分递归排序
                sort(a, less, great, false);
    
            } else {  // Partitioning with one pivot 
    			// 这里选取的5个元素刚好相等，使用传统的单轴三路快排
                /* * Use the third of the five sorted elements as pivot. * This value is inexpensive approximation of the median. * 在5个元素中取中值 */
                int pivot = a[e3];
    
                /* * Partitioning degenerates to the traditional 3-way * (or "Dutch National Flag") schema: * * left part center part right part * +-------------------------------------------------+ * | < pivot | == pivot | ? | > pivot | * +-------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot * all in [less, k) == pivot * all in (great, right) > pivot * * Pointer k is the first index of ?-part. */
                for (int k = less; k <= great; ++k) { 
                    if (a[k] == pivot) { 
                        continue;
                    }
                    int ak = a[k];
                    if (ak < pivot) {  // Move a[k] to left part
                        a[k] = a[less];
                        a[less] = ak;
                        ++less;
                    } else {  // a[k] > pivot - Move a[k] to right part
                        while (a[great] > pivot) { 
                            --great;
                        }
                        if (a[great] < pivot) {  // a[great] <= pivot
                            a[k] = a[less];
                            a[less] = a[great];
                            ++less;
                        } else {  // a[great] == pivot
                            /* * Even though a[great] equals to pivot, the * assignment a[k] = pivot may be incorrect, * if a[great] and pivot are floating-point * zeros of different signs. Therefore in float * and double sorting methods we have to use * more accurate assignment a[k] = a[great]. */
                            a[k] = pivot;
                        }
                        a[great] = ak;
                        --great;
                    }
                }
    
                /* * Sort left and right parts recursively. * All elements from center part are equal * and, therefore, already sorted. * * 左右两边还没有完全排序，所以递归解决 * 中心区只有一个值，不再需要排序 * */
                sort(a, left, less - 1, leftmost);
                sort(a, great + 1, right, false);
            }
        }
    }