插入排序：

思想：

插入排序和打牌一样，核心：数小往前插，数大则不管。
一个数只和它前面的那个数进行比较，
如果比前面的数小,则该元素往前边插去（交换位置），然后继续向前进行新的比较；
如果比前面的数大，则不将该元素往前插入（即，不管该数了），直接进行去轮询到（后边的）下一个元素；

时间复杂度：
插入排序的平均时间复杂度是O(n²)。

eg——举例： 4,2,5,1,7
　　第一轮： i=1
　　内循环, 拿到数2,和4进行对比，2小，换位置;
　　即：2,4,5,1,7
　　交换位置之后，j–,不满足j>0了，所以内循环结束；
　　
　　第二轮： i++,所以i=2
　　内循环,拿到数5，和4比，位置不变，直接跳出内循环，进行下一轮;
　　即：2,4,5,1,7
　　
　　第三轮： i++,所以i=3
　　内循环,拿到数1，和5比，交换位置，
　　即：2,4,1,5,7
　　 j–,继续内循环，即1再往前和4比，又交换位置，
　　即：2,1,4,5,7
　　 j–,继续内循环，1继续往前和2比，再次交换位置;
　　即：1,2,4,5,7
　　 j–,不满足j>0了，所以内循环结束；
　　
　　第四轮： i++,所以i=4
…

代码：

package charupaixu;/** * @author：张永辉; * @date: 2020/3/16; 9:20 * todo: 插入排序：（每个元素只和它前边的那个元素进行比较）， *                      如果比前边的元素小，则该元素往前边插去（交换位置），然后继续比较； *                      如果该元素比前边的元素大或相等，则不将该元素往前插入，直接进行轮询（后边的）下一个元素； */public class ChaRu2 {
       public static void main(String[] args) {
           //        一，定义数组：        int[] arr = {
   23,54,65,3,5,2,87,33,345,435,11,325,555,121,346,0,20,49,17};//        二，定义一个临时变量，用来后边交换元素顺序，作中间值；        int temp = 0;//        三，开始排序：//         	1），常规操作，先定义一个外循环：        for (int i = 1; i < arr.length; i++) {
   //			2），再定义一个内循环：            for (int j = i; j >0; j--) {
   //                2.1）如果一个元素，比它前面的那个元素小：                if (arr[j] < arr[j-1]) {
   //                    2.1.1）则往前插入（交换位置）                    temp = arr[j];                    arr[j] = arr[j - 1];                    arr[j - 1] = temp;//                    2.1.2）并继续往前比较；(即，j--;//                          j--的话，则j必须>0，所以，j的初始值应为1、不能为0)                }//                2.2）如果该元素，大于等于它前边的那个元素，则不管该元素了，继续往后边遍历下一个元素,即，j++；//                  可是上边的for循环已经规定了j--了，那怎么j++呢？//                     答：可以让i++，然后将i的值赋给j，不就实现j++了嘛！//                        所以，j的初始值为：j=i; 所以，i的初始值应为1；////                        总结，如果该元素大于等于它前边的那个元素，则继续往后边遍历下一个元素——跳出当前内循环（为了让i++，然后将i的值赋给j，从而实现j++）；                else{
                       break;                }            }        }        //        四，打印结果：        for (int i : arr) {
               System.out.print(i+"----");        }    }}

转载地址：http://hktzi.baihongyu.com/

你可能感兴趣的文章