一.直接插入排序
思想：将一个个未排序的数字插入到已经排好顺序的数组中。
例如：
思路：先将前两个数字排序，然后将后面数字与前面数字比较排序。
操作：
1.引入变量 i 遍历数组[1，array.lenth]
2.用临时变量tmp记录[i]的值，用于后续比较。
3.与前面数字比较，用 j 遍历[0，i-1]
4.判断[j]与tmp大小，若[j]>tmp则令[j]前移
5.将tmp放在[j+1]
代码：
public static void insertSort(int[] array) {//遍历整个数组for (int i = 1; i < array.length; i++) {//使0-i有序int j = i-1;int tmp = array[i];for (; j >= 0; j--) {if(tmp < array[j]) {array[j+1] = array[j];}else {//因为前面已经有序，大于之后直接跳出循环break;}}array[j+1] = tmp;}}时间复杂度：O（n*n）
空间复杂度：O（1）
稳定性：稳定
适用范围：数组越有序，排序越快。
二.希尔排序
思想：将数组分为n组，分别对每组进行排序，然后重复进行分组，排序，最后将数组分成一组进行排序。
操作：
1.i遍历[gap,array.length-1]
2.记录[i]->tmp
3.j遍历[0,gap-1] ([i-gap,array.length-1-gap])
4.判断[j]与tmp大小，若[j]>tmp则令[j]前移
5.将tmp放在[j+1]
有没有一点眼熟，对，希尔排序就是对插入排序的优化先让它变成大致有序的数组，在进行插入排序。
时间复杂度：希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
从书中得知大致范围在O（n^1.25）~O（1.6*n^1.25）
空间复杂度：O（1）
稳定性：不稳定
//希尔排序public static void shellSort(int[] array) {int gap = array.length;while(gap != 0) {gap /= 2;shell(array,gap);}}public static void shell(int[] array,int gap) {//遍历整个数组for (int i = gap; i < array.length; i++) {//使0-i有序int j = i-gap;int tmp = array[i];for (; j >= 0; j-=gap) {if(tmp < array[j]) {array[j+gap] = array[j];}else {//因为前面已经有序，大于之后直接跳出循环break;}}array[j+gap] = tmp;}
}
三.选择排序
思想：将最小的元素找到放在左边，然后遍历数组重复这个操作。
操作：
1. i 遍历数组
2.记录minIndex最小值的下标，第一次记录为i
3.遍历i之后的元素，每找到比minIndx小的元素就替换minIndex，最终找到最小值
4.交换minIndex与 i 下标元素
public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;//找到i之后的 最小的 小于array[i]的元素for (int j = i; j < array.length; j++) {if(array[j] < array[minIndex]) {minIndex = j;}}//将最小的元素换到i下标处swap(array,i,minIndex);}}public static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
选择排序2.0
传统的选择排序使用了一个minIndex，现在介绍使用两个数，minIndex，maxIndex
分别同时寻找最左边与最右边 。
操作：
1.定义left，right用于放置最大值与最小值
2.在left<right时循环，找到所有minIndex，maxIndex
3.定义minIndex，maxIndex，统一定义在left处
4.循环[left+1,right]的元素，并找到minIndex，maxIndex更改下标
5.找到之后swap，注意maxIndex == left 这个特殊情况即可。
public static void selectSort2(int[] array) {int left = 0;int right = array.length-1;while(left < right) {//两个都初始化在最左边，防止漏掉左边int minIndex = left;int maxIndex = left;//找到中间的最大值与最小值for (int i = left+1; i < right; i++) {if(array[i] < array[minIndex]) {minIndex = i;}if(array[i] > array[maxIndex]) {maxIndex = i;}}swap(array,left,minIndex);//为了防止最大值在left处，然后被交换到minIndex处if(maxIndex == left) {maxIndex = minIndex;}swap(array,right,maxIndex);left++;right--;}}四.堆排序
思路：建立一个大根堆，转化为小根堆。
1.完成向下排序代码：
1.1找两个孩子节点的最大值（注意只有右节点的情况）
1.2与父亲节点交换
1.3令父亲节点上移，并找其孩子节点重复上述过程
2.创建大根堆：从最后一个父亲节点循环到根节点
3.将根节点与最后一个节点互换，然后继续向下排序重复互换操作。
//排升序要建大堆，排降序建小堆public static void heapSort(int[] array) {createHeap(array);//换成降序int end = array.length-1;while(end > 0) {swap(array,0,end);//找到最大值放在最后，最终形成降序siftDown(array,0,end);end--;}}//创建大根堆（从下面到上面排序，保证下面先形成 大根堆）public static void createHeap(int[] array) {for(int parent = (array.length-1-1)/2; parent >= 0; parent--) {siftDown(array,parent,array.length);}}//向下排序public static void siftDown(int[] array,int parent,int len) {//孩子节点int child = 2*parent + 1;//将该父亲节点对应的孩子节点 及 孩子的孩子节点 排序while(child < len) {//寻找左右孩子节点Maxif(child + 1 < len && array[child] < array[child+1]) {child++;}if(array[child] > array[parent]) {//上大下小，大根堆swap(array,child,parent);//继续向下排序parent = child;child = 2*parent+1;}else {//下面已经排好了，不满足直接返回break;}}}时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
