数据结构与算法之插入排序(含改进版)

常用数据结构与算法实现

以下博客根据B站罗召勇老师视频:数据结构与算法基础-Java版(罗召勇)写的详细笔记


数据结构与算法基础:


数据结构与算法之基础概述


数据结构:


(一)数据结构与算法之数组

(二)数组结构与算法之栈

(三)数据结构与算法之队列

(四)数据结构与算法之链表

(五)数据结构与算法之树结构基础

(六)数据结构与算法之二叉树大全

(七)数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)

(八)数据结构与算法之多路查找树(2-3树、2-3-4树、B树、B+树)

(九)数据结构与算法之图结构


十大经典算法:


(一)数据结构与算法之冒泡排序(含改进版)

(二)数据结构与算法之选择排序(含改进版)

(三)数据结构与算法之插入排序(含改进版)

(四)数据结构与算法之希尔排序

(五)数据结构与算法之归并排序

(六)数据结构与算法之快速排序

(七)数据结构与算法之堆排序

(八)数据结构与算法之计数排序

(九)数据结构与算法之桶排序

(十)数据结构与算法之基数排序


插入排序概念

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间


动图展示:

数据结构与算法之插入排序(含改进版)



代码实现

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        insertSort(arr);
//        [4, 5, 6, 3, 2, 1]
//        [4, 5, 6, 3, 2, 1]
//        [3, 4, 5, 6, 2, 1]
//        [2, 3, 4, 5, 6, 1]
//        [1, 2, 3, 4, 5, 6]
    }

    //插入排序
    public static void insertSort(int[] arr) {
        //遍历所有的数字,从第二个开始和前一个比较
        for (int i = 1; i < arr.length; i++) {
            //如果当前数字比前一个数字小
            if (arr[i] < arr[i - 1]) {
                //把当前遍历的数字存起来
                int temp = arr[i];
                //遍历当前数字前面的数字
                int j;
                for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                    //把前一个数赋给后一个数
                    arr[j + 1] = arr[j];
                }
                //把临时变量(外层for循环的当前元素)赋给不满足条件的后一个元素
                arr[j + 1] = temp;
            }
            //打印每次排序后的结果
            System.out.println(Arrays.toString(arr));
        }
    }
}

时间复杂度

最优时间复杂度:O(n) (升序排列,序列已经处于升序状态)

最坏时间复杂度:O(n^2)

稳定性:稳定

在第一趟排序中,插入排序最多比较一次,第二趟最多比较两次,依次类推,最后一趟最多比较N-1次。因此有:1+2+3+...+N-1 = N*N(N-1)/2


因为在每趟排序发现插入点之前,平均来说,只有全体数据项的一半进行比较,我们除以2得到:N*N(N-1)/4


复制的次数大致等于比较的次数,然而,一次复制与一次比较的时间消耗不同,所以相对于随机数据,这个算法比冒泡排序快一倍,比选择排序略快。


与冒泡排序、选择排序一样,插入排序的时间复杂度仍然为O(N^2),这三者被称为简单排序或者基本排序,三者都是稳定的排序算法。


如果待排序数组基本有序时,插入排序的效率会更高


代码改进

在插入某个元素之前需要先确定该元素在有序数组中的位置,上例的做法是对有序数组中的元素逐个扫描,当数据量比较大的时候,这是一个很耗时间的过程,可以采用二分查找法改进,这种排序也被称为二分插入排序

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        insertSort(arr);
//        [4, 5, 6, 3, 2, 1]
//        [4, 5, 6, 3, 2, 1]
//        [3, 4, 5, 6, 2, 1]
//        [2, 3, 4, 5, 6, 1]
//        [1, 2, 3, 4, 5, 6]
    }

    //二分插入排序
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //如果新记录小于有序序列的最大元素,则用二分法找出新纪录在有序序列中的位置
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i]; //定义temp存储所要插入的数
                int left = 0; //最左边的数,从str[0]开始
                int right = i - 1; //最右边位,所要插入那个数的前一位

                while (left <= right) {
                    int middle = (left + right) / 2;   //mid中间位
                    //如果值比中间值大,让left右移到中间下标+1
                    if (arr[middle] < temp) {
                        left = middle + 1;
                    }
                    //如果值比中间值小,让right左移到中间下标-1
                    else {
                        right = middle - 1;
                    }
                }
                //以左下标为标准,在左位置前插入该数据,左及左后边全部后移
                for (int j = i; j > left; j--) {
                    arr[j] = arr[j - 1];
                }
                arr[left] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}



上一篇:WPF System.Windows.Interactivity 使用示例


下一篇:在spring cloud eureka中使用ip而不是hostname