文档章节

快速3排序

黑妹妹牙膏
 黑妹妹牙膏
发布于 2014/08/19 17:49
字数 656
阅读 21
收藏 0
package com.victor.sort.algorithms;

import java.util.ArrayList;

import com.victor.sort.seeds.*;
import com.victor.sort.seeds.Seeds;

/**
 * 快速3排序
 * @author 黑妹妹牙膏
 *
 */
public class Quick3 extends SortAlgorithms {

	/**
	Algorithm
	# choose pivot
	swap a[n,rand(1,n)]

	# 3-way partition
	i = 1, k = 1, p = n
	while i < p,
	  if a[i] < a[n], swap a[i++,k++]
	  else if a[i] == a[n], swap a[i,--p]
	  else i++
	end
	→ invariant: a[p..n] all equal
	→ invariant: a[1..k-1] < a[p..n] < a[k..p-1]

	# move pivots to center
	m = min(p-k,n-p+1)
	swap a[k..k+m-1,n-m+1..n]

	# recursive sorts
	sort a[1..k-1]
	sort a[n-p+k+1,n]
	Properties
	■Not stable 
	■O(lg(n)) extra space 
	■O(n2) time, but typically O(n·lg(n)) time 
	■Adaptive: O(n) time when O(1) unique keys 
	Discussion
	The 3-way partition variation of quick sort has slightly higher overhead compared to the standard 2-way partition version. Both have the same best, typical, and worst case time bounds, but this version is highly adaptive in the very common case of sorting with few unique keys. 

	The 3-way partitioning code shown above is written for clarity rather than optimal performance; it exhibits poor locality, and performs more swaps than necessary. A more efficient but more elaborate 3-way partitioning method is given in Quicksort is Optimal by Robert Sedgewick and Jon Bentley. 

	When stability is not required, quick sort is the general purpose sorting algorithm of choice. Recently, a novel dual-pivot variant of 3-way partitioning has been discovered that beats the single-pivot 3-way partitioning method both in theory and in practice. 
	*/
	
	@Override
	protected ArrayList<Integer> doSort(ArrayList<Integer> Alist) {
		return sort(Alist,0,Alist.size()-1);
	}
	
	private ArrayList<Integer> sort(ArrayList<Integer> Alist,int from,int end) {
		if(from >= end) return Alist;
		ArrayList<Integer> a = Alist;
		int n = end - from;
		//choose pivot
		java.util.Random rd = new java.util.Random();
		int pivot = rd.nextInt(n) + from;
		
//		print(a);
		//swap a[n,rand(1,n)]
		int temp = a.get(end);
		a.set(end, a.get(pivot));
		a.set(pivot, temp);
		moveMentIncrease();
//		System.out.println("pivot:"+pivot);
//		print(a);
		// 3-way partition
		int i=from,k = from,p=end;
		while(i<p)
		{
			if(a.get(i)<a.get(end))
			{
				
				//swap a[i++,k++]
				temp = a.get(k);
				a.set(k, a.get(i));
				a.set(i, temp);
				moveMentIncrease();
//				print(a);
				k++;
				i++;
//				System.out.println("a.get("+i+")<a.get("+end+") swap a[i++,k++]");
//				System.out.println("k:"+k+" i:"+i);
			}
			else
			{
				int ai = a.get(i);
				int aend = a.get(end);
				if(ai==aend)
				{
					// swap a[i,--p]
					p--;
					temp = a.get(p);
					a.set(p, a.get(i));
					a.set(i, temp);
					moveMentIncrease();
//					print(a);
//					System.out.println("a.get("+i+")==a.get("+end+") swap a[i,--p]");
//					System.out.println("p:"+p+" i:"+i);
				}
				else
				{
					i++;
//					System.out.println("a.get("+i+")>a.get("+end+")");
//					System.out.println("i:"+i);
				}
			}
		}
		if(p==from) return a;
		//m= min(p-k,n-p+1);
		int m = p-k<end-p+1?p-k:end-p+1;
		
//		print(a,k,p,from,end);
		for(int swapi=0;swapi<m;swapi++)
		{
			temp = a.get(k+swapi);
			a.set(k+swapi, a.get(end-(m-swapi-1)));
			a.set(end-(m-swapi-1), temp);
			moveMentIncrease();
		}
		int fromK = k-1;
		int endk = k+end-p+1;
		a = sort(a,from,fromK);
		a = sort(a,endk,end);
		return a;
	}
	
