内部排序之一:插入排序和希尔排序的N中实现

2024-09-02 06:08

本文主要是介绍内部排序之一:插入排序和希尔排序的N中实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

   本来想将所有的内部排序总结为一篇博文,但是随着研究的深入,还是放弃了这个念头,斟前酌后,还是觉得分开来写比较好,具体原因,看完本篇博文也就自然明了了。

   本篇文章主要探讨插入排序和希尔排序,之所将二者放在一起,很明显,是因为希尔排序是建立在插入排序的基础之上的。

   注:以下各排序算法的N种实现方法大部分都是我根据算法思想,自己写出来的,或者是参考其本身的经典实现,我自己都已测试通过,但不敢保证一定都没问题,如果有疑问,欢迎指出。

插入排序

   插入排序的思想很简单,它的基本操作就是将一个数据插入到已经排好序的序列中,从而得到一个新的有序序列。根据查找插入位置的实现思路不同,它又可以分为:直接插入排序、折半插入排序、2-路插入排序。。。这里,我们主要探讨下直接插入排序和折半插入排序。

   直接插入排序

   直接插入排序是最基本的插入排序方法,也是一种最简单的排序方法。其基本实现思想如下:

   1、首先把第一个元素单独看做一个有序序列,依次将后面的元素插入到该有序序列中;

   2、插入的时候,将该元素逐个与前面有序序列中的元素进行比较,找到合适的插入位置,形成新的有序序列;

   3、当有序序列扩大为整个原始序列的大小时,排序结束。

     第一种实现方法

   按照该思想,我第一次写出来的实现代码如下:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
第一种代码形式
插入排序后的顺序为从小到大
*/
void Insert_Sort1( int *arr, int len) 
     int i; 
     //从第1个元素开始循环执行插入排序 
     for (i=1;i<len;i++)    
     {   //将第i个元素分别与前面的元素比较,插入适当的位置 
         if (arr[i]<arr[i-1]) 
         {   //一直向左进行比较,直到插入到适当的位置 
             int key = arr[i]; 
             int count = 0;  //用来记录key在与前面元素时向左移动的位置 
             while (i>0 && key<arr[i-1]) 
            
                 arr[i] = arr[i-1]; 
                 arr[i-1] = key; 
                 i--; 
                 count++; 
            
             //将待插入的数定位到下一个元素, 
             //因为后面还要执行i++,所以这里不再加1 
             i += count;   
         }  
    
}

第二种实现方法


    很明显,上面的代码有些冗杂,如果面试的时候让你手写插入排序的代码,很难一下子写出来。于是,我考虑将while循环去掉,直接在后面再来一个for循环,每次比较,遇到比自己大的就交换,直到遇到比自己小的,才退出for循环。这样代码改成了如下形式:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
第二种代码形式
插入排序后的顺序为从小到大
*/
void Insert_Sort2( int *arr, int len) 
     int i,j; 
     for (i=1;i<len;i++) 
         for (j=i-1;j>=0 && arr[j]>arr[j+1];j--) 
        
             //交换元素数值 
             //由于arr[j]不等于arr[j+1], 
             //因此可以安全地用该交换方法 
             arr[j]^=arr[j+1]; 
             arr[j+1]^=arr[j]; 
             arr[j]^=arr[j+1]; 
        
}

第三种实现方法


   上面的代码要用到数据的交换,即每次要插入的元素要逐个地与前面比它大的元素互换位置,而数据交换需要三步赋值操作,我们完全可以避免进行如此多的操作(排序算法中一般都会尽量避免数据的交换操作),为了提高执行效率(虽然该执行效率的提高可能并没有那么显著),我们再回过头来看第一种实现方法,我们可以通过key变量先将待插入的数据保存起来,在比较时只将元素右移一位即可,最后再将key放到要插入的位置,这样可以减少两个赋值操作的执行时间。这样我们可以把代码改成如下实现形式:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
第三种代码形式
插入排序后的顺序为从小到大
*/
void Insert_Sort3( int *arr, int len) 
     int i,j; 
     for (i=1;i<len;i++) 
         if (arr[i] < arr[i-1]) 
         {   //向前逐个比较,直到需要插入的地方 
             int key = arr[i]; 
             for (j=i-1;j>=0 && arr[j]>key;j--) 
                 arr[j+1] = arr[j]; 
             arr[j+1] = key;    //插入key 
        
}

