冒泡排序
1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
3．N=N-1，如果N不为0就重复前面二步，否则排序完成。
时间复杂度
图示：
冒泡1
public class BubbleSort { public static void sort(int[] arr){ for(int i =0;i<arr.length;i++){ for(int j =1;j<arr.length-i;j++){ if(arr[j]<arr[j-1]){ int temp = arr[j]; arr[j]=arr[j-1]; arr[j-1]=temp; } } } } public static void main(String[] args) { int[] arr = {4,2,1,7,5}; sort(arr); for(int i =0;i<arr.length;i++){ System.out.print(arr[i]+" "); } } }
下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
//冒泡排序2
void BubbleSort2(int a[], int n) { int j, k; bool flag; k = n; flag = true; while (flag) { flag = false; for (j = 1; j < k; j++) if (a[j - 1] > a[j]) { Swap(a[j - 1], a[j]); flag = true; } k--; } }
再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，
最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。
//冒泡排序3
void BubbleSort3(int a[], int n){ int j, k; int flag; flag = n; while (flag > 0){ k = flag; flag = 0; for (j = 1; j < k; j++){ if (a[j - 1] > a[j]){ Swap(a[j - 1], a[j]); flag = j; }
} } }
冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。
参考：http://www.cnblogs.com/morewindows/archive/2011/08/06/2129603.html
直接插入排序
直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
设数组为a[0…n-1]。
1. 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
2. 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
3. i++并重复第二步直到i==n-1。排序完成。
代码
public class InsertSort { public static void sort(int[] arr) { for (int i = 0; i < arr.length-1; i++) { for (int j = i + 1; j >= 1 && arr[j] < arr[j - 1]; j--) { int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } } public static void main(String[] args) { int[] arr ={4,3,7,1,5}; sort(arr); for(int i =0;i<arr.length;i++){ System.out.print(arr[i]+" "); } } }
原文：http://www.cnblogs.com/pingh/p/3536968.html