首页 > 代码库 > 笔试算法题（54）：快速排序实现之三路划分, 三元中值法和插入排序处理小子文件
笔试算法题（54）：快速排序实现之三路划分, 三元中值法和插入排序处理小子文件
议题：快速排序算法实现之三（三路划分遍历，解决与划分元素相等元素的问题）
分析：
-
算法原理：使用三路划分策略对数组进行划分（也就是荷兰国旗问题，dutch national flag problem）。这个实现是对实现二的改进，它添加处理等于划分元素的值的逻辑，将所有等于划分元素的值集中在一起，并且以后都不会再对他们进行划分。 本算法中使用四个标示值进行操作。使用left和right同时向中间遍历时，当left遇见等于划分元素时，就与iflag指向的值进行交换 （iflag指向的当前值到最左端表示left在过程中遇见的等于划分元素的值部分），同理，右边也使用同样的逻辑完成对等于划分元素的处理。最后分别交 换左右部分的相等值（left和iflag对应交换，right和rflag对应交换），由于需要返回两个标记值，所以将partition和 quicksort合并成一个方法。
-
即使没有重复键，最后的移动开销就不需要，即使有也是线性问题；较好的处理了划分元素的相等值问题，没有多余的性能损耗，所以运行时间为线性N；
-
此程序将序列划分成三个部分：小于划分元素的元素（放置于a[l]到a[left]）；等于划分元素的元素（放置于a[left+1]到a[right- 1]）；大于划分元素的元素（放置于a[right]到a[r]）；由于直接进行如此划分不是特别方便，所以首先将left和right指针分别遇到的等 于pivot的元素放置到最左边和最右边，当处理完所有元素之后才将两边等于pivot的元素拷贝到序列中间，并且分别递归处理left左边的序列和 right右边的序列；
样例：
1 void quickSort_3(int *array, int l, int r) { 2 /** 3 * 由于三路划分中有可能有两个不同的划分点，所以不能 4 * 使用函数直接返回，这里将partition和quickSort驱动 5 * 程序结合成一个方法； 6 * */ 7 if(l>=r) return; 8 /** 9 * 选择pivot划分元素，并将其与array[r]交换 10 * */ 11 int pivot, temp; 12 pivot=l+rand()%(r-l+1); 13 temp=array[pivot]; 14 array[pivot]=array[r]; 15 array[r]=temp; 16 /** 17 * 双向扫描： 18 * left和right都为主动移动 19 * lflag和rflag为被动移动 20 * */ 21 int left=l, lflag=l; 22 int right=r-1, rflag=r-1; 23 while(true) { 24 25 while(array[left]<=array[r] && left<r) { 26 /** 27 * 如果array[left]与pivot相等，则将其交换到 28 * lflag当前指向的元素 29 * */ 30 if(array[left]==array[r]) { 31 temp=array[left]; 32 array[left]=array[lflag]; 33 array[lflag]=temp; 34 lflag++; 35 } 36 left++; 37 } 38 39 while(array[right]>=array[r] && right>=l) { 40 /** 41 * 如果array[right]与pivot相等，则将其交换到 42 * rflag当前指向的元素 43 * */ 44 if(array[right]==array[r]) { 45 temp=array[right]; 46 array[right]=array[rflag]; 47 array[rflag]=temp; 48 rflag--; 49 } 50 right--; 51 } 52 53 if(left>=right) break; 54 /** 55 * 将左边大于pivot的元素与右边小于pivot的元素进行 56 * 交换 57 * */ 58 temp=array[left]; 59 array[left]=array[right]; 60 array[right]=temp; 61 62 left++;right--; 63 } 64 /** 65 * 由于left和lflag指向的当前元素都是即将需要处理的元素， 66 * 也就是当处理结束之后，他们都需要左移一步才是已经处理好的 67 * 元素； 将等于pivot的元素交换到中间 68 * */ 69 lflag--;left--; 70 while(lflag>=l) { 71 temp=array[left]; 72 array[left]=array[lflag]; 73 array[lflag]=temp; 74 left--;lflag--; 75 } 76 /** 77 * 由于right和rflag指向的当前元素都是即将需要处理的元素， 78 * 也就是当处理结束之后，他们都需要右移一步才是已经处理好的 79 * 元素；将等于pivot的元素交换到中间 80 * 注意：由于pivot本身也需要移动到中间，所以这里的判断条件 81 * 包含r 82 * */ 83 rflag++;right++; 84 while(rflag<=r) { 85 temp=array[right]; 86 array[right]=array[rflag]; 87 array[rflag]=temp; 88 right++;rflag++; 89 } 90 /** 91 * 最终递归处理左右子序列部分 92 * */ 93 quickSort_3(array, l, left); 94 quickSort_3(array, right, r); 95 } 96 97 int main() { 98 int array[]={2,5,8,2,1,6}; 99 quickSort_3(array,0,5); 100 for(int i=0;i<6;i++) 101 printf("%d,",array[i]); 102 return 1; 103 }
议题：快速排序算法实现之四（三元中值法，InsertSort处理小子文件，减少递归栈）
分析：
-
算法原理：此算法利用insert算法处理小子文件，从而有效减小系统栈空间的耗用；使用三元中值（Median-of-Three-Method）划分 策略在数组的左，中，右抽样，并使用他们的中值作为划分元素，然后使用小子文件（放弃对小序列使用递归调用）策略对序列元素小于11的子序列放弃使用递 归，而是使用插入排序。也就是将每一次递归之前进行判断的if(l>=r) return;修改为当l和r相差一定大小的时候就调用Insertion Sort。使用Probabilistic Algorithm（随机取值）获取的划分元素可以最高概率地获得好性能。Median-of-Three Method（取头，中，尾三处的中间大小元素）获取的划分元素可以更好地获取高性能（减少算法平均时间的10%）；
-
优势：当系统递归栈的开销所占递归处理本身的比例较高时，快速排序性能较低，从而可以使用直接排序而非递归处理小子文件；
-
三元中值划分法表示一种抽样估算的思想，也就是使得划分元素尽量接近序列的中间值，具体的抽样可不限于三个，并且在代码实现的时候，需要考虑到循环内部操作的优化，并且在实现过程中，为了优化栈操作，有的较小序列直接使用插入排序，可以从系统的角度提升算法的性能；
-
时间：运行时间可以在N㏒N的基础上减少10%。小子文件大小在5-25之间的性能改善相似；
样例：
1 void insertSort(int *array, int l, int r); 2 3 int partition_4(int *array, int l, int r) { 4 5 int temp; 6 int pivot; 7 /** 8 * 获取array[l],array[(l+r)/2], array[r] 9 * 的中间值 10 * */ 11 if(array[l]<=array[(l+r)/2]<=array[r] || 12 array[r]<=array[(l+r)/2]<=array[l]) 13 pivot=array[(l+r)/2]; 14 else if(array[(l+r)/2]<=array[r]<=array[l] || 15 array[l]<=array[r]<=array[(l+r)/2]) 16 pivot=array[r]; 17 else if(array[(l+r)/2]<=array[l]<=array[r] || 18 array[r]<=array[l]<=array[(l+r)/2]) 19 pivot=array[l]; 20 21 temp=array[pivot]; 22 array[pivot]=array[r]; 23 array[pivot]=temp; 24 25 /** 26 * 双向扫描： 27 * left从array的左边l处开始向右处理，直到r-1 28 * right从array的右边r-1处开始向左处理，直到l 29 * left和right都是主动移动 30 * */ 31 int left=l, right=r-1; 32 while(true) { 33 /** 34 * left左边的元素为小于等于array[r]的元素 35 * 并注意array[r]为最大值的情况，left会一直 36 * 移动到r 37 * */ 38 while(array[left]<=array[r] && left<r) 39 left++; 40 /** 41 * right右边的元素为大于array[r]的元素 42 * 并注意array[r]为最小值的情况，right会一直 43 * 移动到l-1 44 * 这里仅使用大于的逻辑关系还可以避免当array 45 * 都是相同元素的情况时指针交叉的发生 46 * */ 47 while(array[right]>array[r] && right>=l) 48 right--; 49 /** 50 * 有四种序列情况： 51 * 1. 一般情况：left和right在序列中间的某个元素交叉 52 * 2. array[r]是最大值情况：left移动到r,right在r-1 53 * 3. array[r]是最小值情况：left在l，right移动到l-1 54 * 4. array所有元素为同一个值：left移动到r，right在r-1 55 * */ 56 if(left>=right) 57 break; 58 /** 59 * 交换元素 60 * */ 61 temp=array[left]; 62 array[left]=array[right]; 63 array[right]=temp; 64 65 left++;right--; 66 } 67 /** 68 * 最终将array[r]的pivot元素与array[left]进行交换 69 * 由于此时的array[right]比array[r]小，所以只能交换 70 * array[left] 71 * */ 72 temp=array[left]; 73 array[left]=array[r]; 74 array[r]=temp; 75 return left; 76 } 77 78 void quickSort_4(int *array, int l, int r) { 79 /** 80 * 当序列大小小于11的时候，假设此时系统堆栈的开销已经 81 * 大于处理递归序列本身的开销，则递归调用具有低效率， 82 * 所以直接使用插入排序进行排序 83 * */ 84 if(l-r>11) { 85 insertSort(array, l, r); 86 return; 87 } 88 /** 89 * 利用partition方法获取划分元素 90 * */ 91 int pivot=partition_4(array, l, r); 92 /** 93 * 划分元素已经到达最终位置，所以不用参与进一步处理 94 * 分别递归处理左右部分的元素 95 * */ 96 quickSort_4(array, l, pivot-1); 97 quickSort_4(array, pivot+1, r); 98 } 99 100 int main() { 101 int array[]={2,5,8,2,1,6}; 102 quickSort_4(array,0,5); 103 for(int i=0;i<6;i++) 104 printf("%d,",array[i]); 105 return 1; 106 }