这也是最常见的实现形式,如果在面试中要手写插入排序的话,直接把这种实现代码写出来就可以了。

   另外,很明显可以看出来,对于长度为n的待排序咧,直接插入排序的平均时间复杂度为O(n*n),而且直接插入排序的比较次数与原始序列的中各元素的位置密切相关,待排序的序列越接近于有序,需要比较的次数就越小,时间复杂度也就越小。



   折半插入排序

    直接插入排序算法简单,且容易实现,当待排序的长度n很小时,是一种很好的排序方法,尤其当原始序列接近有序时,效率更好。如果待排序的长度n很大,则不适宜采用直接排序。这时我们可以考虑对其做些改进,我们可以从减少比较和移动的次数入手,因此可以采用折半插入排序,其思想类似于折半查找,这里不再详细说明,直接给出实现代码:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
插入排序后的顺序为从小到大
*/
void BInsert_Sort( int *arr, int len) 
     int i; 
     //从第1个元素开始循环执行插入排序 
     for (i=1;i<len;i++)    
     {    
         int low =0; 
         int high = i-1; 
         int key = arr[i]; 
         //循环至要插入的两个点之间 
         while (low<=high) 
        
             int mid = (low+high)/2;  
             if (key<arr[mid]) 
                 high = mid-1; 
             else
                 low = mid+1; 
        
         //循环结束后low=high+1,并且low位置即为key要插入的位置 
       
         //从low到i的元素依次后移一位 
         int j; 
         for (j=i;j>low;j--) 
             arr[j] = arr[j-1]; 
         //将key插入到low位置处 
         arr[low] = key; 
    
}

从代码中可以看出,折半插入排序所需附加的存储空间与直接插入排序相等,时间上来看,折半插入排序减少了比较的次数,但是元素的移动次数并没有减少。因此,折半插入排序的平均时间复杂度仍为O(n*n)。



希尔排序    希尔排序(shell排序),又称缩小增量排序。上面我们提到,直接插入排序在原始序列越接近有序的情况下,排序效率越高,希尔排序正是利用了直接插入排序的这个优势。希尔排序的基本思想如下:



   它将序列按照某个增量间隔分为几个子序列,分别对子序列进行插入排序,而后再取另一增量间隔,对划分的子序列进行插入排序,依次往后。。。待序列已经大致有序,最后再对整个序列进行插入排序(即增量间隔为1),从而得到有序序列。

   本文的重点放在排序算法的各种代码实现上,因此不再对具体的实现思想做过多的阐述,读者可以查阅相关资料或书籍来熟悉希尔排序的具体思想。由于希尔排序要用到插入排序,因此,我们依次根据上面基本插入排序的三种不同实现方法来书写希尔排序的代码。


   第一种实现方法


   仔细分析希尔排序的实现思想,会发现,如果要循环对各个子序列依次进行插入排序,我们需要在直接插入排序代码的外面再加一层for循环,用来循环所有的子序列。我们根据插入排序的第一种实现方法写出的代码如下:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
第一种形式的代码
对长为len的数组进行一趟增量为ader的插入排序
本算法在插入排序算法的第一种实现形式上进行修改得到
*/
void Shell_Insert1( int *arr, int len, int ader) 
     int i,k; 
     //循环对ader个子序列进行插入排序操作 
     for (k=0;k<ader;k++) 
         for (i=ader+k;i<len;i+=ader)      //对一个子序列进行插入排序操作 
         {   //将第i个元素分别与前面的每隔ader个位置的元素比较,插入适当的位置 
             if (arr[i]<arr[i-ader]) 
             {   //一直向左进行比较,直到插入到适当的位置 
                 int key = arr[i]; 
                 int count = 0;  //用来记录key在与前面元素比较时向左移动了几个ader长度 
                 while (i>k && key<arr[i-ader]) 
                
                     arr[i] = arr[i-ader]; 
                     arr[i-ader] = key; 
                     i -= ader; 
                     count++; 
                
                 //将待插入的数定位到下一个元素,执行下一次插入排序 
                 //因为后面还要执行i+=ader,所以这里回到原位置即可 
                 i += count*ader;   
             }  
        
}

第二种实现方法

