|
快速排序算法实现之（三路划分遍历，解决与划分元素相等元素的问题） 算法原理：使用三路划分策略对数组进行划分（也就是荷兰国旗问题，dutch national flag problem）。这个实现是对实现二的改进，它添加处理等于划分元素的值的逻辑，将所有等于划分元素的值集中在一起，并且以后都不会再对他们进行划分。本算法中使用四个标示值进行操作。使用left和right同时向中间遍历时，当left遇见等于划分元素时，就与iflag指向的值进行交换（iflag指向的当前值到最左端表示left在过程中遇见的等于划分元素的值部分），同理，右边也使用同样的逻辑完成对等于划分元素的处理。最后分别交换左右部分的相等值（left和iflag对应交换，right和rflag对应交换），由于需要返回两个标记值，所以将partition和quicksort合并成一个方法。
算法代码： void quickSort_3(int *array, int l, int r) { /** * 由于三路划分中有可能有两个不同的划分点，所以不能 * 使用函数直接返回，这里将partition和quickSort驱动 * 程序结合成一个方法； * */ if(l>=r) return; /** * 选择pivot划分元素，并将其与array[r]交换 * */ int pivot, temp; pivot=l+rand()%(r-l+1); temp=array[pivot]; array[pivot]=array[r]; array[r]=temp; /** * 双向扫描： * left和right都为主动移动 * lflag和rflag为被动移动 * */ int left=l, lflag=l; int right=r-1, rflag=r-1; while(true) { while(array[left]<=array[r] && left * 如果array[left]与pivot相等，则将其交换到 * lflag当前指向的元素 * */ if(array[left]==array[r]) { temp=array[left]; array[left]=array[lflag]; array[lflag]=temp; lflag++; } left++; } while(array[right]>=array[r] && right>=l) { /** * 如果array[right]与pivot相等，则将其交换到 * rflag当前指向的元素 * */ if(array[right]==array[r]) { temp=array[right]; array[right]=array[rflag]; array[rflag]=temp; rflag--; } right--; } if(left>=right) break; /** * 将左边大于pivot的元素与右边小于pivot的元素进行 * 交换 * */ temp=array[left]; array[left]=array[right]; array[right]=temp; left++;right--; } /** * 由于left和lflag指向的当前元素都是即将需要处理的元素， * 也就是当处理结束之后，他们都需要左移一步才是已经处理好的 * 元素； 将等于pivot的元素交换到中间 * */ lflag--;left--; while(lflag>=l) { temp=array[left]; array[left]=array[lflag]; array[lflag]=temp; left--;lflag--; } /** * 由于right和rflag指向的当前元素都是即将需要处理的元素， * 也就是当处理结束之后，他们都需要右移一步才是已经处理好的 * 元素；将等于pivot的元素交换到中间 * 注意：由于pivot本身也需要移动到中间，所以这里的判断条件 * 包含r * */ rflag++;right++; while(rflag<=r) { temp=array[right]; array[right]=array[rflag]; array[rflag]=temp; right++;rflag++; } /** * 最终递归处理左右子序列部分 * */ quickSort_3(array, l, left); quickSort_3(array, right, r); } int main() { int array[]={2,5,8,2,1,6}; quickSort_3(array,0,5); for(int i=0;i<6;i++) printf("%d,",array[i]); return 1; } 算法说明： 即使没有重复键，最后的移动开销就不需要，即使有也是线性问题；较好的处理了划分元素的相等值问题，没有多余的性能损耗，所以运行时间为线性N。 此程序将序列划分成三个部分：小于划分元素的元素（放置于a[l]到a[left]）；等于划分元素的元素（放置于a[left+1]到a[right-1]）；大于划分元素的元素（放置于a[right]到a[r]）；由于直接进行如此划分不是特别方便，所以首先将left和right指针分别遇到的等于pivot的元素放置到最左边和最右边，当处理完所有元素之后才将两边等于pivot的元素拷贝到序列中间，并且分别递归处理left左边的序列和right右边的序列； 快速排序算法实现之（三元中值法，InsertSort处理小子文件，减少递归栈） 算法原理：此算法利用insert算法处理小子文件，从而有效减小系统栈空间的耗用；使用三元中值（Median-of-Three-Method）划分策略在数组的左，中，右抽样，并使用他们的中值作为划分元素，然后使用小子文件（放弃对小序列使用递归调用）策略对序列元素小于11的子序列放弃使用递归，而是使用插入排序。也就是将每一次递归之前进行判断的if(l>=r) return;修改为当l和r相差一定大小的时候就调用Insertion Sort。使用Probabilistic Algorithm（随机取值）获取的划分元素可以最高概率地获得好性能。Median-of-Three Method（取头，中，尾三处的中间大小元素）获取的划分元素可以更好地获取高性能（减少算法平均时间的10%） 算法代码： void insertSort(int *array, int l, int r); int partition_4(int *array, int l, int r) { int temp; int pivot; /** * 获取array[l],array[(l+r)/2], array[r] * 的中间值 * */ if(array[l]<=array[(l+r)/2]<=array[r] || array[r]<=array[(l+r)/2]<=array[l]) pivot=array[(l+r)/2]; else if(array[(l+r)/2]<=array[r]<=array[l] || array[l]<=array[r]<=array[(l+r)/2]) pivot=array[r]; else if(array[(l+r)/2]<=array[l]<=array[r] || array[r]<=array[l]<=array[(l+r)/2]) pivot=array[l]; temp=array[pivot]; array[pivot]=array[r]; array[pivot]=temp; /** * 双向扫描： * left从array的左边l处开始向右处理，直到r-1 * right从array的右边r-1处开始向左处理，直到l * left和right都是主动移动 * */ int left=l, right=r-1; while(true) { /** * left左边的元素为小于等于array[r]的元素 * 并注意array[r]为最大值的情况，left会一直 * 移动到r * */ while(array[left]<=array[r] && left<> left++; /** * right右边的元素为大于array[r]的元素 * 并注意array[r]为最小值的情况，right会一直 * 移动到l-1 * 这里仅使用大于的逻辑关系还可以避免当array * 都是相同元素的情况时指针交叉的发生 * */ while(array[right]>array[r] && right>=l) right--; /** * 有四种序列情况： * 1. 一般情况：left和right在序列中间的某个元素交叉 * 2. array[r]是最大值情况：left移动到r,right在r-1 * 3. array[r]是最小值情况：left在l，right移动到l-1 * 4. array所有元素为同一个值：left移动到r，right在r-1 * */ if(left>=right) break; /** * 交换元素 * */ temp=array[left]; array[left]=array[right]; array[right]=temp; left++;right--; } /** * 最终将array[r]的pivot元素与array[left]进行交换 * 由于此时的array[right]比array[r]小，所以只能交换 * array[left] * */ temp=array[left]; array[left]=array[r]; array[r]=temp; return left; } void quickSort_4(int *array, int l, int r) { /** * 当序列大小小于11的时候，假设此时系统堆栈的开销已经 * 大于处理递归序列本身的开销，则递归调用具有低效率， * 所以直接使用插入排序进行排序 * */ if(l-r>11) { insertSort(array, l, r); return; } /** * 利用partition方法获取划分元素 * */ int pivot=partition_4(array, l, r); /** * 划分元素已经到达最终位置，所以不用参与进一步处理 * 分别递归处理左右部分的元素 * */ quickSort_4(array, l, pivot-1); quickSort_4(array, pivot+1, r); } int main() { int array[]={2,5,8,2,1,6}; quickSort_4(array,0,5); for(int i=0;i<6;i++) printf("%d,",array[i]); return 1; } 算法说明： 优势：当系统递归栈的开销所占递归处理本身的比例较高时，快速排序性能较低，从而可以使用直接排序而非递归处理小子文件； 三元中值划分法表示一种抽样估算的思想，也就是使得划分元素尽量接近序列的中间值，具体的抽样可不限于三个，并且在代码实现的时候，需要考虑到循环内部操作的优化， 并且在实现过程中，为了优化栈操作，有的较小序列直接使用插入排序，可以从系统的角度提升算法的性能。 时间：运行时间可以在N㏒N的基础上减少10%。小子文件大小在5-25之间的性能改善相似 |
|
|
来自： kingwenguang > 《排序》
