排序算法

/**  * 冒泡排序，每进行一次大循环，最值就会冒泡一样出来  * @param args  */ public static void main(String[] args) {  int[] arr={5,4,9,2,1};  //i为每次循环比较时的，冒泡后剩余元素的最大索引值  //比如第二次，已经冒泡出一个，剩下四个元素，那就是0-4中间的比较，最大索引值为4  //最后一次，那就是冒泡出了三个，剩下俩元素，那就是0-1中间的比较，最大索引值为1  for (int i = arr.length-1; i >0; i--) {   //里面层，依次比较临近元素，比较的最大值放在右边，这样最后冒泡出的最大值就在最右边。   //每次就是索引0和1比，1和2比，。。。最后就是i-1和i比。因此j最大为i-1   for (int j = 0; j < i; j++) {    if (arr[j]>arr[j+1]){     int temp=arr[j+1];     arr[j+1]=arr[j];     arr[j]=temp;    }   }  } }

/**<br>&nbsp;*&nbsp;选择排序，每进行一次大循环就选择出当前数组最小(或最大)的数。<br>&nbsp;*&nbsp;@param&nbsp;args<br>&nbsp;*/<br>public&nbsp;static&nbsp;void&nbsp;main(String[]&nbsp;args)&nbsp;{<br>&nbsp;int[]&nbsp;arr={5,4,9,2,1};<br>&nbsp;//每执行一次循环，就把最小的元素放到最左边。<br>&nbsp;//外层是核心元素索引,<br>&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;=&nbsp;arr.length-2;&nbsp;i++)&nbsp;{<br>&nbsp;&nbsp;//里层是每次循环要比的元素，最小就是核心元素后面那个，最大就是数组最后一个元素<br>&nbsp;&nbsp;for&nbsp;(int&nbsp;j&nbsp;=&nbsp;i+1;&nbsp;j&nbsp;&lt;=&nbsp;arr.length-1;&nbsp;j++)&nbsp;{<br>&nbsp;&nbsp;&nbsp;if&nbsp;(arr[j]&lt;arr[i]){<br>&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;temp=arr[i];<br>&nbsp;&nbsp;&nbsp;&nbsp;arr[i]=arr[j];<br>&nbsp;&nbsp;&nbsp;&nbsp;arr[j]=temp;<br>&nbsp;&nbsp;&nbsp;}<br>&nbsp;&nbsp;}<br>&nbsp;}<br>}

/**<br>&nbsp;*&nbsp;插入排序：就是从数组目前的第二个元素开始，依次和前面的比较后再插入的。<br>&nbsp;*&nbsp;就像数组原来就一个元素，后面的元素插入前都与已存在的元素进行了比较。<br>&nbsp;*&nbsp;{5,4,22,1,9,13};就当做当前只有一个元素5，后面的元素依次取出，并与已插入的元素(也就是前面的元素)进行比较大小来确定插入新数组所在的索引位置<br>&nbsp;*&nbsp;4，5==》4,5,22==》1,4,5,22==》1,4,5,9,22==》1,4,5,9,13,22<br>&nbsp;*&nbsp;@param&nbsp;arr<br>&nbsp;*/<br>//此次是从小到大排序<br>public&nbsp;static&nbsp;void&nbsp;main(String[]&nbsp;args)&nbsp;{<br>&nbsp;int[]&nbsp;arr={5,4,9,6,1};<br>&nbsp;//外层循环意义：新插入元素的老索引.i从1开始，因为第一个元素直接插入不用比较<br>&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;1;&nbsp;i&nbsp;&lt;=&nbsp;arr.length-1;&nbsp;i++)&nbsp;{<br>&nbsp;&nbsp;//新插入元素需要与已插入的所有元素进行依次比较，<br>&nbsp;&nbsp;//比如插入的是第四个元素6，此时数组为{4,5,9,6,1}那就要6和9比，交换，6再和5比，不交换，5再和4比，不交换。<br>&nbsp;&nbsp;for&nbsp;(int&nbsp;j&nbsp;=&nbsp;i-1;&nbsp;j&nbsp;&gt;=&nbsp;0;&nbsp;j--)&nbsp;{<br>&nbsp;&nbsp;&nbsp;if&nbsp;(arr[j+1]&lt;arr[j]){<br>&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;temp=arr[j+1];<br>&nbsp;&nbsp;&nbsp;&nbsp;arr[j+1]=arr[j];<br>&nbsp;&nbsp;&nbsp;&nbsp;arr[j]=temp;<br>&nbsp;&nbsp;&nbsp;}else{//因为是依次进行比较的，当不进行交换时，前面的元素都是已经排序插入的，就不需要再比较了<br>&nbsp;&nbsp;&nbsp;&nbsp;j=0;<br>&nbsp;&nbsp;&nbsp;}<br>&nbsp;&nbsp;}<br><br>&nbsp;}<br>}<br>

/**<br>&nbsp;*&nbsp;@ClassName&nbsp;T3<br>&nbsp;*&nbsp;@description:$将数组当做二叉树，思考会更简单<br>&nbsp;*&nbsp;@author:&nbsp;李杰<br>&nbsp;*&nbsp;@create:&nbsp;2021-12-01&nbsp;00:27<br>&nbsp;*&nbsp;@Version&nbsp;1.0<br>&nbsp;**/<br>public&nbsp;class&nbsp;T&nbsp;{<br><br>&nbsp;&nbsp;&nbsp;&nbsp;/**<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;归并排序：先把数组依次拆分，拆分到每个组只有一个，再进行合并。类似于树的递归运算。<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;args<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<br>&nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;void&nbsp;main(String[]&nbsp;args)&nbsp;{<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int[]&nbsp;arr={5,4,22,1,9,13};<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sortArr(arr,0,arr.length-1);<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;arr.length;&nbsp;i++)&nbsp;{<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(arr[i]);<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>&nbsp;&nbsp;&nbsp;&nbsp;}<br><br>&nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;void&nbsp;sortArr(int[]&nbsp;arr,&nbsp;int&nbsp;start,&nbsp;int&nbsp;end)&nbsp;{<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//首先判断是否已经不用再拆分了<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(end&gt;start){<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//拆分<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;mid=(start+end)/2;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sortArr(arr,&nbsp;start,&nbsp;mid);<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sortArr(arr,&nbsp;mid+1,&nbsp;end);<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;merge(arr,start,mid,mid+1,end);<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}else{<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//不用拆分了<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println("拆分到最小了，反转向上合并");<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br><br>&nbsp;&nbsp;&nbsp;&nbsp;}<br><br>&nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;void&nbsp;merge(int[]&nbsp;arr,&nbsp;int&nbsp;start1,&nbsp;int&nbsp;end1,&nbsp;int&nbsp;start2,&nbsp;int&nbsp;end2)&nbsp;{<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//定义一个临时数组：存放俩数组合并后的所有元素<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int[]&nbsp;temp=new&nbsp;int[end2-start1+1];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//定义左数组的未比较元素的最小索引<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;left=start1;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//定义右数组的未比较元素的最小索引<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;right=start2;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//依次取出每个数组的最小索引元素来比较,将最小元素放到temp<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;temp.length;&nbsp;i++)&nbsp;{<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(left&gt;end1){<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//左数组已经没有元素了，不用比较，直接将右数组元素放入temp<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp[i]=arr[right];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;right++;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}else&nbsp;if&nbsp;(right&gt;end2){<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//右数组已经没有元素了，不用比较，直接将左数组元素放入temp<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp[i]=arr[left];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;left++;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}else{//左右数组都有元素，则进行比较<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(arr[left]&gt;arr[right]){<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp[i]=arr[right];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;right++;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}else{<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp[i]=arr[left];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;left++;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//将排序归并的数组temp覆盖掉原数组<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;index=start1;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;temp.length;&nbsp;i++)&nbsp;{<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr[index]=temp[i];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index++;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>&nbsp;&nbsp;&nbsp;&nbsp;}<br>}<br>