[数据结构与算法]排序算法代码：冒泡排序、插入排序、选择排序、快速排序

public class MyClass {

	public static void main(String[] args) {
		int[] array = {100, 3, 58, 11, 88, 2, 5, 3, 22};
		maxMin(array);
		//bubble(array);
		//bubble2(array);
		//selectSort(array);
		//quickSort(0,8,array);
		insertSort(array);
	}

	/**
	 * 插入排序
	 */
	private static void insertSort(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}
		int length = array.length;
		for (int i = 1; i < length; i++) {
			int temp = array[i];
			int j = i;
			while (j > 0 && array[j - 1] > temp) {
				array[j] = array[j - 1];
				j--;
			}
			array[j] = temp;//找到合适的位置插入!
		}

		print("插入排序", array);
	}

    /**
	 * 快速排序
	 */
	private static void quickSort(int left, int right, int[] array) {
		if (array == null || array.length == 0 || left > right) {
			print("快速排序2", array);
			return;
		}

		int i, j, temp, base;
		i = left;
		j = right;
		base = array[left];
		while (i != j) {
			//先从右边循环查找，直到找到一个比哨兵元素值小的元素
			while (array[j] >= base && i < j) {
				j--;
			}

			//再从左边循环查找，知道找到一个比哨兵元素值大的元素
			while (array[i] <= base && i < j) {
				i++;
			}

			//将前面找到的两个元素交换
			if (i < j) {
				temp = array[j];
				array[j] = array[i];
				array[i] = temp;
			}
		}
		array[left] = array[i];
		array[i] = base;

		quickSort(left, i - 1, array);
		quickSort(i + 1, right, array);
	}

	/**
	 * 快速排序，此实现方法在Java中不可用
	 */
	private static void quickSort2(int array[], int length) {
		if (array == null || length < 1) {
			print("快速排序", array);
			return;
		}

		int start = 0;
		int end = length - 1;
		int sentry = array[start];
		while (start < end) {
			while (start < end) {
				if (array[end--] < sentry) {
					array[start++] = array[++end];
					break;
				}
			}
			while (start < end) {
				if (array[start++] > sentry) {
					array[end--] = array[--start];
					break;
				}
			}
		}
		array[start] = sentry;

		quickSort2(array, start);
		quickSort2(array + start + 1, length - start - 1);
		// C语言可以指定数组的起始位置坐标，但Java不行
	}


	/**
	 * 选择排序
	 * 利用sorted变量，可以控制最优时间复杂度达到O(n)
	 */
	private static void selectSort(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}

		boolean sorted = false;
		int length = array.length;
		int temp;
		for (int i = length - 1; !sorted && i > 0; i--) {
			sorted = true;
			int max = 0;
			for (int j = 1; j <= i; j++) {
				if (array[j] > array[max]) {
					max = j;
				} else {
					sorted = false;
				}
			}
			if (max != i) {
				temp = array[i];
				array[i] = array[max];
				array[max] = temp;
			}
		}

		print("选择排序", array);
	}

	/**
	 * 选择排序，不稳定
	 * 例如序列 5 8 5 2 66，经第一遍选择，2与第一个5交换，这样两个5的先后顺序就变了，故不稳定
	 */
	private static void selectSort3(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}
		int length = array.length;
		int temp;
		for (int i = 0; i < length; i++) {
			int min = array[i];
			for (int j = i; j < length; j++) {
				if (array[j] < min) {
					temp = array[j];
					array[j] = min;
					min = temp;
				}
			}
			array[i] = min;
		}

		print("选择排序3", array);
	}

	/**
	 * 选择排序
	 */
	private static void selectSort2(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}

		int length = array.length;
		int tempIndex = 0;
		int temp;
		for (int i = 0; i < length; i++) {
			temp = array[i];
			tempIndex = i;
			for (int j = i + 1; j < length; j++) {
				if (array[j] < temp) {
					temp = array[j];
					tempIndex = j;
				}
			}
			array[tempIndex] = array[i];
			array[i] = temp;
		}

		print("选择排序2", array);
	}

    /**
	 * 冒泡排序
	 */
	public static void bubble(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}

		boolean flag;//是否交换的标志
		for (int i = 0; i < array.length - 1; i++) {
			// 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换
			flag = false;
			for (int j = 0; j < array.length - 1 - i; j++) {
				if (array[j] > array[j + 1]) {
					int temp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temp;
					flag = true;    //只要有发生了交换，flag就置为true
				}
			}
			// 判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
			if(!flag) break;
		}
	}

	/**
	 * 冒泡排序：从最后面开始，把小的往上“浮”
	 */
	private static void bubble2(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}

		int temp;
		for (int i = 0; i < array.length; i++) {
			for (int j = array.length - 1; j > i; j--) {
				if (array[j] < array[j - 1]) {
					temp = array[j];
					array[j] = array[j - 1];
					array[j - 1] = temp;
				}
			}
		}
		print("冒泡排序", array);
	}

	/**
	 * 冒泡排序：从第一个开始，把后面小的往前换
	 */
	private static void bubble3(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}

		int length = array.length;
		int temp;
		//label:
		for (int i = 0; i < length; i++) {
			for (int j = i + 1; j < length; j++) {
				if (array[i] > array[j]) {
					temp = array[i];
					array[i] = array[j];
					array[j] = temp;
				}
			}
			//if(i==0) break label;
		}
		print("冒泡排序2", array);
	}

	/**
	 * 計算最大值和最小值
	 */
	private static void maxMin(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int j : array) {
			if (min > j) {
				min = j;
			}
			if (max < j) {
				max = j;
			}
			/*int temp = array[i];
			if (i + 1 < array.length && temp > array[i + 1]) {
				array[i] = array[i + 1];
				array[i + 1] = temp;
			}*/
		}
		System.out.println("最大值：" + max);
		System.out.println("最小值：" + min);
	}

	private static void print(String sortName, int[] array) {
		if (array == null || array.length == 0) {
			return;
		}
		System.out.print(sortName + ": ");
		for (int j : array) {
			System.out.print(j + " ");
		}
		System.out.println("");
	}
}