sort.java

这里面包含有栈

package org.huhuiyu.datastructures;

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * 排序类
 */
public class Sort {
	/**
	 * 快速排序的最小限制
	 */
	public static final int MIN_LIMIT=10; 
	
	/**
	 * 冒泡(选择)排序
	 * 
	 * @param datas
	 *            要排序的数组
	 */
	public static void selectionSort(int[] datas) {
		boolean check;
		for (int i = 0; i < datas.length; i++) {
			check = true;
			// 交换相邻的数据，确保最大数被交换到最后的位置
			for (int j = 1; j < datas.length - i; j++) {
				if (datas[j] < datas[j - 1]) {
					Common.swap(datas, j, j - 1);
					check = false;
				}
			}
			if (check) { // 如果没有发生过交换表示数组已经正确排序了
				break;
			}
		}
	}

	/**
	 * 插入排序
	 * 
	 * @param datas
	 *            要排序的数组
	 */
	public static void insertionSort(int[] datas) {
		insertionSort(datas, 0, datas.length - 1);
	}

	/**
	 * 插入排序
	 * 
	 * @param datas
	 *            要排序的数组
	 * @param start
	 *            起始下标
	 * @param end
	 *            结束下标
	 */
	private static void insertionSort(int[] datas, int start, int end) {
		for (int i = start + 1; i <= end; i++) {
			int data = datas[i]; // 记下需要插入到合适位置的数据
			int j = i - 1;
			while (j >= 0 && data < datas[j]) { // 有序的情况就不用循环查找
				datas[j + 1] = datas[j]; // 未排序的数据被移动到后面的位置
				j--;
			}
			datas[j + 1] = data; // 将数据插入到空下来的位置
		}
	}

	/**
	 * 快速排序
	 * 
	 * @param datas
	 *            要排序的数组
	 */
	public static void quickSort(int[] datas) {
		quickSort(datas, 0, datas.length - 1);
	}

	/**
	 * 快速排序
	 * 
	 * @param datas
	 *            要排序的数组
	 * @param start
	 *            起始下标
	 * @param end
	 *            结束下标
	 */
	private static void quickSort(int[] datas, int start, int end) {
		if (!false) { //正确版本的快速排序
			if (end - start <= MIN_LIMIT) {
				insertionSort(datas, start, end);
			}
			else {
				int position = partition(datas, start, end);
				quickSort(datas, start, position - 1);
				quickSort(datas, position + 1, end);
			}
		}
		else { //不稳定的快速排序
			if (start < end) {
				int position = errorPartition(datas, start, end);
				quickSort(datas, start, position - 1);
				quickSort(datas, position + 1, end);
			}
		}
	}

	/**
	 * 分区排序
	 * 
	 * @param datas
	 *            要排序的数组
	 * @param start
	 *            起始下标
	 * @param end
	 *            结束下标
	 * @return 中点下标
	 */
	private static int errorPartition(int[] datas, int start, int end) {
		int basic = datas[start]; // 用区间的第1个记录作为基准数据
		while (start < end) // 从区间两端交替向中间扫描，直至start=end为止
		{
			// 虚拟排序过程：
			//                                s e
			// 18 32 37 38 22  4 24 21 34 17  0 9
			// 17 32 37 38 22  4 24 21 34 17  1 9
			// 17 32 37 38 22  4 24 21 34 32  1 8
			// 17  4 37 38 22  4 24 21 34 32  1 5
			// 17  4 37 38 22 37 24 21 34 32  2 5
			// 17  4 18 38 22 37 24 21 34 32  2 2
			
			// 从右向左扫描，查找第1个小于basic的记录
			while (start < end && datas[end] >= basic) {
				end--;
			}
			if (start < end) // 表示找到的第一个小于basic的纪录
			{
				datas[start] = datas[end];
				start++;
			}
			// 从左向右扫描，查找第1个关键字大于basic的记录
			while (start < end && datas[start] <= basic) {
				start++;
			}
			if (start < end) // 表示找到的第一个大于basic的纪录
			{
				datas[end] = datas[start];
				end--;
			}
		}
		datas[start] = basic; // 基准记录已被最后定位
		return start; // 将中点位置返回
	}
	
