常考为比较类七种
冒泡 1选择 1插入 1希尔 1归并 1快排 1堆排 1计数排序 2桶排序 2基数排序 2代码
for(int i = 0; i < n-1; i++){ for(int j = 0; j <n-1; j++){ if(arr[j] > arr[j+1]){ int temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = arr [j+1]; } } }不停地交换，其实有很多废的步骤，但不需要去管
代码
for(int i = 0; i < n-1; i++){ int minIndex = i; for(int j = i+1; j < n; j++){ if(arr[j] < arr[minIndex]){ minIndex = j; } } int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; }不停从前往后去找最小或者最大
代码
for(int i = 1; i < n; i++){ int preIndex = i - 1; int current = arr[i]; while (preIndex >= 0 && arr[preIndex] > current){ arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex+1] = current; }这个循环比较巧妙，将后面不断和前面比较，同时指针变化，最后恢复
第一个突破O(n2),插入版的改进 代码
for(int k = n/2; k >0; k /=2){//希尔增量 for(int i = k; i < n; i++){ for(int j = i; j >= k && arr[j] < arr[j-k]; j -= k){//这个循环比较特殊，两两比较，相当于插值永远要不大于右边要不小于左边，以此保证序列有序 int temp = arr[j-k]; arr[j-k] = arr[j]; arr[j] = temp; } } }有点先排好一个大间隔数列然后插小间隔数列，保证增量数列永远有序
nlogn 分治思想
public static void main(String[] args) { int [] arr = new int[n]; int [] temp = new int[n]; mergeSorts(arr,0,n-1,temp); } public static void merge(int[] arr,int low, int mid, int high, int [] temp){ int i =0; int j =low , k = mid + 1; while (j <= mid && k <=high){//左边序列和右边序列起始索引，在已有排好的基础上，进行交叉对比 if (arr[k] < arr[j] ){ temp[i++] = arr[k++]; }else{ temp[i++] = arr[j++]; } } while (j <= mid){//左边遗漏，其实if也行，应该就一个取不到 temp[i++] = arr[j++]; } while (k <= high){//右边遗漏 temp[i++] = arr[k++]; } for(int t =0; t<i; t++){ arr[low+t] = temp[t]; } } public static void mergeSorts(int[] arr,int low, int high, int [] temp){ if(low < high) { int mid = (low + high) / 2; mergeSorts(arr, low, mid, temp); mergeSorts(arr, mid + 1, high, temp); merge(arr, low, mid, high, temp); } }分治 nlogn 所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面 代码：
public static void quickSorts(int[] arr, int low, int high){ if(low >= high) return;//这个等号可有可无，没有也不执行 int temp = arr[low]; int i = low; int j = high; while (i < j){ while (arr[j] >= temp && i < j){//一定是右边先动,判断的等号也不能少,想想为什么 j--; } while (arr[i] <= temp && i < j){ i++; } if(i < j){ int tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; } } arr[low] = arr[i]; arr[i] = temp; quickSorts(arr,low,j-1); quickSorts(arr,j+1,high); }快排有些小细节就有意思了 等号必须交换，要不然就不往下走了 右边之后想
二叉树 nlogn 代码：
public static void heapSort(int[] arr,int n){ //创建堆 for(int i = (n-1)/2; i >= 0; i--){ //第一个非叶子结点从下至上,从右至左 adjustHeap(arr,i,arr.length); } //调整结构+交换堆顶元素与末尾元素 for(int i = n - 1; i > 0; i--){ int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; //重新堆调整 adjustHeap(arr,0,i); } } public static void adjustHeap(int[] arr, int parent, int length){ //将temp作为父节点 int temp = arr[parent]; //左孩子 int lChlid = 2*parent + 1; while (lChlid < length){ //右孩子 int rChlid = lChlid + 1; //如果右孩子有结点,并且右孩子结点的值大于左孩子结点,选右孩子 if(rChlid < length && arr[lChlid] < arr[rChlid]){ lChlid++; } //父节点值大于孩子结点值,直接结束 if(temp >= arr[lChlid]){ break; } //把孩子结点值赋给父节点 arr[parent] = arr[lChlid]; //选孩子结点的左孩子结点,继续向下筛选 parent = lChlid; lChlid = 2*lChlid + 1; } arr[parent] = temp; }没完全看懂，但基本思路就是先构建大顶堆，大顶堆通过不停比较改变父节点和子节点位置，同时改变时一定要递归改变其他子节点，构建完成大顶堆然后把最上面的脱堆，然后调整堆，因为上面永远最大
