`
flyingdutchman
  • 浏览: 358598 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

三向切分的快速排序算法:有大量重复元素的快速排序

阅读更多
        在之前的《快速排序及改进》中,已经对快速排序做了改进;但是在实际的工作环境中,经常会遇到含有大量重复元素的数组,也经常会对这样的数组排序,对这样的数组排序,快速排序性能还可以,但是可以有更大的性能改进,将快速排序的的时间复杂度有对数级提高到线性级别。
        三向切分的快速排序是对快速排序算法改进,特别适用于有大量重复元素的数组的排序,其时间复杂度介于N - NlogN之间,最好的时间复杂度接近于O(N),在没有重复元素的情况下有最坏的时间复杂度,空间复杂度为lgN。
        三向切分的快速排序算法在包括重复元素很多的情况下,要比归并排序和其他排序方法有更好的性能。
        三向切分的快速排序的过程是这样的:从左到右遍历数组一次,维护一个指针lt使得a[lo ... lt - 1]中的元素都小于v,一个指针gt使得a[gt + 1 ... hi]中的元素都大于v,一个指针使得a[lt...i - 1]中的元素都等于v,a[i ... gt]中的元素都还不确定,如下图所示:

        一开始i = lo,使用Comparable接口对a[i]进行三向比较处理:
        1)、a[i]小于v,将a[lt]和a[i]交换,然后将lt和i加一;
        2)、a[i]大于v,将a[gt]和a[i]交换,然后将gt减一;
        3)、a[i]等于v,然后将i加一;
        除非和切分元素相等,其他元素都会被交换。全部代码如下:
        /**
         * 三向切分的快速排序算法:有大量重复元素的快速排序 
         * @author jacky
         *
         */
 public class Quick3waySort extends SortBase{

	    public static void sort(Comparable[] a){
		    //为获得接近于最好的排序性能(最好的时间复杂度),首先将原数组“洗牌"
		    shuffle(a);
		    //开始排序
		    sort(a,0,a.length - 1);
	    }
	
	    /**
	     * 三向切分的快速排序实现
	     * @param a
	     * @param lo
	     * @param hi
	     */
	    private static void sort(Comparable[] a,int lo,int hi){
		    if(hi <= lo) return;
		    int lt = lo;
		    int i = lo + 1;
		    int gt = hi;
		    Comparable v = a[lo];
		    int cmp = 0;
		    while(i <= gt){
			    cmp = a[i].compareTo(v);
			    if(cmp < 0){
				    exch(a,lt++,i++);
			    }else if(cmp > 0){
				    exch(a,i,gt--);
			    }else{
				    i++;
			    }
		    }//现在a[lo ... lt - 1] < v = a[lt ... gt] < a[gt + 1 ... hi]成立
		    sort(a,lo,lt - 1);
		    sort(a,gt + 1,hi);
	    }
 }
        
  • 大小: 25.3 KB
分享到:
评论

相关推荐

    三向切分快速排序+插入排序

    快速排序的优化想法,对于三向切分排序的实践(文件中附 快速排序的 二向 三向切分、插入排序代码)(见 https://github.com/Zhangxuan-Xing/Quicksort-ThreeWay ,欢迎 关注 star)

    计算机C编程语言程序快速排序算法总结

    - **三向切分**:对于包含大量重复元素的序列,可以采用三向切分的快速排序,将序列分为小于、等于和大于基准的三个部分,这样可以减少不必要的比较和交换。 - **尾递归优化**:在递归调用时,如果子序列只有一个...

    超快速排序算法整理.pdf

    总结来说,超快速排序是快速排序的一种优化版本,通过三向切分策略提高了处理含有大量重复元素的数组时的效率。它具有较高的平均性能,原地排序和较小的空间复杂度,是实际应用中广泛使用的排序算法之一。不过,需要...

    C#快速排序算法

    - **三向切分**:对于有大量重复元素的数组,可以采用三向切分快速排序,将数组分为小于、等于和大于基准的三部分,减少比较和交换的次数。 - **随机化**:随机选择基准值可以避免最坏情况的发生,提高平均性能。 ...

    qk_快速排序算法源代码.zip

    快速排序还有一种优化版本——三向切分快速排序,它在处理包含大量重复元素的数组时效率更高。通过将数组分为小于枢轴、等于枢轴和大于枢轴三个部分,可以减少递归次数,提高性能。 总结来说,快速排序是一种非常...

    舍伍德——快速排序源码报告和算法分析

    7. **性能优化**:包括优化基准选取、使用插入排序处理小数组(因为快速排序对于小数组可能不如插入排序高效)、三向切分(处理含大量重复元素的数组)等。 8. **并行化**:舍伍德可能也研究了如何利用多核处理器...

    快速排序是一种高效的排序算法

    - **三向切分**:对于包含大量重复元素的数组,可以在分区时同时处理等于基准的元素,减少比较次数。 - **随机化选择基准**:随机选择基准元素可以降低最坏情况的发生概率,提高平均性能。 - **尾递归优化**:在递归...

    快速排序算法

    2. **三向切分快速排序**:对于包含大量重复元素的情况,传统的快速排序可能会退化到O(n^2)的复杂度。三向切分快速排序通过将数组分为小于、等于和大于基准值的三个部分,可以有效地处理这种情况。 3. **尾递归优化...

    基于python的排序算法-快速排序Quick Sort

    - 三向切分:对于含有大量重复元素的数组,采用三向切分快速排序可以提高效率。 - 插入排序优化:对于小规模数据或部分有序的数据,插入排序可能更快,因此可以在快速排序的基础上结合插入排序进行优化。 快速...

    算法设计中分而治之快速排序

    例如,三向切分是在分区过程中区分小于、等于和大于枢轴的元素,这样可以处理包含大量重复元素的数组,避免不必要的比较。 《算法设计与分析》这本书可能提供了关于快速排序的详细实现和分析,包括如何选择枢轴,...

    cpp-pdqsort一种新颖的模式消除快速排序算法

    2. **三向切分**:pdqsort采用三向切分快速排序的方式,可以更有效地处理包含大量重复元素的数组。在三向切分过程中,数组被分为小于、等于和大于基准的三部分,这有助于减少比较次数。 3. **插入排序的融合**:...

    快速排序 数据结构 实现

    - 使用三向切分快速排序,处理重复元素,减少比较次数。 - 对于小规模数据,可以考虑使用插入排序等简单排序算法,因为对于小数组,它们可能更快。 - 避免在递归深度过大时导致栈溢出,可以通过尾递归优化或使用迭代...

    基于python实现的快速排序算法.zip

    快速排序的优化策略包括三向切分法(处理重复元素)、随机化选择基准元素(防止最坏情况的发生)以及尾递归优化等。这些优化方法可以在保持效率的同时,提高算法的稳定性和适应性。 在实际编程中,Python的内置`...

    冒泡,快速排序的比较

    而优化的快速排序,如三向切分快速排序,能进一步提高效率,特别是对于含有大量重复元素的序列。 在实验中,我们应记录并分析比较次数和移动次数的变化,这有助于理解算法在不同数据结构上的表现。例如,如果某组...

    基于比较的排序算法汇总 选择排序法 插入排序法 归并排序法 快速排序法 堆排序法 冒泡排序法 希尔排序法

    在实际编程中,还可以结合各种优化策略,如三向切分快速排序、插入排序的二分查找优化等,进一步提高排序效率。对于这些算法的实现,可以参考`sorting-algorithm-master`这个压缩包中的代码,通过阅读和理解代码,能...

    快速排序算法基本思想、图解和代码示例

    快速排序是一种基于分治策略的高效排序算法,由C.A.R. Hoare在1960年提出。它的工作原理可以分为三个...同时,通过优化,例如随机化选择基准元素、三向切分等方法,可以进一步提高其性能,降低最坏情况发生的可能性。

    数据结构课程设计(快速排序).docx

    - 三向切分快速排序:处理大量重复元素时更为高效。 - 小数组使用插入排序:对于小数组采用插入排序,因为插入排序在小规模数据上的表现更好。 #### 三、快速排序的测试结果与分析 - **测试案例**:为了验证快速...

    快速排序优化的几种方法代码实现

    4. 三向切分快速排序(Three-way Quicksort):对于含有大量重复元素的数组,可以使用三向切分的方式。这种方法可以更高效地处理重复元素,避免了不必要的交换操作。以下是三向切分的基本流程: - 初始化三个指针...

    快速排序的非递归实现

    - **三向切分**:对于含有大量重复元素的数组,可以采用三向切分快速排序,将数组分为小于、等于和大于基准的三部分,这样可以减少比较次数。 总的来说,非递归快速排序是一种利用栈来实现的高效排序方法,它通过...

Global site tag (gtag.js) - Google Analytics