第二章排序 2.1 O(n2) 算法
给定一数组，其大小为8个元素，数组内的数据无序。
冒泡排序：两两比较，将两者较少的升上去，第一次比较空间为0-(N-1)直到最后一轮比较空间为0-1
public class bubbleSort { public static void main(String[] args) { int[] test = { 6, 3, 5, 7, 0, 4, 1, 2 }; for (int i = 0; i < test.length - 1; i++) { for (int j = 0; j < test.length - i - 1; j++) { if (test[j] > test[j + 1]) { int temp = test[j]; test[j] = test[j + 1]; test[j + 1] = temp; } } } for (int k = 0; k < test.length; k++) { System.out.println(test[k]); } } }选择排序：在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换……第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。
public class selectSort { public static void main(String[] args) { int[] test = { 6, 3, 5, 7, 0, 4, 1, 2 }; for (int i = 0; i < test.length; i++) { int min = i; for (int j = i + 1; j < test.length; j++) { if (test[min] > test[j]) { min = j; } } if (min != i) { int temp = test[i]; test[i] = test[min]; test[min] = temp; } } for (int k = 0; k < test.length; k++) { System.out.println(test[k]); } } }插入排序：对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。
public class insertSort { public static void main(String[] args) { int[] test = { 6, 3, 5, 7, 0, 4, 1, 2 }; for (int i = 0; i < test.length; i++) { for (int j = i; j > 0; j--) { if (test[j] < test[j - 1]) { int temp = test[j]; test[j] = test[j - 1]; test[j - 1] = temp; } else { break; } } } for (int k = 0; k < test.length; k++) { System.out.println(test[k]); } } } 2.2 O(nlogN) 算法归并排序:将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列（分治法），每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
快速排序：任取一个分界值，大于划分值放在右边，小于划分值放在左边，然后分别递归处理划分值的左右两边。实现方法：将划分值放在数组最后的位置，然后初始化一个长度为0的小于等于空间放在最左边，接着从左到右遍历所有元素，如果当前元素大于划分值，继续遍历下一个元素，如果当前元素小于等于划分值，将当前数和小于等于空间的下一个数交换位置，小于等于空间向右扩一个位置，遍历完所有元素，直到最后一个数，将划分值与小于等于空间下一个元素交换。（一次完整划分过程）
堆排序：堆是一种重要的数据结构，为一棵完全二叉树,底层如果用数组存储数据的话，假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树，那么左子树的位置是2i+1，如果有右子树，右子树的位置是2i+2，如果有父节点，父节点的位置是(n-1)/2取整。分为最大堆和最小堆，最大堆的任意子树根节点不小于任意子结点，最小堆的根节点不大于任意子结点。所谓堆排序就是利用堆这种数据结构来对数组排序，我们使用的是最大堆。堆排序的大概步骤如下:(1)构建最大堆；(2)选择顶，并与第0位置元素交换；(3)由于步骤2的的交换可能破环了最大堆的性质，第0不再是最大元素，需要调用maxHeap调整堆(沉降法)，如果需要重复步骤2。