常见算法可以分为两大类：
非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
1、冒泡排序
思路：外层循环从1到n-1，内循环从当前外层的元素的下一个位置开始，依次和外层的元素比较，出现逆序就交换，通过与相邻元素的比较和交换来把小的数交换到最前面。
//定义一个数组
int[] arr = new int[]{3, 1, 2, 9, 8, 6, 7, 4, 45, 69, 18, 66, 16};
//冒泡排序
for (int j = 0; j < arr.length - 1; j++) {
for (int i = 0; i < arr.length - 1 - j; i++) { //-j的意思是每次排完一次都确定了最后一个，所以最后的就不用在比了
if (arr[i] > arr[i + 1]) { //如果第一位大于第二位
int t = arr[i]; //定义一个变量，将第一位的值给这个变量，那么现在第一位也就空了
arr[i] = arr[i + 1]; //将第二位的值放到第一位，此时，第二位也就空了
arr[i + 1] = t; //此时再将临时变量里面的值放到第二位
}
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}2、选择排序
思路：冒泡排序是通过相邻的比较和交换，每次找个最小值。选择排序是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
//定义一个数组
int[] arr = {49, 38, 65, 97, 76, 13, 27, 50};
//选择排序
for (int i = 0; i < arr.length-1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}3、插入排序
思路：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。可以理解为玩扑克牌时的理牌；
private static void sort(int[] array) {
int n = array.length;
/**
*从第二位数字开始，每一个数字都试图跟它的前一个比较并交换，并重复；直到前一个数字不存在或者比它小或相等时停下来
**/
for (int i = 1; i < n; i++) {//从第二个数开始
int key = array[i];
int j = i -1;
while (j >= 0 && array[j]>key) {
array[j + 1] = array[j]; //交换
j--; //下标向前移动
}
array[j+1] = key;
}
}
