1.时间性能

2. 辅助空间

3. 算法的复杂性

1.3冒泡排序

public class BubbleSort {
	public static void main(String[] args) {
		int[] array = { 3, 9, 1, 4, 8, 6, 7, 5, 2, 0 };

		System.out.println(Arrays.toString(bubbleSort0(array)));
	}

	/** 冒泡排序初级版 */
	static int[] bubbleSort0(int[] a) {
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = i + 1; j < a.length; j++) {
				if (a[i] > a[j]) {
					swap(a, i, j);
				}
			}
		}
		return a;
	}

	/** 交换a数组中的下标为 i 和 j 的值 */
	static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

/** 对数组a进行排序 */
static int[] bubbleSort1(int[] a) {
	for (int i = 0; i < a.length - 1; i++) {
		for (int j = a.length - 2; j >= i; j--) {// j从后往前循环
			if (a[j] > a[j + 1]) {// 若前一个元素大于后一个元素，则交换
				swap(a, j, j + 1);// 交换a[j]和a[j+2]的值
			}
		}
	}
	return a;
}

/** 改进后对数组a进行排序 */
static int[] bubbleSort2(int[] a) {
	boolean flag = true; //设置一个标记
	for (int i = 0; i < a.length - 1 && flag; i++) {//当flag为false时，有序，退出循环
		flag = false;
		for (int j = a.length - 2; j >= i; j--) {// j从后往前循环
			if (a[j] > a[j + 1]) {// 若前一个元素大于后一个元素，则交换
				swap(a, j, j + 1);// 交换a[j]和a[j+2]的值
				flag = true;//如果有数据交换，则设置为true，继续循环
			}
		}
	}
	return a;
}

冒泡排序复杂度分析

1.4选择排序

/** 简单选择排序 */
static int[] bubbleSort0(int[] a) {
	int min;
	for (int i = 0; i < a.length - 1; i++) {
		min = i;//将当前下标定义为最小值
		for (int j = i + 1; j < a.length; j++) {
			if (a[min] > a[j]) {//如果有小于当前的关键字，将下标赋值给min
				min = j;
			}
			if(min != i){//若min不等于i，则找到最小值，并交换
				swap(a,min,i);
			}
		}
		
	}
	return a;
}

简单选择排序复杂度分析

1.5直接插入排序

/** 插入排序 */
static int[] insertSort(int[] a) {
	int j;// 单独定义，用于记录第二层for循环退出时候的j值
	for (int i = 1; i < a.length; i++) {
		if (a[i] < a[i - 1]) {// 如果后一个值比前一个小，则交换    
			int temp = a[i];// 临时变量，存放循环的条件
			for (j = i - 1; j >= 0 && a[j] > temp; j--) {
				a[j + 1] = a[j];// 将比temp大的值，依次后移
			}
			a[j + 1] = temp;//将跳出循环的后一个记录赋值为temp
		}
	}
	return a;
}

直接插入排序复杂度分析

1.6希尔排序

/** 希尔排序 */
static int[] shelltSort(int[] a) {
	int j;
	int increment = a.length;
	do {
		increment = increment / 3;//增量序列
		for (int i = increment + 1; i < a.length; i++) {
			if (a[i] < a[i - increment]) {
				int temp = a[i];
				for (j = i - increment; j >= 0 && a[j] > temp; j = j - increment) {
					a[j + increment] = a[j];// 记录后移 .查找插入位置
				}
				a[j + increment] = temp;
			}
		}
	} while (increment > 1);
	return a;
}

1.7堆排序

/** 堆排序 */
static int[] heapSort(int[] a) {
	int[] temp = null;// 定义一个临时数组用于接收调整过的大顶堆
	for (int i = a.length / 2; i >= 0; i--) {
		temp = heapAdjust(a, i, a.length);// 调整大顶堆
	}

	for (int i = a.length; i >= 0; i--) {
		swap(temp, 0, i - 1);// 将调整好的大顶堆的首尾互换
		temp = heapAdjust(a, 0, i - 1);// 调整交换完成后的剩余元素为大顶堆
	}
	return a;
}

/** 将数组a调整为一个大顶堆 */
static int[] heapAdjust(int[] a, int i, int len) {
	int j, temp;
	temp = a[i];// 临时变量用于
	for (j = 2 * i; j < len && len != 1; j = 2 * j) {// len!=1为了避免陷入死循环，即剩余一个元素不用调整大顶堆
		if (j < len - 1 && a[j] < a[j + 1]) {// 如果左孩子小于有孩子，则j++,a[j]指向右孩子
			j++;
		}

		if (temp >= a[j])// 如果结点a[i]值均大于左右孩子结点，则不交换，跳出循环
			break;
		a[i] = a[j];// 否则 交换 两者位置
		i = j;
	}
	a[i] = temp;
	return a;
}

/** 交换a数组中的下标为 i 和 j 的值 */
static void swap(int[] a, int i, int j) {
	if (j >= 0 && i >= 0) {// 当 i,j大于等于0时执行交换
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

1.8归并排序

public static int[] data = http://www.mamicode.com/{ 50, 10, 90, 30, 70, 40, 80, 60, 20 };>
归并排序复杂度分析 
时间复杂度对长度为n的数据需要进行log2n次二路归并，每次归并的时间为O（N）。故时间复杂度无论是在最好的情况下还是最坏的情况下都是nlog2(N)。

归并排序是一种比较占用内存，但却效率高且稳定的算法。
1.9快速排序
快速排序 (Quick Sort) 的基本思想是:通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
public static void main(String[] args) {
	// TODO Auto-generated method stub
	int[] data = http://www.mamicode.com/{ 50, 10, 90, 30, 70, 40, 80, 60, 20 };>
快速排序复杂度
我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。如图 9-9-7所示 ， 它是{50，10，90，30，70，40，80，60，20}在快速排序过程中的递归过程 。 由于我们的第一个关键字是 50 ，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。

快速排序优化

总结