IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> Java实现数据结构基本算法——排序——插入排序(Insertion_Sort) -> 正文阅读

[数据结构与算法]Java实现数据结构基本算法——排序——插入排序(Insertion_Sort)


一、插入排序的定义及分类

插入排序的基本思想:每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列中,直到全部记录插入完成。
分类:直接插入排序、折半插入排序、希尔排序。


二、插入排序——直接插入排序

1. 基本思想:

(1)将待排序的记录序列划分位有序区无序区,初始时有序区为待排记录的第一个元素(只有一个元素arr[0]),无序区包括所有剩余待排的元素(arr[1] 到 arr[arr.length - 1])共arr.length - 1 个元素;
(2)将无序区中的第一个记录插入到有序区的合适位置中,从而使无序区减少一个元素,有序区增加一个元素;
(3)重复执行步骤(2),直到无序区中所有的记录都取完,再也没有剩余元素为止,这样前面的有序区就是经过排序得到的有序序列


2. 排序过程:

元素下标0123456
初始序列【 49 】386597761327
第1躺排序之后【 3849 】6597761327
第2躺排序之后【 384965 】97761327
第3躺排序之后【 38496597 】761327
第4躺排序之后【 3849657697 】1327
第5躺排序之后【133849657697 】27
第6躺排序之后【13273849657697 】

3. 代码实现:

public class Straight_Insertion_Sort {
    public static void main(String[] args){
        int[] arr = {49,38,65,97,76,13,27};
        int i , j;
        System.out.println("初始序列:"+ Arrays.toString(arr));
        //先将a[0]放入有序区,将剩下的 (arr.length - 1) 个元素放入无序区,所以循环从 i = 1开始
        for( i = 1 ; i < arr.length ; i ++){
            int temp = arr[i];          //每次循环将arr[i]插入到它前面已排序的子序列中
                for( j = i - 1 ; j > -1 && arr[j] > temp ; j--){        //将前面较大的元素后移
                    arr[j+1] = arr[j];
                }
                arr[j+1] = temp;        //temp值到达插入位置
        }
        System.out.println("排序后结果:"+ Arrays.toString(arr));
    }
}


4. 运行结果:

初始序列:[49, 38, 65, 97, 76, 13, 27]
排序后结果:[13, 27, 38, 49, 65, 76, 97]

三、插入排序——折半插入排序

1. 基本思想:

将比较操作和移动操作分离开来,即先折半查找出元素的待插入位置,然后再统一移动插入位置之后的元素。
在有序表中查找插入位置时,可以不断二分有序表来确定插入位置,即一次比较,通过待插入记录与有序表居中的记录按关键码比较,将有序表一分为二,下次的比较操作在其中一个有序子表中进行,按同样的方法再将子表一分为二,这样继续下去,直到要比较的子表中只有一个记录时进行最后一次比较,便确定插入位置。


2. 排序过程:

元素下标0123456
初始序列49386597761327
第1躺排序之后38496597761327
第2躺排序之后38496597761327
第3躺排序之后38496597761327
第4躺排序之后38496576971327
第5躺排序之后13384965769727
第6躺排序之后13273849657697

3. 代码实现:


public class Binary_Insertion_Sort {
    public static void main(String[] args){
        int[] arr = {49,38,65,97,76,13,27};
        int i , j , low , high , mid;
        System.out.println("初始序列:"+ Arrays.toString(arr));
        for(i = 1 ; i < arr.length ; i++){
            if(arr[i] < arr[i-1]){
                int temp = arr[i];      //缓存下标为i的元素
                //记录搜索范围的左边界
                low = 0; 
                //记录搜索范围的有边界
                high = i - 1;
                //折半确定插入位置
                while(low <= high){
                    //记录中间位置
                    mid = ( low + high) / 2;
                    //比较中间位置数据和 i 处数据大小 , 以缩小搜索范围
                    if(arr[mid] > temp)
                        high = mid - 1;
                    else
                        low = mid + 1;
                }
                //将 high ~ i 处数据整体向后移动一位
                for( j = i - 1 ; j > -1 && j >= high ; j--){
                    arr[j+1] = arr[j];
                }
                arr[high + 1] = temp;

            }
//            System.out.printf("第%d躺排序结果:",i);
//            System.out.println(Arrays.toString(arr));
        }
        System.out.println("排序后结果:"+ Arrays.toString(arr));
    }
}


4. 运行结果:

初始序列:[49, 38, 65, 97, 76, 13, 27]
排序后结果:[13, 27, 38, 49, 65, 76, 97]

四、插入排序——希尔排序

1. 基本思想:

希尔排序也成为“缩小增量排序”,其基本思想是,现将待排序的数组元素分成多个子序列,使得每个子序列的元素个数相对较少,然后对各个子序列分别进行直接插入排序,待整个待排序列“基本有序”后,最后在对所有元素进行一次直接插入排序。因此,我们要采用跳跃分割的策略:将相距某个“增量”的记录组成一个子序列,这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。希尔排序是对直接插入排序算法的优化和升级
具体过程如下:
(1)选择一个步长序列:d1 ,d2 ,… ,di ,… dj ,… , dk ,其中 di > dj , dk=1;
(2)按步长序列个数k,对序列进行k躺排序;
(3)每趟排序,根据对应的步长 di ,将待排序列分割成若干长度为 m = n / di 或 m = n / di + 1 ,分别对各子表进行直接插入排序,仅步长因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度。


2. 排序过程:

不同步长的排序过程如下:
在这里插入图片描述


3. 代码实现:

public class Shell_Sort {
    public static void main(String[] args){
        int[] arr = {49,38,65,97,76,13,27,38,55,4};
        int i , j , d;
        System.out.println("初始序列:"+ Arrays.toString(arr));
        for (d = arr.length / 2 ; d >= 1 ; d = d / 2){
            for (i = d  ; i < arr.length ; i++){
                    int temp = arr[i];
                    j = i - d;
                    while (j >= 0 && temp < arr[j]){
                        arr[j+d] = arr[j];
                        j -= d;
                    }
                    arr[j+d] = temp;
            }
        }
        System.out.println("排序后结果:"+ Arrays.toString(arr));
    }
}

4. 运行结果:

初始序列:[49, 38, 65, 97, 76, 13, 27, 38, 55, 4]
排序后结果:[4, 13, 27, 38, 38, 49, 55, 65, 76, 97]

五、算法分析

一般应从以下几方面综合考虑:1. 时间复杂度;2. 空间复杂度;3. 稳定性;4. 算法简单性; 5. 待排序记录个数;6. 记录本身信息量大小;7. 关键码分布情况。

排序方法平均时间最坏情况辅助空间稳定性不稳定举例
直接插入排序O(n2)O(n2)O(1)稳定
折半插入排序O(n2)O(n2)O(1)稳定
希尔排序O(n2)O(n2)O(1)不稳定60,60’,50(d = 2,1)

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-11 12:40:50  更:2021-08-11 12:41:42 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 17:28:14-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计