1.冒泡：1.时间复杂度：平均O(n2)，最好O(n)，最坏O(n2) 空间复杂度：O(1) 稳定（没有发生跳跃式的交换：排序前后相同数字的前后顺序没有改变） 每次将最大的数放到后面
public static int[] bubbleSort(int[] arr) { if(arr == null || arr.length <= 1){ return arr; } for(int i=0;i<arr.length-1;i++){ int a=0; for(int j=0;j<arr.length-1-i;j++){//每次循环结束后最后一个元素为当前最大元素 if(arr[j]>arr[j+1]){//将大数往后移 int tmp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=tmp; a++; } } if(a==0){//所有数有序 break; } } return arr; }2.选择：时间复杂度：O(n2)，平均、最好、最坏都是 空间复杂度：O(1) 不稳定 从待排序数字的后面找到比当前待排序数字小的数字进行交换（每次将最小的放到前面）
3.直接插入：时间复杂度：平均O(n2)，最好O(n)，最坏O(n2)，越有序越快 空间复杂度：O(1) 稳定 每次将在前面的比当前数大的放在后面，当前数从1开始，放在tmp，从前面找大的放在当前位置，一直往前，不大则跳出，将tmp放到前面的停止位置。
4.Shell：时间复杂度：平均O(n1.3)，最好O(n)，最坏O(n2) 空间复杂度：0(1) 不稳定 组内进行有序（插入排序），每次除了数组，传入一个gap，作为分组的间隔， 进行多次，直到gap为1，则全部有序
5.快排：时间复杂度：平均0(nlog2n)，最好0(nlog2n)，最坏O(n2) 空间复杂度：0（log2n） 不稳定 每次获得一个基准数，将前面的大数放到它后面，后面的小数放到它前面，直到low和high相遇，得到基准数的位置，再对后面和前面进行重复操作，直到每块都只有一个数，则全部有序。 基准默认选取分区中的第一个数，优化可以在分区中随机选择，或在low、high和中间三个数中取中间大小的数 快排的本质就是把比基准数大的放在基准数的右边，比基准数小的放在基准数的左边，这样就找到了该数据在数组中的正确位置。然后递归的对前半部分和后半部分继续排序。 有序时时间复杂度最坏，每次得到的基准都在最前面或最后面，一次只能得到一个有序数，划分的剩下的区间为n-1
6.归并：时间复杂度：平均0(nlog2n)，最好0(nlog2n)，最坏0(nlog2n) 空间复杂度：0(n) 稳定 使每个子序列有序，再使子序列段间有序 归并应用了分治法的思想，将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。 归并操作的工作原理如下： 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后序列 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾
7.堆排：时间复杂度：平均0(nlog2n)，最好0(nlog2n)，最坏0(nlog2n) 空间复杂度：0(1) 不稳定 建立大根堆，每次将最大的放在后面
分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可以得到原问题的解。 步骤：1.分解；2.求解；3.合并 例如：二分查找、归并排序。
能用动归算法解决的问题，都有两个基本的要素： 1.最优子结构 2.子问题划分有重叠
动态规划解决问题，主要找出两样东西： 1.“状态” dp[i] ：如组成价值i所需要的最少的硬币的数量 2.状态转移方程
public static int maxW(int money,int n,int[] p,int[] w){ int maxw = 0; int[][] dp = new int[n+1][money+1]; for(int i = 1;i<n+1;i++){ for(int j = 1;j<money+1;j++){ if(p[i]>j){ dp[i][j] = dp[i-1][j]; }else { dp[i][j] = Math.max(dp[i-1][j],dp[i][j-p[i]]+w[i]);//此为0-多背包，若为0-1，则后面为dp[i-1][j-p[i]]+w[i] } } } maxw = dp[n][money]; return maxw; }