虫虫的技术博客 技术 生活

Tuesday, April 30, 2019

面试基础-插入排序

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

测试输入: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

0 comments:

Post a Comment

Popular Posts

Copyright © 虫虫的成长历程 | Powered by Blogger Design by PWT | Blogger Theme by NewBloggerThemes.com