很明显,与上面插入排序的第一种实现方法一样,更加冗杂,现在我们用插入排序的第二种实现方法来实现希尔排序,同样采用添加外层for循环的方式,来循环对每个子序列进行插入排序。代码如下:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
第二种形式的代码
对长为len的数组进行一趟增量为ader的插入排序
本算法在插入排序算法的第三种实现形式上进行修改得到
*/
void Shell_Insert2( int *arr, int len, int ader) 
     int i,j,k; 
     //循环对ader个子序列各自进行插入排序 
     for (k=0;k<ader;k++) 
         for (i=ader+k;i<len;i+=ader) 
             for (j=i-ader;j>=k && arr[j]>arr[j+ader];j-=ader) 
            
                 //交换元素数值 
                 arr[j]^=arr[j+ader]; 
                 arr[j+ader]^=arr[j]; 
                 arr[j]^=arr[j+ader]; 
            
}

第二种实现方法的改进


   上面的代码中需要三个for循环,因为我们是循环对每个子序列进行插入排序的,实际上我们还可以这样做:对每个子序列交叉进行排序。比如,第1个子序列中的第2个元素A5(A5表示它在总序列A中的位置序号是5,下同)刚进行完插入排序操作,便接着对第2个子序列中的第2个元素A6进行插入排序操作。这样我们就可以少写一个for循环,但实际比较的次数还是相同的,只是代码更加简洁。如下:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
在第二种代码的形式上继续精简代码
交叉进行各个子序列的插入排序
*/
void Shell_Insert2_1( int *arr, int len, int ader) 
     int i,j; 
     //交叉对ader个子序列进行插入排序 
         for (i=ader;i<len;i++) 
             for (j=i-ader;j>=0 && arr[j]>arr[j+ader];j-=ader) 
            
                 //交换元素数值 
                 //由于arr[j]不等于arr[j+1], 
                 //因此可以安全地用该交换方法 
                 arr[j]^=arr[j+ader]; 
                 arr[j+ader]^=arr[j]; 
                 arr[j]^=arr[j+ader]; 
            
}

第三种实现方法

  同样,根据插入排序的第三种实现方法,循环逐个对每个子序列进行插入排序操作,我们可以得到希尔排序的实现方法,如下:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
第三种形式的代码
对长为len的数组进行一趟增量为ader的插入排序
本算法在插入排序算法的第二种实现形式上进行修改得到
*/
void Shell_Insert3( int *arr, int len, int ader) 
     int i,j,k; 
     //循环对ader个子序列各自进行插入排序 
     for (k=0;k<ader;k++) 
         for (i=ader+k;i<len;i+=ader) 
             if (arr[i] < arr[i-ader]) 
            
                 int key = arr[i]; 
                 for (j=i-ader;j>=k && arr[j]>key;j-=ader) 
                     arr[j+ader] = arr[j]; 
                 arr[j+ader] = key; 
            
}

第三种实现方法的改进


   我们可以对该方法做出同样的改进,对各个子序列进行交叉排序,代码如下:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
在第三种代码的形式上继续精简代码
交叉进行各个子序列的插入排序
*/
void Shell_Insert3_1( int *arr, int len, int ader) 
     int i,j; 
     //对ader子序列交叉进行插入排序 
     for (i=ader;i<len;i++) 
         if (arr[i] < arr[i-ader]) 
        
             int key = arr[i]; 
             for (j=i-ader;j>=0 && arr[j]>key;j-=ader) 
                 arr[j+ader] = arr[j]; 
             arr[j+ader] = key; 
        
}

同样,如果在面试中要手写希尔排序的代码,推荐这种方法实现的代码。

   希尔排序的时间复杂度根据选择的增量序列不同会有所不同,但一般都会比n*n小(序列长度为n)。

   在选择增量序列时,应使增量序列中的值没有除1之外的公因子,并且最后一个增量值必须为1.

   看如下两个增量序列:

n/2、n/4、n/8...1

1、3、7...2^k-1

   第一个序列称为希尔增量序列,使用希尔增量时,希尔排序在最坏情况下的时间复杂度为O(n*n)。

   第二个序列称为Hibbard增量序列,使用Hibbard增量时,希尔排序在最坏情况下的时间复杂度为O(n^3/2)。

   经验研究表明,在实践中使用这些增量序列要比使用上面两个增量序列的效果好的多,其中最好的序列是

