排序分多种，插入排序类有直接插入排序，希尔排序；选择排序类有简单选择排序，堆排序；交换排序类有冒泡排序，快速排序。
各排序时间复杂度对比：
1.冒泡排序:每轮两两交换排出一个最大或最小值
实现思路：
1.对相邻的数两两比较其大小，前面大于后面的数，就将这两个数据进行交换。一次往后进行比较，一轮结束将最大值放在末尾。
2.对剩下的数继续按照该方法比较，直到所有数排完。
动态演示图：（说再多不如一张动图讲得清楚）
实现代码：
/**
* 冒泡排序
*/
public static void bubbleSort(int[] array) {
//定义排序的次数，每次找出最大的一个，总共要找array.length次
//当前排好序的个数为i
for (int i = 0; i < array.length; i++) {
//将剩余的未排序的array.length-i个数循环进行排序，比较次数为(array.length-i-1)
for (int j = 0; j < array.length - i - 1; j++) {
//如果左边的书比右边的大，相互交换值
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
2.插入排序：从第二个数起，将每个插入到前面有序数组中
实现思路：
1.将前两个数进行比较大小排序。
2.将第三个数与之前的有序数组进行比较，一次与前一个数比较大小，直到插入到合适的位置，后面的数依次往后移一位。
3.不断重复上述过程，直到把最后一个数插完。
动态演示图:
代码实现：
/**
* 插入排序
*/
public static void insertSort(int arr[]) {
for (int i = 1; i < arr.length; i++) { //除了第一个，后面都要插入排一次
if (arr[i] < arr[i - 1]) { //如果后一个比前一个小，需要挪动位置，否则不挪
int temp = arr[i]; //temp为当前待插入元素
int j;
//判断应该插入到哪个位置
for (j = i - 1; j >= 0 && temp < arr[j]; j--) { //循环判断大小，看是否该往后挪动
arr[j + 1] = arr[j]; //需要换位置的数往后移
}
arr[j + 1] = temp; //把当前数插入最终挪出来的空位
}
}
}
3.选择排序：每次选其中最小的与第i个位置交换
实现思路：
1.从该数组中两两比较一轮，选出一个最小数与第一个位置交换。
2.然后从剩下的leng-1个数中选出最小的数，该轮选完就与第二个位置数交换。
3.重复上述步骤，直到最后两个数交换完成。
动态演示图
代码实现：
/**
* 选择排序
*/
public static void selectSort(int[] array) {
//i表示当前选择到的位置
for (int i = 0; i < array.length; i++) {
int minPos = i; //假设当前一轮选择，最小的数为第一个，即位置i
for (int j = i ; j < array.length; j++) {
if (array[j] < array[minPos]) { //循环判断与当前最小数进行比较，如有更小的则重新记录最小值位置
minPos = j;
}
}
//将最小数与当前轮第一个数交换
int temp = array[i];
array[i] = array[minPos];
array[minPos] = temp;
}
}
4.快速排序：每一轮找到中间值，对左右两边子列表递归调用该快速排序。
实现思路：
1.选择一个基准元素,通常选择第一个元素。
2.通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值都小，另一部分记录的元素值比基准值都大。
3.此时基准元素在其排好序后的正确位置
4.然后分别对这两部分记录用同样的方法继续进行排序，每一轮递归调用排序方法，直到整个序列有序。
动态演示图：
过程如下：
int[] array = {1,3,42,0,4,6};
/**
* 给给定范围，返回轴点元素的位置，
*轴点元素左边都比轴点元素小，右边都比轴点元素大
* 最终begin与end位置会重叠，即为最终轴点位置
* while(begin < end)循环，缺一不可
* @return
*/
private int pivotIndex(int begin, int end) {
//备份begin位置的元素
int pivot = array[begin];
//end指向最后一个元素
end--;
while(begin < end) {
//能循环移动的条件
while(begin < end) {
//在条件内都能进入
if (array[end] > pivot) { //右边元素大于轴点元素，只需end前移
end--;
} else {
//一旦执行到这里，则交换完成，从end转为begin比较，所以break
array[begin] = array[end];
begin++;
break;
}
}
while(begin < end) {
if (pivot > array[begin]) { //左边元素小于轴点，只需begin右移
begin++;
} else {
//一旦执行到这里，则交换完成，从begin转为end比较，所以break
array[end] = array[begin];
end--;
break;
}
}
}
//将轴点元素值放入最终位置，即begin或end位置
array[begin] = pivot;
//否则，begin会等于end，直接返回该位置
return begin;
}
public void quickSort(int begin, int end) {
if (end-begin<2) return;
int mid = pivotIndex(begin, end); //轴点位置已经移动到正确位置
//对轴点左边范围进行快排，对轴点右边范围进行快排
quickSort(begin, mid);
quickSort(mid+1, end);
}
先写到这儿，接下来会相继加入希尔排序，堆排序等。
