Quicksort

快排算法

经典快排算法

• 效率：O(log(n))

• 基本思路：分治思想——选择一个数组中的元素作为轴pivot，小于轴的放左边，大于等于轴的放右边，然后对左右两边进行递归。

• 改进：当出现多个等于轴的元素时将导致交换次数增多，因此需要使用单轴单向三分区——小于轴的放左边，等于轴的放中间，大于轴的放右边，对左右两边进行递归。

  • 具体算法：取第一个元素为轴，i指向等于轴元素集合的第一个元素，k指向未遍历的第一个元素，j指向未遍历的最后一个元素。k向右边移动，如果遇到的元素小于轴，k与i指向的元素交换后i自加一，k继续移动(即将该元素加入小于轴元素集合)；如果遇到的元素等于轴，k跳过该元素继续移动(即将该元素加入等于轴元素集合);如果遇到的元素大于轴，k与j指向的元素交换后j自减一，k继续移动(即将该元素加入大于轴元素集合)。k大于j结束比较

• 进一步改进：如果在遍历过程中，j指向的原本大于轴的元素被交换，也增加了了交换次数，因此使用单轴双向三分区。

  • 具体算法：如果遇到的元素大于轴，j向左移动直到遇到小于轴的元素，i与j指向的元素交换后k与j指向的元素交换，i自加一,j自减一，k自加一，或者遇到等于轴的元素，k与j指向的元素交换后k自加一，j自减一。

		//代码清单：
		public static void div3DescanQuicksort(int[] array,int start,int end){
			if (end-start>1) {
				int pivot=array[start];
				int i=start,k=start+1,j=end;
				while(k<=j){
					if(array[k]<pivot){
						swap(array,i,k);
						++k;
						++i;
					}
					else if(array[k]==pivot){
						++k;
					}
					else{
						while(array[j]>pivot){
							--j;
						}
						if(k<=j) {//此处必须先验证k是否仍旧小于等于j，否则当第一个元素即为最小时就会导致出错。		
							if(array[j]<pivot){
								swap(array,i,j);
								swap(array,j,k);
								++i;
							}
							if(array[j]==pivot){
								swap(array,j,k);
							}
							++k;
							--j;
						}
					}
				}
				div3DescanQuicksort(array,start,i-1);
				div3DescanQuicksort(array,k,end);	
			}
		}

Dual-Pivot Quicksort

• 效率：O(n log(n))
• 具体算法

	//in Java source code：值得注意的是java.util.DualPivotQuicksort类中实现了对各种基本数据类型的双轴双向快排才导致类代码量很大
	// Inexpensive approximation of length / 7 即sevennth=length/7
    int seventh = (length >> 3) + (length >> 6) + 1;

	//均匀地取从中间往两边取数
	int e3 = (left + right) >>> 1; // The midpoint
    int e2 = e3 - seventh;
    int e1 = e2 - seventh;
    int e4 = e3 + seventh;
    int e5 = e4 + seventh;

	// 对e1~e5进行插入排序，问题是为什么不使用循环结构？难道是这样效率更高？或者彩蛋？？不得而知
    if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }

    if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t;
        if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
    }
    if (a[e4] < a[e3]) { long 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; }
        }
    }
    if (a[e5] < a[e4]) { long 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; }
            }
        }
    }


	//按照单轴双向快排类似方法排成三个区间：<p1 | p1<=&<=p2 | >p2
	outer:
    for (int k = less - 1; ++k <= great; ) {
        long ak = a[k];
        if (ak < pivot1) { // Move a[k] to left part
            a[k] = a[less];
            /*
             * Here and below we use "a[i] = b; i++;" instead
             * of "a[i++] = b;" due to performance issue.
             */
            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];
                a[less] = a[great];
                ++less;
            } else { // pivot1 <= a[great] <= pivot2
                a[k] = a[great];
            }
            a[great] = ak;
            --great;
        }
    }
	
	//less-1和great+1放置在left和right以空出空间把p1和p2分别放置在less-1和great+1的位置
    a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
    a[right] = a[great + 1]; a[great + 1] = pivot2;

	// 左部和右部迭代快排：值得注意的是，左部必须传入参数leftmost表示该部是左部，原因在于，左部和右部将在数组长度小于插入排序阙值时使用不同的插入排序——左部使用经典插入排序，右部使用双点插入排序(速度更快)
	sort(a, left, less - 2, leftmost);
	sort(a, great + 2, right, false);
	
	//中部处理：如果中部长度大于数组长度的4/7，先将中部中等于p1和p2的数使用双轴双向快排方法分别放置到less之前和great之后，在对less到great之间的元素进行迭代快排。
	 if (less < e1 && e5 < great) {

	        while (a[less] == pivot1) {
	            ++less;
	        }
	
	        while (a[great] == pivot2) {
	            --great;
	        }
	        outer:
	        for (int k = less - 1; ++k <= great; ) {
	            long 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];
	
	                    a[less] = pivot1;
	                    ++less;
	                } else { // pivot1 < a[great] < pivot2
	                    a[k] = a[great];
	                }
	                a[great] = ak;
	                --great;
	            }
	        }
	    }
	    sort(a, less, great, false);
	  } else { 如果中部长度不大于数组长度的4/7，则使用以e3为轴的单轴双向快排进行排序
            long pivot = a[e3];
            for (int k = less; k <= great; ++k) {
                if (a[k] == pivot) {
                    continue;
                }
                long 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
                        a[k] = pivot;
                    }
                    a[great] = ak;
                    --great;
                }
            }
            sort(a, left, less - 1, leftmost);
            sort(a, great + 1, right, false);
        }