原来插入排序、希尔排序是这样的

知乎 · · 64 次点击 · · 开始浏览    

Hello,小伙伴们,大家好,我是才辰。


今天和大家一起学习的是排序算法中的插入排序希尔排序。为什么把这两个排序放在一起呢?这是因为这两种排序有一定的关联,希尔排序实际上是对插入排序的一种变形

还是老样子,我先总体上介绍一下算法的过程,接着以一个例子分步讲解,最后给出了详细的代码以及相关分析。

插入排序

插入排序,就和我们平时玩牌是一样的


因为你想,我们在打牌的时候,是不是先把手里的牌由小到大排好,然后每摸到一张牌,就依照大小把它放在排在正确的位置。同样,插入排序也是如此。

步骤:

  1. 首先选取数组第二个元素,若小于数组第一个元素,则插入到第一个位置,否则保持不动;
  2. 接着选取第3个元素,把它和左边第一个元素比较,如果其小于左边第一个元素,则继续与左边第二个元素比较,知道遇到不比它大的元素,然后插入到这个元素右边。
  3. 然后依次选取第4、5、6…n个元素,重复第二个步骤,选择适当的位置插入。

下面以数组arr=[4,3,9,8,1]说明一下

举例说明:
假设arr数组为[4,3,9,8,1].


第一步:选择数组第二个元素3,3<4,将3插入到数组第一个位置;


第二步:9>4,保持不动

第三步:8<9,8>4,将8插入到元素4的后面


第四步:1<9,1<8,1<4,1<3,将1插入到数组第一个位置,至此排序完成


代码(有详细注解):

public class InsertSort{
public static int []InsertSort(int[] arr) {
if(arr.length<=1)
return arr;   
int len=arr.length;   
for(int i=1;i<len;i++)   { 
int t=arr[i];   
//找到插入位置  
int k=i-1;  
while(k>=0&&arr[k]>arr[i])  
        k--;    
//arr[k]之后的元素右移一位     
for(int j=i;j>k+1;j--)  
      {    
        arr[j]=arr[j-1]   
            }   
//插入位置是k+1  
      arr[k+1]=t;  
      } 
return arr;
    } 
  }

性质:

  • 时间复杂度:O(n*n)
  • 空间复杂度:O(1)
  • 是否是稳定排序:是
  • 是否是原地排序:是

希尔排序

对于希尔排序,其实是插入排序的一种变形。



在插入排序中,如果元素的有序程度不高或者数据规模比较大,则需要交换很多次才能到达正确位置。希尔排序通过分组的方式,先使数组局部有序,从而可以减少最后元素交换次数,降低时间复杂度。

希尔排序是采用插入排序的思想,先让数组中任意间隔h的元素有序,接着让数组中任意间隔为h/2的元素有序,接着h/4,h/8…,就这样一直缩小,当h=1时,数组中任意间隔为1的数组都是有序的,即完成了数组的排序。

举例说明:


假设arr=[6,9,4,3,2,7,1,5,0,8]
第一步: 取h=n/2=5,将任意间隔为5的元素分为1组,即以下相同颜色的元素为一组


对每一组元素进行插入排序,得到结果如下:

第二步:取h=n/4=2,即将任意间隔为2的元素归为1组,可分为2组,如下


对每一组元素进行插入排序,得到


由此可以看出,数组已基本有序。

第三步:h=n/8=1,即将数组所有元素进行插入排序,得到最后结果


虽然希尔排序需要进行多趟排序,但在数组元素有序程度不高或者数据规模较大的情况下,仍然要比插入排序要快的多。

【代码】

public class ShellSort {   
public static int[] shellSort(int arr[]) { 
if(arr.length<=1)    
return arr;    
int n=arr.length;
//将数组元素以h为间隔分组,开始时h通常取n/2. 
for(int h=n/2;h>0;h=h/2)     {   
for(int i=h;i<n;i++)  
      {
//对arr[i]进行插入排序      
        insertsort(arr,i,h); 
        }   
      }    
return arr;  
    } 
//arr[i]所在的组为arr[i-2*h]、arr[i-h]、arr[i+h]...   
public static void insertsort(int arr[],int i,int h) {  
int t=arr[i]; 
//空出位置    
for(int k=i-h;k>0&&arr[k]>t;k-=h)     {   
      arr[k+h]=arr[k];    
      } 
//插入    
    arr[k+h]=t;  
    } 
  }

从代码中也可以看出,对各个组进行插入的时候并不是对一组排序完再对另一个组排,而是轮流对每个组进行插入排序。


性质:

  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(1)
  • 是否是稳定排序:否
  • 是否是原地排序:是

这篇文章简单介绍了下插入排序和希尔排序,接下来还会继续写剩下的排序算法。如果有关于文章的任何问题,欢迎加我的微信交流哦。

最后,欢迎关注我的公众号【编程365】,学习更多算法+计算机基础知识。

本文来自:知乎

感谢作者:知乎

查看原文:原来插入排序、希尔排序是这样的

64 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传