quicksort.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 208 行

/*
 * Copyright (C) 2000-2007 Wang Pengcheng <[e-mail]>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
//8 Oct 2007
package cn.edu.whu.iss.algorithm.unit07;

import static cn.edu.whu.iss.algorithm.basictools.BasicSortTool.*;
import cn.edu.whu.iss.algorithm.unit09.RandomizedSelect;

/**
 * Quick sort with two version.
 * @author wpc
 * @version 0.0.1
 */
public class QuickSort {
	/**
	 * Refer the elements waiting for sort
	 */
	private static Object[] element;
	
	/**
	 * Simple partition
	 * @param p
	 * @param r
	 * @return
	 */
	private static int partition(int p,int r){
		Object x = element[r];
		int i=p-1;
		for(int j=p;j<r;j++){
			if(compare(element[j], x)<=0){
				i++;
				swap(element,i,j);
			}
		}
		swap(element,i+1,r);
		return i+1;
	}
	
	/**
	 * Randomized partition
	 * @param p
	 * @param r
	 * @return
	 */
	private static int randomizedPartition(int p,int r){
		int i = randomInt(p,r);
		swap(element,r,i);
		return partition(p, r);
	}
	
	/**
	 * Get the partition between element[p..r]
	 * @param element
	 * @param p
	 * @param r
	 * @return
	 */
	public static int randomizedPartition(Object[] element,int p,int r){
		QuickSort.element = element;
		return randomizedPartition(p, r);
//		Object[] cl = null;
//		if(QuickSort.element!=null){
//			cl = QuickSort.element.clone();
//		}
//		QuickSort.element = element;
//		int i =  randomizedPartition(p, r);
//		QuickSort.element = cl;
//		return i;
	}
	
	private static int selectPartition(int p,int r){
		int i = RandomizedSelect.getNumber(element,(p+r+1)>>1);
		swap(element,r,i);
		return partition(p, r);
	}
	/**
	 * Hoare partition
	 * @param p
	 * @param r
	 * @return
	 */
	private static int hoarePartition(int p,int r){
		Object x = element[p];
		int i = p-1;
		int j = r+1;
		
		while(true){
			do{
				j--;
			}while(compare(element[j], x)>0);
			do{
				i++;
			}while(compare(element[i], x)<0);
			if(i<j){
				swap(element,i,j);
			}else{
				break;
			}
		}
		
		return j;
	}
	
	/**
	 * 
	 * @param element
	 */
	public static void hoareSort(Object[] element){
		QuickSort.element = element;
		hoareSort(0,element.length-1);
	}
	
	/**
	 * 
	 * @param p
	 * @param r
	 */
	private static void hoareSort(int p,int r){
		if(p<r){
			int q= hoarePartition(p, r);
			hoareSort(p,q-1);
			hoareSort(q+1,r);
		}
	}
	
	/**
	 * Quick sort the arrays by simple partition
	 * @param element
	 */
	public static void sort(Object[] element){
		QuickSort.element = element;
		sort(0,element.length-1);
	}
	
	/**
	 * Quick sort the arrays by simple partition
	 * @param element
	 */
	public static void randomizedSort(Object[] element){
		QuickSort.element = element;
		randomizedSort(0,element.length-1);
	}
	
	/**
	 * Sort the sub arrays p..r by the simple partition
	 * @param p
	 * @param r
	 */
	private static void sort(int p,int r){
		if(p<r){
			int q = partition(p, r);
			sort(p,q-1);
			sort(q+1,r);
		}
	}
	
	/**
	 * Sort the sub arrays p..r by the randomized partition
	 * @param p
	 * @param r
	 */
	private static void randomizedSort(int p,int r){
		if(p<r){
			int q = randomizedPartition(p, r);
			randomizedSort(p,q-1);
			randomizedSort(q+1,r);
		}
	}
	
	/**
	 * 
	 * @param element
	 */
	public static void selectSort(Object[] element){
		QuickSort.element = element;
		selectSort(0, element.length-1);
	}
	
	/**
	 * 
	 * @param p
	 * @param r
	 */
	private static void selectSort(int p,int r){
		if(p<r){
			int q = selectPartition(p, r);
			selectSort(p,q-1);
			selectSort(q+1,r);
		}
	}

}