专栏首页猿计划insertionSoft(插入排序) 2.1-1 And 重写insertionSoft 2.1-2

insertionSoft(插入排序) 2.1-1 And 重写insertionSoft 2.1-2

input:{31,41,59,26,41,58}

output:{31,26,41,41,58,59}

伪代码:

InsertionSort(A, n) {
   for j = 2 to n {    
        key = A[j];    
        i = j - 1;     
        while (i > 0) and (A[i] > key) {          
            A[i+1] = A[i];         
            i = i - 1;    
         }          
        A[i+1] = key;
     }          
}

真代码:

    public static int[] insertionSoftIntArr(int[] A){
        for (int i = 2; i < A.length; i++) {
            int key = A[i];
            int j = i -1;
            while (j > 0 && A[j] > key){
                A[j+1] = A[j];
                j = j -1;
            }
            A[j+1] = key;
        }
        return A;
    }

执行流程:

2.1-2 重写InsertSoft算法使之递减

伪代码:

InsertionSort(A, n) {
     for j = 1 to n {    
         key = A[j];    
         i = j - 1;     
         while (i >= 0) and (A[i] < key) {          
             A[i+1] = A[i];         
             i = i - 1;    
          }          
         A[i+1] = key;
      }          
}

真实代码:

 public static int[] RewriteinsertionSoftIntArr(int[] A){
        for (int i = 1; i < A.length; i++) {
            int key = A[i];

            int j = i -1;

            while (j >= 0 && A[j] < key){
                A[j+1] = A[j];
                j = j -1;
            }
            A[j+1] = key;
        }
        return A;
    }

过程略

全部代码:

package 测试学习;

/**
 * 插入排序
 * 输入:{31,41,59,26,41,58}
 *
 */
public class insertionSoft {

    public static void main(String[] args) {
        int [] A = {31,41,59,26,41,58};


        A = RewriteinsertionSoftIntArr(A);

        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i]+" ");
        }
    }


    public static int[] insertionSoftIntArr(int[] A){
        for (int i = 2; i < A.length; i++) {
            int key = A[i];

            int j = i -1;

            while (j > 0 && A[j] > key){
                A[j+1] = A[j];
                j = j -1;
            }
            A[j+1] = key;
        }
        return A;
    }

    /**
     * 重写
     * @param A
     * @return
     */
    public static int[] RewriteinsertionSoftIntArr(int[] A){
        for (int i = 1; i < A.length; i++) {
            int key = A[i];

            int j = i -1;

            while (j >= 0 && A[j] < key){
                A[j+1] = A[j];
                j = j -1;
            }
            A[j+1] = key;
        }
        return A;
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer LeetCode 面试题59 - I. 滑动窗口的最大

    输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释:

    TrueDei
  • 剑指Offer LeetCode 面试题17. 打印从1到最大的n位数

    输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。

    TrueDei
  • 剑指Offer LeetCode 面试题21. 调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

    TrueDei
  • 奇数魔方阵(奇数幻方)

    mathor
  • 这种方式写冒泡,更简单

    冒泡排序,相信大家听到这四个字都觉得很简单,我觉得也是,但能不能更简单呢?比如,用递归实现。

    一个优秀的废人
  • 第88场周赛

    第二反应:根据上述这个模拟超时过程,想一优化,shifts数组后面开始,逐个偏移,根据描述,后面的偏移会加到前面。于是有了后缀和这一说法。

    用户1145562
  • 树的重心(个人模版)

    树的重心(树的重心定义为:找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心) 1 #include<stdio.h> 2 #inc...

    Angel_Kitty
  • LeetCode 454. 四数相加 II(哈希)

    给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l]...

    Michael阿明
  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常
  • 1365 浴火银河星际跳跃

    1365 浴火银河星际跳跃 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 小...

    attack

扫码关注云+社区

领取腾讯云代金券