十大经典排序算法-希尔排序,归并排序,快速排序
前言
这是十大经典排序算法详解的第二篇,这是之前第一篇文章的链接:十大经典排序算法详解(一)冒泡排序,选择排序,插入排序,没有看过的小伙伴可以看一下.
每次讲解都是先采用文字的方式帮助大家先熟悉一下算法的基本思想,之后我会在通过图片的方式来帮助大家分析排序算法的动态执行过程,这样就能够帮助大家更好的理解算法.
每次的图画起来都比较的繁琐,真的很耗费时间.所以如果你觉得文章写得还可以或者说对你有帮助的话,你可以选择一键三连,或者选择关注我的公众号:萌萌哒的瓤瓤 ,这对我真的很重要.UP在此谢谢各位了.
废话不多说了,下面开始我们的正文部分吧!!!
1-希尔排序
算法思想:
其实希尔排序的思想很简单,因为希尔排序的基本思想就是第一篇中间讲解的关于插入排序的基本思想,只是希尔排序相比较与插入排序多加了一步就是确定步长.之前在插入排序的过程中,我们的步长是固定的即为1,在希尔排序中我们的步长是不固定的,一开始数组长度的一半,之后每次分组排序之后步长就再减半,直到步长到1为止.这时候我们的排序就已经完成了.
说完了,那我们接下来还是通过图解的方式来帮助大家更好的理解希尔排序吧:
看完上面的图之后相信大家就基本了解希尔排序算法的思想了,那么接下来我们还是来分析一下希尔排序算法的特点吧:
希尔排序算法是不稳定的,这里大家可能会产生这样的疑问,本身希尔排序算法的本质就是插入排序,只不过是多了一步确定步长的过程,为什么插入排序就是稳定的,但是希尔排序缺失不稳定的呢?其实重点就是在分组之后,大家都知道在一个分组里面进行一次插入排序肯定是稳定的,关键就在于希尔排序的过程中会出现多次分组,那么就会出现在之前的分组里面是稳定的,但是到下一次分组的时候就会出现不稳定的情况.
说这么多还不如直接来个例子给大家看一下,大家就知道了:
希尔排序是 第一个 在时间复杂度上突破O(N*N)的算法,这一点是非常有意义的.时间复杂度仅为O(N*log N)
算法图解:
示例代码:
按照算法思想不改动的版本:
public static void main(String[] args) { int []num ={7,4,9,3,2,1,8,6,5,10}; long startTime=System.currentTimeMillis(); //规定步长 for(int step=num.length/2;step>0;step/=2) { System.out.println("步长为"+step+"的分组排序:"); //步长确定之后就需要分批次的对分组进行插入排序 for(int l=0;l<step;l++) { //插入排序的代码 for(int i=l+step;i<num.length;i+=step) { int temp=num[i]; int j=i; while(j>0&&temp<num[j-step]) { num[j]=num[j-step]; j-=step; //这里需要注意一点就是j-step可能会越界,所以我们需要继续进行判断 //之前在插入排序中,步长始终是1,所以在while循环那里就会阻断,但是现在步长会发生变化 //所以我们需要在这里提前进行判断,否则金辉发生数组越界的情况 if(j-step<0) break; } if(j!=i) { num[j]=temp; } } System.out.println(" "+l+"号分组排序:"); for(int k=0;k<num.length;k++) System.out.print(num[k]+" "); System.out.println(); } System.out.println(); } long endTime=System.currentTimeMillis(); System.out.println("程序运行时间： "+(endTime-startTime)+"ms"); }
但是大家会发现如果真的按照希尔排序的思想这样做得的话,我们会发现用了三层for循环,那么很显然时间复杂度就会达到我们目前遇到的最坏的情况即O(N*N*N),所以我们需要进行改进,主要就是改进分组排序的过程,之前我们是确定完步长之后,就通过for循环进行循环分组的排序,这里我们修改成直接和下一个for循环一起,直接进行循环分组
改进后的代码:
public static void main(String[] args) { int []num ={7,4,9,3,2,1,8,6,5,10}; long startTime=System.currentTimeMillis(); for(int step=num.length/2;step>0;step/=2) { System.out.println("步长为"+step+"的分组排序:"); System.out.println("循环分组排序:"); for(int j=step;j<num.length;j++) { int temp=num[j]; int k=j; while(k-step>=0&&temp<num[k-step]) { num[k]=num[k-step]; k-=step; } num[k]=temp; for(int l=0;l<num.length;l++) System.out.print(num[l]+" "); System.out.println(); } } long endTime=System.currentTimeMillis(); System.out.println("程序运行时间： "+(endTime-startTime)+"ms"); }
改进之后的算法之使用了两层for循环,真的让时间复杂度达到了O(N*log N)
复杂度分析:
理解完希尔排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.
时间复杂度
希尔排序的时间复杂度在各情况下,主要就取决于元素的个数以及分组的次数,我们分析得到分组的次数刚好就是log N,所以我们可以得到希尔排序的时间复杂度仅为O(N*log N)
空间复杂度
这个我们可以看到我们整个排序的过程中只增加一个存储Key的位置,所以希尔排序的空间复杂是常量级别的仅为O(1).