	/**
	 * 分区排序
	 * 
	 * @param datas
	 *            要排序的数组
	 * @param start
	 *            起始下标
	 * @param end
	 *            结束下标
	 * @return 中点下标
	 */
	private static int partition(int[] datas, int start, int end) {
		// 虚拟排序过程：
		// 18 32 37 38 22  4 24 21 34 17
		// 17 32 37 38 18  4 24 21 34 22
		int mid=(start+end)/2;
		sortFirstMiddleLast(datas,start,mid,end);
		//放置中点元素到数组结束位置-1，因为最后一个数肯定比它大。
		int index=end-1;
		Common.swap(datas, mid, end-1);
		int middata=datas[index]; //支点的数据
		// 17 32 37 38 34  4 24 21 18 22
		//需要比较的数组范围
		int left=start+1; //第一个肯定比支点元素小，不用在比较
		int right=end-2; //最后两个是不用比较的
		//                                s e
		// 17 32 37 38 34  4 24 21 18 22  1 7 
		// 17  4 37 38 34 32 24 21 18 22  2 4
		// 17  4 18 38 34 32 24 21 37 22  2 2
		while(true){
			while(datas[left]<middata){ //查找第一个比支点的数据大的数据
				left++;
			}
			while(datas[right]>middata){ //查找第一个比支点的数据小的数据
				right--;
			}
			if(left<right){ //如果找到相应的数据就交换位置
				Common.swap(datas, left, right);
				left++;
				right--;
			}
			else{ //否则就表示找到了中点
				break;
			}
		}
		//放置中点元素到正确的位置
		Common.swap(datas, index, left);
		index=left;
		return index;
	}
	
	/**
	 * 排序3个指定位置的数组元素
	 * 
	 * @param datas
	 *            要排序的数组
	 * @param start
	 *            起点
	 * @param mid
	 *            中点
	 * @param end
	 *            终点
	 */
	private static void sortFirstMiddleLast(int[] datas, int start,int mid, int end){
		if(datas[start]>datas[mid]){
			Common.swap(datas, start, mid);
		}
		if(datas[mid]>datas[end]){
			Common.swap(datas, mid, end);
		}
		if(datas[start]>datas[mid]){
			Common.swap(datas, start, mid);
		}
	}

	/**
	 * java自带排序演示
	 */
	public static void javaSort() {
		SimpleDateFormat sdf = new SimpleDateFormat("HH:mm:ss,SSS");
		int[] datas = Common.getRandomData(200000);
		System.out.println(sdf.format(new Date()) + "-排序前：");
		Common.showArray(datas, 10);
		java.util.Arrays.sort(datas);
		System.out.println(sdf.format(new Date()) + "-排序后：");
		System.out.printf("是否正确排序：%b%n", Common.checkSort(datas));
		Common.showArray(datas, 10);
	}

	public static void main(String[] args) {
		System.out.println("java自带排序");
		javaSort();
		System.out.println("+++++++++++++++++++++++++++++++++++");
		SimpleDateFormat sdf = new SimpleDateFormat("HH:mm:ss,SSS");
		int[] datas = Common.getRandomData(20);
		System.out.println(sdf.format(new Date()) + "-排序前：");
		Common.showArray(datas, 10);
		Sort.selectionSort(datas);
		System.out.println(sdf.format(new Date()) + "-排序后：");
		System.out.printf("是否正确排序：%b%n", Common.checkSort(datas));
		Common.showArray(datas, 10);
		System.out.println("+++++++++++++++++++++++++++++++++++");
		datas = Common.getRandomData(200000);
		System.out.println(sdf.format(new Date()) + "-排序前：");
		System.out.printf("是否正确排序：%b%n", Common.checkSort(datas));
		Common.showArray(datas, 10);
		Sort.quickSort(datas);
		System.out.println(sdf.format(new Date()) + "-排序后：");
		System.out.printf("是否正确排序：%b%n", Common.checkSort(datas));
		Common.showArray(datas, 10);
	}
}