	public void print(ArrayList<Integer> a,int k,int p,int from,int end)
	{
		System.out.println("Items after sorted:");
		System.out.println("#######################################");
		for(int i=0;i<a.size();i++)
		{
			boolean selected = false;
			if(i==from)
			{
				//System.out.println("[-"+i+"] : "+a.get(i));
				//selected = true;
			}
			if(i==end)
			{
				//System.out.println("[+"+i+"] : "+a.get(i));
				//selected = true;
			}
			if(i==k)
			{
				System.out.println("["+i+"] : "+a.get(i));
				selected = true;
			}
			if(i==p)
			{
				System.out.println("[p"+i+"] : "+a.get(i));
				selected = true;
			}
			if(!selected) System.out.println(i+": "+a.get(i));
		}
		System.out.println("#######################################");
	}

	@Override
	public String getName() {
		return "Quick3";
	}
	
	public static void main(String[] args)
	{
		Seeds seed1 = new Random();
		Seeds seed2 = new NearSorted();
		Seeds seed3 = new Reversed();
		Seeds seed4 = new FewUniqueKeys();
		SortAlgorithms SA = new Quick3();
		SA.sort(seed1,800);
		SA.sort(seed2,800);
		SA.sort(seed3,800);
		SA.sort(seed4,800);
		//SA.print();
	}

}


© 著作权归作者所有

上一篇: 根排序
下一篇: 快速排序
黑妹妹牙膏
粉丝 23
博文 35
码字总数 23081
作品 0
杭州
程序员
私信 提问
list map set总结

括号为是否线程安全 list: LinkedList(no) ArrayList(no) Vector(yes) Stack(yes) map: HashMap(no) LinkedHashMap(no) HashTable(yes) WeakHashMap TreeMap set: HashSet(no) LinkedHashSet......

五大三粗
2015/07/23
44
0
Navicat 如何进行表单查看

Navicat 表单查看方便表单查看、更新或删除数据,显示当前的记录:栏位名及其值。表单的弹出菜单包括这些功能:设置栏位值为 Null 或空白字符串、使用当前栏位值为筛选、设置表单查看格式及更...

Navicat数据库管理工具
2016/04/28
453
0
十二、MySQL中常用的SQL优化 - 系统的撸一遍MySQL

插入优化 MyISAM批量导入 非空的表导入的时候会同时处理索引,导致导入效率低下,所以通过以下方式可以快速导入。 InnoDB批量导入 1、按主键顺序导入,InnoDB的数据按主键排列的B+Tree结构,...

logbird
2016/11/14
97
0
Lucene4.3开发之第五步之融丹筑基(五)

排序是对于全文检索来言是一个必不可少的功能,在实际运行中,排序功能在某些时候给我们带来了很大的方便,比如在淘宝、京东等一些电商网站我们可能通过排序来快速找到价格最便宜的商品,或者...

heroShane
2014/02/21
145
0
lucene4.7 之排序(四)

排序是对于全文检索来言是一个必不可少的功能,在实际运用中,排序功能能在某些时候给我们带来很大的方便,比如在淘宝,京东等一些电商网站我们可能通过排序来快速找到价格最便宜的商品,或者...

一枚Sir
2014/04/10
6.1K
0

没有更多内容

加载失败,请刷新页面

加载更多

PostgreSQL 11.3 locking

rudi
今天
5
0
Mybatis Plus sql注入器

一、继承AbstractMethod /** * @author beth * @data 2019-10-23 20:39 */public class DeleteAllMethod extends AbstractMethod { @Override public MappedStatement injectMap......

一个yuanbeth
今天
15
1
一次写shell脚本的经历记录——特殊字符惹的祸

本文首发于微信公众号“我的小碗汤”,扫码文末二维码即可关注,欢迎一起交流! redis在容器化的过程中,涉及到纵向扩pod实例cpu、内存以及redis实例的maxmemory值,statefulset管理的pod需要...

码农实战
今天
4
0
为什么阿里巴巴Java开发手册中不建议在循环体中使用+进行字符串拼接?

之前在阅读《阿里巴巴Java开发手册》时,发现有一条是关于循环体中字符串拼接的建议,具体内容如下: 那么我们首先来用例子来看看在循环体中用 + 或者用 StringBuilder 进行字符串拼接的效率...

武培轩
今天
9
0
队列-链式(c/c++实现)

队列是在线性表功能稍作修改形成的,在生活中排队是不能插队的吧,先排队先得到对待,慢来得排在最后面,这样来就形成了”先进先出“的队列。作用就是通过伟大的程序员来实现算法解决现实生活...

白客C
今天
93
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部