四种基本排序算法（java表示）

工具类：

/**
 * 获取数据
 * 
 * @timestamp Mar 11, 2016 12:27:20 PM
 * @author smallbug
 */
public class DataUtil {

	public static final String ASC = "asc";
	public static final String DESC = "desc";

	/**
	 * 获取数据
	 * 
	 * @timestamp Mar 11, 2016 1:17:10 PM
	 * @param sum
	 * @return
	 */
	public static int[] getData(int sum) {
		int[] ii = new int[sum];
		Random r = new Random();
		for (int i = 0; i < sum; i++) {
			ii[i] = r.nextInt(sum);
		}
		return ii;
	}

	/**
	 * 交换数据
	 * 
	 * @timestamp Mar 11, 2016 1:17:17 PM
	 * @param data
	 * @param i
	 * @param j
	 */
	public static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	/**
	 * 验证排序是否成功
	 * 
	 * @timestamp Mar 11, 2016 1:38:09 PM
	 * @param data
	 * @param orderBy
	 * @return
	 */
	public static boolean verify(int[] data, String orderBy) {
		boolean flag = true;

		if (ASC.equalsIgnoreCase(orderBy)) {
			for (int i = 0; i < data.length - 1; i++) {
				if (data[i] > data[i + 1])
					flag = false;
			}
		} else if (DESC.equalsIgnoreCase(orderBy)) {
			for (int i = 0; i < data.length - 1; i++) {
				if (data[i] < data[i + 1])
					flag = false;
			}
		} else {
			throw new RuntimeException("order error!");
		}
		return flag;
	}

}

?冒泡：

/**
 * 冒泡排序
 * <ul>
 * <li>平均情况：O(N^2)</li>
 * <li>最好情况：O(N)</li>
 * <li>最坏情况：O(N^2)</li>
 * <li>辅助存储：O(1)</li>
 * <li>稳定</li>
 * <ul>
 * 
 * @timestamp Mar 11, 2016 1:08:08 PM
 * @author smallbug
 */
public class BubbleSort {

	public static void main(String[] args) {

		int[] data = DataUtil.getData(1000);
		System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		sort(data);
		System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功：" + (DataUtil.verify(data, DataUtil.DESC) ? "是" : "否"));
	}

	/**
	 * 每一次的外层循环都是将一个最小的数字推到了次小或相等数字的下面<br />
	 * 内层循环是为了将小数字往上推
	 * 
	 * @timestamp Mar 11, 2016 1:05:21 PM
	 * @param data
	 */
	private static void sort(int[] data) {
		boolean flag = true;
		for (int i = 1; i < data.length; i++) {
			for (int j = 0; j < data.length - i; j++) {
				if (data[j + 1] > data[j]) {
					flag = false;
					DataUtil.swap(data, j + 1, j);
				}
			}
			if (flag)
				return;
		}
	}
}

?选择：

package cn.smallbug.structure.sort;

import java.util.Arrays;

/**
 * 选择排序
 * <ul>
 * <li>平均情况：O(N^2)</li>
 * <li>最好情况：O(N^2)</li>
 * <li>最坏情况：O(N^2)</li>
 * <li>辅助存储：O(1)</li>
 * <li>不稳定</li>
 * <ul>
 * 
 * @timestamp Mar 11, 2016 12:52:57 PM
 * @author smallbug
 */
public class SelectSort {

	public static void main(String[] args) {
		int[] data = DataUtil.getData(1000);
		System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		selectSort(data);
		System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功：" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否"));
	}

	public static void selectSort(int[] data) {
		int index = 0;
		for (int i = 0; i < data.length; i++) {
			index = i;// 要比较的索引
			for (int j = i; j < data.length; j++) {// 与剩下的数字依次比较，取最小数的索引位置
				if (data[index] > data[j]) {
					index = j;
				}
			}
			if (index != i) {// 交换
				DataUtil.swap(data, index, i);
			}
		}
	}

}

?插入：

/**
 * 插入排序
 * <ul>
 * <li>平均情况：O(N^2)</li>
 * <li>最好情况：O(N)</li>
 * <li>最坏情况：O(N^2)</li>
 * <li>辅助存储：O(1)</li>
 * <li>稳定</li>
 * <ul>
 * 
 * @timestamp Mar 11, 2016 1:25:05 PM
 * @author smallbug
 */
public class InsertSort {

	public static void main(String[] args) {
		int[] data = DataUtil.getData(1000);
		System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		insertSort(data);
		System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功：" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否"));
	}

	private static void insertSort(int[] data) {
		int temp;
		for (int i = 1; i < data.length; i++) {
			temp = data[i];// 保存待插入的数值
			int j = i;
			for (; j > 0 && temp < data[j - 1]; j--) {
				data[j] = data[j - 1];// 如果待插入的数值前面的元素比该值大，就向后移动一位
			}
			data[j] = temp;// 插入
		}
	}
}

?Shell：

/**
 * Shell排序<br />
 * <ul>
 * <li>平均情况：O(N^1.5)</li>
 * <li>最好情况：O(N)</li>
 * <li>最坏情况：O(N^2)</li>
 * <li>辅助存储：O(1)</li>
 * <li>不稳定</li>
 * <ul>
 * 
 * @timestamp Mar 11, 2016 2:01:32 PM
 * @author smallbug
 */
public class ShellSort {

	public static void main(String[] args) {
		int[] data = DataUtil.getData(1000);
		System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		shellSort(data);
		System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功：" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否"));
	}

	private static void shellSort(int[] data) {
		int k = 1;// 增量
		for (;;) {
			k = k << 1;
			if (k > data.length) {
				k >>= 1;
				break;
			}
		} // 这里取的增量是2^n-1,即长度为1000算出的k是512，它是最大的小于1000且为2的倍数的数
		for (; k > 1; k >>>= 1) {
			int temp;
			for (int i = k - 1; i < data.length; i++) {
				temp = data[i];// 保存待插入的数值
				int j = i;
				for (; j > k - 2 && temp < data[j - k + 1]; j = j - k + 1) {// j-k+1=j-(k-1)=k-增量
					data[j] = data[j - k + 1];// 如果待插入的数值前面的元素比该值大，就向后移动k-1位
				}
				data[j] = temp;// 插入
			}
		}

	}
}

?

四种基本排序算法（java表示）

原文：http://smallbug-vip.iteye.com/blog/2282209