首页 > 代码库 > 笔试算法题(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 }