stoogesort.java

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

/*
 * 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.
 */
//15 Oct 2007
package cn.edu.whu.iss.algorithm.unit07;

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

/**
 * Stooge sort
 * T(n) = 3T(2n/3)+O(1)
 * @author wpc
 *
 */
public class StoogeSort {

	private static Object[] element;
	
	public static void sort(Object[] element){
		StoogeSort.element = element;
		sort(0,element.length-1);
	}
	
	private static void sort(int p,int r){
		if(compare(element[p], element[r])>0){
			swap(element, p, r);
		}
		if(p+1>=r){
			return;
		}
		
		int k = (r+1-p)/3;
		
		sort(p,r-k);
		sort(p+k,r);
		sort(p,r-k);
	}
}