无聊想到种排序方式,不知道属于什么排序

查了下原来也属于快排的一种实现,了解了

 

package com.fourfireliu.test;

public class MySort {
	//计算循环次数
	private static int count1 = 0;
	//计算互换次数
	private static int count2 = 0;
	
	
	public static void main(String args[]) {
		int[] testArray = {3,3,0,3,3};
		MySort qs = new MySort();
		qs.sort(testArray);
	}
	
	public void sort(int[] array) {
		if (array!=null&&array.length>1) {
			sort(array, 0, array.length-1);	
		}
		
		//打印结果
		System.out.println();
		for (int i:array) {
			System.out.print(i+" ");
		}
		
		System.out.println();
		System.out.println("Count1 is " + count1 + " and count2 is " + count2);
	}
	
	//排序基本方法入口
	private void sort(int[] array, int fromIndex, int endIndex) {
		if (isOutOfBound(array, fromIndex)||isOutOfBound(array, endIndex)||fromIndex>=endIndex) {
			return;
		}

		
		int mid = getMid(fromIndex, endIndex);

		int from = getFirstLarger(array, fromIndex, mid);
		int to = getFirstSmaller(array, endIndex, mid);

		//从开头结尾各找一个位置不对的,两者进行互换，直到其中一个先到达中点
		while (from!=-1&&to!=-1) {
			swap(array, from, to);
			from = getFirstLarger(array, from, mid);
			to = getFirstSmaller(array, to, mid);
		}

		//轮询剩下的，将目标数安置在合适位置
		int target = mid;

		if (from!=-1) {
			for (int count=from;count<mid;count++) {
				count1++;
				target = getSwapTarget(array, count, target);
			}
		}

		if (to!=-1) {
			for (int count=to;count>mid;count--) {
				count1++;
				target = getSwapTarget(array, count, target);
			}
		}

		//继续对子列进行如此操作
		sort(array, fromIndex, target-1);
		sort(array, target+1, endIndex);
	}
	
	//在目标数左边搜索第一个比目标数更大的
	private int getFirstLarger(int[] array, int fromIndex, int mid) {
		for (int i=fromIndex;i<mid;i++) {
			count1++;
			if (array[i]>array[mid]) {
				return i;
			} 
		}
		
		return -1;
	}
	
	//在目标数右边搜索第一个比它更小的
	private int getFirstSmaller(int[] array, int fromIndex, int mid) {
		for (int i=fromIndex;i>mid;i--) {
			count1++;
			if (array[i]<array[mid]) {
				return i;
			} 
		}
		
		return -1;
	}
	
	/**
	 * 如果顺序不对，则互换位置
	 * 
	 * @param array
	 * @param count
	 * @param target
	 * @return
	 */
	private int getSwapTarget(int[] array, int count, int target) {
		if (array[count]<array[target]&&count>target) {
			swap(array, count, target);
			target = count;
		}
		
		if (array[count]>array[target]&&count<target) {
			swap(array, count, target);
			target = count;
		}
		
		return target;
	}
	
	private void swap(int[] array, int a, int b) {
		int temp = array[a];
		array[a] = array[b];
		array[b] = temp;
		count2++;
	}
	
	private boolean isOutOfBound(int[] array, int index) {
		return index<0||index>=array.length;
	}
	
	private int getMid(int start, int end) {
		return (start+end)/2;
	}
}