{1、5、9、41、109...}

   该序列中的项或是9*4^i-9*2^i+1,或是4^i-3*2^i+1。

   希尔排序的性能是完全可以接受的,即时是对数以万计的n来说也是如此。编程的简单特点使得它成为对适度的大量输入数据进行排序时经常选用的算法。

完整代码下载    各种实现方式的完整的代码打包下载地址:http://download.csdn.net/detail/mmc_maodun/6969381


来源: csdn   作者:兰亭风雨   
源自:http://tech.ddvip.com/2014-03/1394804220209161.html

这篇关于内部排序之一:插入排序和希尔排序的N中实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1129203

相关文章

Spring Boot配置和使用两个数据源的实现步骤

《SpringBoot配置和使用两个数据源的实现步骤》本文详解SpringBoot配置双数据源方法,包含配置文件设置、Bean创建、事务管理器配置及@Qualifier注解使用,强调主数据源标记、代... 目录Spring Boot配置和使用两个数据源技术背景实现步骤1. 配置数据源信息2. 创建数据源Be

在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

《在MySQL中实现冷热数据分离的方法及使用场景底层原理解析》MySQL冷热数据分离通过分表/分区策略、数据归档和索引优化,将频繁访问的热数据与冷数据分开存储,提升查询效率并降低存储成本,适用于高并发... 目录实现冷热数据分离1. 分表策略2. 使用分区表3. 数据归档与迁移在mysql中实现冷热数据分

linux批量替换文件内容的实现方式

《linux批量替换文件内容的实现方式》本文总结了Linux中批量替换文件内容的几种方法,包括使用sed替换文件夹内所有文件、单个文件内容及逐行字符串,强调使用反引号和绝对路径,并分享个人经验供参考... 目录一、linux批量替换文件内容 二、替换文件内所有匹配的字符串 三、替换每一行中全部str1为st

SpringBoot集成MyBatis实现SQL拦截器的实战指南

《SpringBoot集成MyBatis实现SQL拦截器的实战指南》这篇文章主要为大家详细介绍了SpringBoot集成MyBatis实现SQL拦截器的相关知识,文中的示例代码讲解详细,有需要的小伙伴... 目录一、为什么需要SQL拦截器?二、MyBATis拦截器基础2.1 核心接口:Interceptor

SpringBoot集成EasyPoi实现Excel模板导出成PDF文件

《SpringBoot集成EasyPoi实现Excel模板导出成PDF文件》在日常工作中,我们经常需要将数据导出成Excel表格或PDF文件,本文将介绍如何在SpringBoot项目中集成EasyPo... 目录前言摘要简介源代码解析应用场景案例优缺点分析类代码方法介绍测试用例小结前言在日常工作中,我们经

基于Python实现简易视频剪辑工具

《基于Python实现简易视频剪辑工具》这篇文章主要为大家详细介绍了如何用Python打造一个功能完备的简易视频剪辑工具,包括视频文件导入与格式转换,基础剪辑操作,音频处理等功能,感兴趣的小伙伴可以了... 目录一、技术选型与环境搭建二、核心功能模块实现1. 视频基础操作2. 音频处理3. 特效与转场三、高

Python实现中文文本处理与分析程序的示例详解

《Python实现中文文本处理与分析程序的示例详解》在当今信息爆炸的时代,文本数据的处理与分析成为了数据科学领域的重要课题,本文将使用Python开发一款基于Python的中文文本处理与分析程序,希望... 目录一、程序概述二、主要功能解析2.1 文件操作2.2 基础分析2.3 高级分析2.4 可视化2.5

Java实现预览与打印功能详解

《Java实现预览与打印功能详解》在Java中,打印功能主要依赖java.awt.print包,该包提供了与打印相关的一些关键类,比如PrinterJob和PageFormat,它们构成... 目录Java 打印系统概述打印预览与设置使用 PageFormat 和 PrinterJob 类设置页面格式与纸张

使用Go实现文件复制的完整流程

《使用Go实现文件复制的完整流程》本案例将实现一个实用的文件操作工具:将一个文件的内容完整复制到另一个文件中,这是文件处理中的常见任务,比如配置文件备份、日志迁移、用户上传文件转存等,文中通过代码示例... 目录案例说明涉及China编程知识点示例代码代码解析示例运行练习扩展小结案例说明我们将通过标准库 os

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