十大经典排序算法解析
十、常用的10种排序算法
文章目录
十、常用的10种排序算法1、二分查找（非递归）2、分治算法3、动态规划4、KMP算法4.1暴力匹配算法4.2KMP匹配算法
5、贪心算法6.普利姆算法7、克鲁斯卡尔算法8、迪杰斯特拉算法9、弗洛伊德算法10、马踏棋盘算法
1、二分查找（非递归）
概念：二分查找算法只适用于从有序序列中进行查找，比如（数字和字母等），将数列排序后在进行查找。二分查找运行的时间复杂度为O(log2N)
代码实现
public static int binarySearch(int[] arr,int target){
int left=0;
int right=arr.length-1;
while (left<=right){
int mid=(left+right)/2;
if(arr[mid]==target){
return mid;
}else if(arr[mid] left=mid+1; }else if (arr[mid]>target){ right=mid-1; } } return -1; } 2、分治算法 概念：分治算法的字面解释是“分而治之”，就是把一个复杂的问题分解成两个或更多的相同或相似的子问题，在把子问题分解成更小的子问题，直到最小的子问题可以直接求解。如快速排序，归并排序、汉诺塔 算法步骤： 分解：将原问题分解成若干个规模较小，相互独立，与原问题形式相同的子问题 解决：若子问题规模较小，则可以直接求解，否则递归的解各个子问题 合并：将各个子问题合并为原问题的解 代码实现,以汉诺塔为例 public static void hanoitower(int num ,char a,char b,char c){ //只有一个盘 if(num==1){ System.out.println("第1个盘从"+a+"->"+c); }else { //如果n>=2，我们总可以把整体看做两个盘，：最下边的盘A和除下边的所有盘B //1、先把最上面的所有盘A->B,移动过程会使用到C hanoitower(num-1,a,c,b); //2、把最下边的盘A->C System.out.println("第"+num+"个盘从"+a+"->"+c); //把B塔中的所有盘B->C,移动过程中使用到a塔 hanoitower(num-1,b,a,c); } } 3、动态规划 概念：动态规划是一类题目的总称，并不是某个固定的算法，其核心思想和分治算法相似，都是将一个大问题分解成小问题，通过对小问题求解从而得到整体问题的求解。与分治算法不同的是。分治算法分解出的子问题是互不相关的，动态规划分解出的子问题是互相关联的。 动态规划的应用-背包问题 背包问题是指一个给定容量的背包、若干具有一定价值的和重量的物品，如何选择物品放入背包使得包中的物品价值最大。 背包问题又可分为01背包和完全背包（完全背包指的是每种物品都可以有无限键使用），该案例使用的是01背包 图解 物品数量价格吉他11500音响43000电脑32000 物品0磅1磅2磅3磅4磅00000吉他01500150015001500音响01500150015003000电脑015001500200035000 思路分析 算法的主要思想是利用动态规划来解决，每次遍历到第i个物品，根据w[i]和v[i]来确定是否需要将物品放入到背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量,C为背包的容量，v[i] [j] 表示在前i个物品中能够装入容量为j的背包中的最大值。 v[i] [0]=v[0] [j];表示填入的第一行和第一列均为0 当w[i]>j时：v[i] [j]=v[i-1] [j]//当准备加入的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略。 当j>w[i]时，v[i] [j]=max{v[i-1] [j],v[i]+v[i-1] [j-w[i]] }//当准备加入的新增商品的容量小于等于当前背包的容量。 v[i-1] [j]:上个单元格装入的最大值 v[i]:表示当前商品的价值 v[i-1] [j-w[i]]:装入i-1商品，到剩余空间j-w[i]的最大值 代码实现 public class KnapackProblem { public static void main(String[] args){ int[] w={1,4,3};//背包的重量 int[] val={1500,3000,2000};//物品的价值 int m=4;//背包容量 int n=val.length;//物品的个数 //创建二维数组;v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大值 int[][] v=new int[n+1][m+1]; //为了记录放入商品的情况，我们定了一个二维数组path int[][] path=new int[n+1][m+1]; //初始化第一行和第一列，在本程序中，可以不去处理，默认为0 for(int i=0;i v[i][0]=0;//将第一列设置为0 } for (int i=0;i v[0][i]=0;//第一行设置为0 } //根据公式进行动态规划处理 for(int i=1;i for(int j=1;j //公式 if(w[i-1]>j){//因为i是从1开始的，所以需要从i-1开始 v[i][j]=v[i-1][j]; }else { // v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]); //为了得到具体的放置，引入了二维数组path if(v[i-1][j] path[i][j]=1; v[i][j]=val[i-1]+v[i-1][j-w[i-1]]; }else { v[i][j]=v[i-1][j]; } } } } //输出显示 int i=path.length-1;//行的最大值 int j=path[0].length-1;//列的最大值 while (i>0&&j>0){ if(path[i][j]==1){ System.out.printf("第%d个商品放入到背包\n",i); j-=w[i-1]; } i--; } } } 4、KMP算法 kmp算法是暴力匹配算法的优化 4.1暴力匹配算法 假设用字符串str2匹配字符创str1 如果当前字符串匹配成功（即str1[i]==str2[j]），则i++，j++，继续匹配下一个字符如果不匹配，即str1[i]！=str2[j]，令i=i-(j-1),j=0。相当于每次匹配失败时，i回溯，j被置为0采用暴力匹配法会有大量的回溯，每次只移动一位，若不匹配，移动到下一位接着判断，这样的算法浪费大量的时间 代码实现 public static int violenceMatch(String arr1,String arr2){ char[] s1=arr1.toCharArray(); char[] s2=arr2.toCharArray(); int len1=s1.length; int len2=s2.length; int i=0; int j=0; while (i if (s1[i]==s2[j]){ i++; j++; }else {//若果没有匹配成功 i=i-(j-1); j=0; } } //判断是否匹配成功 if(j==len2){ return i-j; }else { return -1; } } 4.2KMP匹配算法 概念：KMP算法利用next数组，next数组中保存了模式串中前后最长的公共子序列的长度。每次回溯时。通过next数组找到找到最大后移位置。 kmp算法的核心是跳转表next的实现 public static int[] kmpNext(String dest){ //创建一个next数组保存部分匹配值 int[] next =new int[dest.length()]; next[0]=0;//如果字符串长度为1部分匹配值就是0 for(int i=1,j=0;i //当dest.chatAt(i)!=des.cahrAt(j),我们需要从next[j-1]获取新的j //直到我们发现有dest.chatAt(i)==des.cahrAt(j)成立才退出 //kmp算法的核心核心点 while (j>0&&dest.charAt(i)!=dest.charAt(j)){ j=next[j-1]; } //当dest.charAt(i)==dest.charAt(j)满足时，部分匹配值+1 if(dest.charAt(i)==dest.charAt(j)){ j++; } next[i]=j; } return next; } Kmp查找算法代码实现 public static int kmpSerach(String str1,String str2,int[] next){ //遍历 for(int i=0,j=0;i //需要处理str1.charAt(i)!= str2.charAt(j),去调整j的大小 while (j>0 && str1.charAt(i)!=str2.charAt(j)){ j=next[j-1]; } if(str1.charAt(i)==str2.charAt(j)){ j++; } if(j==str2.length()){// return i-j+1; } } return -1; } 5、贪心算法 概念：贪心算法（贪婪算法）在对问题求解时，在每一步中都选择最好或者最优（即最有利）的选择，从而希望能够导致的结果是最好的或者最优的。 note：贪心算法所得到的结果不一定是最优的结果（有时候会是最优解），但都是对近似（接近）最优解的结果。 案列 集合覆盖问题，假设存在以下付费的广播电台，让广播台的信号可以覆盖所有地区，如何选择最少的广播台，让所有的地区都可以接受到信号。 广播台覆盖地区K1北京，上海，天津K2广州，北京，深圳K3成都，上海，杭州K4上海，天津K5杭州，大连 算法描述： 遍历所有的广播电视台，找到一个覆盖了最多未覆盖地区的电台（此电台可能包含一些已覆盖的地区）将这个电台加入到一个集合中，并把该电台覆盖的地区在下次比较时去掉重复第一步直到覆盖所有的地区 代码实现 public class GreedAlgorithm { public static void main(String[] args){ //创建广播电视台，放入到Map HashMap //将各个电视台放入到broadcastszh HashSet hashSet1.add("北京"); hashSet1.add("上海"); hashSet1.add("天津"); HashSet hashSet2.add("广州"); hashSet2.add("北京"); hashSet2.add("深圳"); HashSet hashSet3.add("成都"); hashSet3.add("上海"); hashSet3.add("杭州"); HashSet hashSet4.add("上海"); hashSet4.add("天津"); HashSet hashSet5.add("杭州"); hashSet5.add("大连"); //加入到map broadcasts.put("k1",hashSet1); broadcasts.put("k2",hashSet2); broadcasts.put("k3",hashSet3); broadcasts.put("k4",hashSet4); broadcasts.put("k5",hashSet5); //创建一个allAreas，存放所有的地区 HashSet allAreas.add("北京"); allAreas.add("上海"); allAreas.add("天津"); allAreas.add("广州"); allAreas.add("深圳"); allAreas.add("成都"); allAreas.add("杭州"); allAreas.add("大连"); //创建ArrayList，存放选择电台的集合 ArrayList //定义一个临时的集合，在遍历过程中存放电台覆盖的地区和还没有覆盖地区的交集 HashSet //定义maxKey，保存在一次遍历过程中能够覆盖最大的未覆盖地区的电台key //如果maxKey，不为null，则会加入到selects String maxKey =null; while (allAreas.size()!=0){ //每进行一次循环， maxKey=null; //遍历所有的broadcast，找出对应的key for (String key:broadcasts.keySet()){ //没进行一次for tempSet.clear(); //当前这key能够覆盖的地区 HashSet tempSet.addAll(areas); //求出tempSet和allAreas的交集，交集会付给tempSet tempSet.retainAll(allAreas); //如果当前这个集合包含的未覆盖的地区数量，比maxKey指向的地区还多，就需要重置maxKey if(tempSet.size()>0&&(maxKey==null||tempSet.size()>broadcasts.get(maxKey).size())){ maxKey=key; } } //maxKey!=null,就应该将maxKey加入selects if(maxKey!=null){ selects.add(maxKey); //将maxKey的指向广播电台的覆盖地区。从allAreas去掉 allAreas.removeAll(broadcasts.get(maxKey)); } } System.out.println(selects); } } 6.普利姆算法 概念 普利姆算法本质上是求最小生成树（Minimum Cost Spanning Tree）MST,也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含的所有n个顶点的连通子图。 最小生成树：给定一个带权的无向连通图，选取一个生成树，使树上所有边上权的总和为最小 无向图 最小生成树 N个顶点，一定有N-1条边包含全部顶点N-1条边都在图中 算法描述 设G=（V,E）是连通网，T=（U，D）是最小生成树，V,U是顶点的集合，E,D是边的集合若从顶点u开始构造最小生成树，则从集合v中取出顶点u放入集合U中，并标记顶点visited[u]=1若集合U中的顶点ui与集合V-U中的顶点vi存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入到集合D中，并标记visited[vj]=1重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边 案列（修路问题） 有7个村庄（A,B,C,D,E,F,G）,现在需要修路把7个村庄连通，使得修路的总里程最短 代码实现 public void prime(Mgraph mgraph,int v){ //标记被访问结点的数组 int visited[]=new int[mgraph.vertexs]; int minWeight=10000;//将两节点间的权重设置为较大的值 int h1=-1; int h2=-1; int total=0; visited[v]=1;//将起始结点标记被访问 for (int k=1;k //已经被访问过的结点的循环 for (int i=0;i //与访问过的结点；邻近结点 for (int j=0;j if (visited[i]==1&&visited[j]==0&&mgraph.weight[i][j] minWeight=mgraph.weight[i][j]; h1=i; h2=j; } } } total+=minWeight; System.out.println("边<"+mgraph.data[h1]+","+mgraph.data[h2]+">权值"+minWeight); //将当前这个结点标记为已访问 visited[h2]=1; minWeight=10000; } System.out.printf("总路程数为"+total); } 7、克鲁斯卡尔算法 定义：克鲁斯卡尔（Kruskal）算法是用来求加权连通图的最小生成树的算法，它是按照权值从小到大的选择选择（n-1）条边并且不构成回路。 案列（公交车路线） 描述：对公交车站点（A、B、C、D、E、F、G）进行连通，并且使得修建公路的总里程数最小。 图解 代码实现 public void krusal() { int index = 0;//表示最后结果数组的索引 int[] ends = new int[edgeNum];//用于保存”已有最小生成树“中的每个顶点在最小生成树中的终点 //创建结果数组，保存最小生成树 Edata[] rets=new Edata[edgeNum]; //获取图中的所有边的集合，一共有12个边 Edata[] edges=getEdges(); System.out.println("图的边的集合="+Arrays.toString(edges)+"共"+edges.length);//12 //按照边的权值进行大小排序 sortEdges(edges); //遍历edges数组，将边添加到最小生成树中时，判断准备加入的边是否形成了回路，如果没有，就加入rests，否则不能加入 for (int i=0;i //获取到第i条边的第一个顶点 int p1=getPsiton(edges[i].start); //获取到第i条边的第2个顶点 int p2=getPsiton(edges[i].end); //获取p1这个顶点在已有最小生成树中的终点 int m=getEnd(ends,p1); //获取p2这个顶点在已有最小生成树的终点 int n=getEnd(ends,p2); //是否构成回路 if (m!=n){ ends[m]=n; rets[index++]=edges[i];//有一条边加入到rests数组中 } } System.out.println("最小生成树为="+Arrays.toString(rets)); } 8、迪杰斯特拉算法 概念：迪杰斯特拉算法是典型的最短路径算法，用于计算一个结点到其它结点的最短路径。它的主要特点是以起始点为中心向外层层扩展（广度优先搜索的思想），直到扩展到终点为止。 算法分析 设置出发顶点为v，顶点集合V（v1,v2,vi…）,v到V中顶点的距离构成距离集合Dis，Dis{d1,d2,di…},Dis集合记录着v到图中各个顶点的距离（到自身可以看做是0，v到vi的距离对应为di） 从Dis中选择最小的dis并移除Dis集合，同时移出V集合中对应的顶点vi,此时的v到vi为最短路径更新Dis集合，更新规则为：比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留较小的一个（同时也应该更新顶点的前驱结点为vi，表明是通过vi到达的）重复执行两步步骤，直到最短路径顶点为目标顶点即可结束。 案例（最短路径） 邮差送邮件,从G点开始，分别把邮件送到A、B、C、D、E、F、G六个地点，计算G点到各个地点的最短距离。 代码实现 9、弗洛伊德算法 概念：和迪杰斯特拉一样，弗洛伊德算法也是求给定加权图中顶点间最短路径的算法。但是迪杰斯特拉算法是通过选定被访问的结点，求出从出发访问结点到其它顶点的最短路径。而弗洛伊德算法中的每一个顶点都是出发访问点，所以需要将每一个顶点都看做被访问的顶点，求出每一个顶点到其它顶点的最短路径。 算法分析 设置顶点vi到顶点vk的最短路径已知为Lik,顶点vk到顶点vj的最短路径为Lkj，顶点vi到顶点vj的路径为Lij，则vi到vj的最短路径为min((Lik+Lki),Lij),vk的取值为图中的所有顶点，则可获得vi到vj的最短路径 代码实现 public void floyd(){ int len=0;//变量保存距离 //对中间顶点遍历,就是中间顶点的下标 for (int k=0;k for (int i=0;i for (int j=0;j //从i顶点出发，经过k顶点，到达j顶点的距离 len=dis[i][k]+dis[k][j]; if (len dis[i][j]=len;//更新距离 pre[i][j]=pre[k][j];//更新前驱结点 } } } } } 10、马踏棋盘算法 案列（网上的图解） 采用回溯的方法进行的，首先确定一个点的所有可以走的点，然后选择一个点（该点的下一步可走的点的数量最少），一直进行回溯，直到走完棋盘上的全部带点。 按照马走“日”字的规则进行移动，要求每个方格只进行一次，走遍棋盘上的全部64个方格 代码实现 public static void traversalChessboard(int[][] chessboard,int row,int column,int step){ chessboard[row][column]=step; visited[row*X+column]=true;//标记该位置已被访问 //获取当前位置可以走的下一位置的集合 ArrayList sort(ps); while (!ps.isEmpty()){ Point p=ps.remove(0);//取出下一个可以走的位置 //判断该点是否被访问过 if (!visited[p.y*X+p.x]){//说明还没有被访问过 traversalChessboard(chessboard,p.y,p.x,step+1); } } //判断马儿是否完成了任务，使用step和应该走的步数比较 //如果没有达到数量，则表示没有完成任务，将棋盘置位0 //1、棋盘到目前的位置，仍然没有走完 //2、棋盘处于一个回溯过程 if(step chessboard[row][column] = 0; visited[row*X+column]=false; }else { finished=true; } }