面试基础-插入排序

第二个排序算法，插入排序的思想是遍历数组中的每一个元素，插入到已经有序的数组中，插入的过程仍需保持数组的有序性。实际写代码时，插入的过程类似于冒泡的过程，从后往前遍历，找到合适的位置插入。插入排序是一次只关心一个元素，直接找到最终位置，冒泡排序是一次比较若干元素，找到一个最大元素放到最终位置。

测试输入：new int[]{1, 17, 6, 9, 2, 4, 100, 38, 94, 29, 46, 3, 57, 65, 19, 5};



    /**
     * 从后往前遍历插入，这个插入过程有点像冒泡，只冒到合适的位置即可
     *
     * @param arr
     */
    public void sort(int[] arr) {
        int compareTimes = 0;
        int swapTimes = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                compareTimes++;
                if (arr[j] < arr[j - 1]) {
                    Util.swap(arr, j, j - 1);
                    swapTimes++;
                } else {
                    break;
                }
            }
        }
        System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes);
    }

打印输出：数组长度:16 比较次数:61 交换次数:46


图片仍来自百度，图片能大致反应排序的思想，但仍不能完全的反应内存真实的动作，所以想自己写一个动画，来反应排序过程中数据在内存中的动画效果，包括比较过程，包括交换过程。努力ing

评论

发表评论

此博客中的热门博文

Tree : Top View - HackerRank解题记录

图片
题目： You are given a pointer to the root of a binary tree. Print the top view of the binary tree. Top view means when you look the tree from the top the nodes, what you will see will be called the top view of the tree. See the example below. You only have to complete the function. For example :    1     \      2       \        5       /  \      3    6       \        4 Top View : 1 -> 2 -> 5 -> 6 Input Format You are given a function, void topView(node * root) { } Constraints 1 Nodes in the tree  500 Output Format Print the values on a single line separated by space. Sample Input    1     \      2       \        5       /  \      3    6       \     ...
阅读全文

设计模式-建造者模式

图片
        建造者模式，又叫构建者模式，构建器模式等等，定义这里我就不赘述了，网上书上都很多，可以很方便找来看。我为什么不说一遍呢，第一，觉得大部分的定义都描述的不是很易懂，第二，我自己目前还没达到能够下定义的水平。         先来看看代码，然后再给出我的理解。 public class Article { private String title ; private String content ; private String sign ; private Date time ; //省略了getter,setter,toString } public interface ArticleBuilder { void setTitle (String title) ; void buildContent (String title) ; void setTime (Date date) ; Article getResultArticle () ; } public class ConcreteArticleBuilder implements ArticleBuilder { private Article article = new Article() ; @Override public void setTitle (String title) { article .setTitle(title) ; } @Override public void buildContent (String content) { article .setContent(content) ; } @Override public void setTime (Date date) { article .setTime(date) ; } @Override public Article getResultArticl...
阅读全文

设计模式-抽象工厂

图片
        工厂方法模式中，工厂类用于生成一系列对象实例并且以这些对象的父级类型作为返回结果。当有多个这样的工厂，这些工厂之间会生产出一系列不同的对象，这种情况下，我们可以定义一个抽象工厂来描述工厂的行为，即创建一系列对象的方法，再让具体的工厂类继承这个抽象工厂。也可以说是把一个系列的工作抽象出来一个抽象的类型，这个抽象的类型就是抽象工厂。 先来看一下结构图： 下面来看一下具体代码： 定义抽象类型 public interface Animal { void say () ; } public interface Cat extends Animal { } public interface Dog extends Animal { } public interface Duck extends Animal { } 定义抽象工厂接口 public interface AnimalFactory { /** * 抽象工厂方法 * 特点与工厂方法一致： * 创建了一个对象 * 返回类型为一个接口或者抽象类 * 有多个类实现了上述抽象类型 * * @param animalType * @return */ Animal getAnimal (String animalType) ; } 抽象类型的具体类与具体工厂类（US） public class CatUs implements Cat { @Override public void say () { System. out .println( "america cat" ) ; } } public class DogUs implements Dog { @Override public void say () { System. out .println( "america dog" ) ; } } public class DuckUs implements Duck { @Override public...
阅读全文