3.2-选择排序
算法思想:
选择排序的重点就是选择,选择的方式就是每次循环选出最小的元素,然后将最小的元素与排序序列中的队头元素进行置换.还是老样子,通过下面的图来让大家更好的理解这一个选择的过程:
这是我们基本就能理解选择排序的基本概念.这里我们需要和上面的冒泡排序区分一点的就是,选择排序在比较结束之后并不会直接交换两个元素的位置,只是记录当前序列中的最小元素 ,当找到最小的元素之后,在将该最小元素与队头的元素进行置换.
了解完这些之后,我们也来稍微说一下选择排序的特点:
每次循环必定能够确定一个元素的最终位置,这一点和冒泡排序是一样的
选择排序也是不稳定的,这里大家可能会不理解,还是老样子我们还是通过下面的图来掩饰一下大家就懂了:
算法图解:
示例代码:
public static void main(String[] args) { int []num ={7,4,9,3,2,1,8,6,5,10}; long startTime=System.currentTimeMillis(); for(int i=0;i<num.length-1;i++) { int min=i; for(int j=i+1;j<num.length;j++) { if(num[min]>num[j]) { min=j; } } if(i!=min) { int temp=num[i]; num[i]=num[min]; num[min]=temp; } System.out.print("第"+(i+1)+"次排序结果:"); for(int j=0;j<num.length;j++) System.out.print(num[j]+" "); System.out.println(); } long endTime=System.currentTimeMillis(); System.out.println("程序运行时间： "+(endTime-startTime)+"ms"); }
复杂度分析:
理解完选择排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.
时间复杂度
时间复杂度我们从两个方面来评判
平均情况
平均情况下我们的算法复杂度主要就是在进行元素的比较的过程.即进 if(num[min]>num[j])的过程,这个过程平均下来就是我们两层for循环的次数,这个我们计算一下就能得出是n*(n-1)/2,我们去最大的次数,可以看到时间复杂度就是O(n*n)
最坏情况
最坏情况本质上和我们的平均情况是一样的,因为不管是平均情况还是最坏情况,都是只在最后置换最小元素与队头元素的位置,比较的次数也是一样的,所以这样算下来时间复杂度也是O(n*n)
空间复杂度
这个我们也可以看到我们整个排序的过程中值增加了两个个空间,这个空间就是我们定义的temp和min,所以选择排序的空间复杂度也是常量级别的即为O(1)
3.3-插入排序
算法思想:
插入排序的算法思想则是将整个序列划分成两段,一段时已经排序完成的序列,另一端序列则是仍然无需的状态.就比方下图所示:
分成这样两个序列之后,插入序列每次都是挑选待排序序列的队头元素插入到已有序的序列之中,从有序序列的队尾开始比较,如果比该元素大的话,将该元素后移,一旦出现小于该元素的元素,插入当前的位置.这个就是插入排序名字的由来.
说了半天大家可能还是不太了解,还是通过下面的图来详细讲解一下该算法的执行过程吧:
理解完插入排序算法的基本思想之后我们再来看看该算法的特点:
这个其实不算特点,只是和上述两个算法对比之后,大家可以发现该算法不像上面的冒泡与选择排序一样,每次循环排序都能确定一个元素的最终位置.插入排序每次循环排序之后是不能够唯一确定一个元素的最终位置的.他只能是每次循环之后确定一些元素的相对位置.
插入排序和冒泡排序一样也有一个极端的排序情况,但是冒泡排序的极端情况是最惨的情况,但是插入排序的极端情况就是最爽的情况.就是在序列已经基本有序的时候,插入排序是最快的,时间复杂度可以达到O(n)即线性级别.因为一旦序列有序之后,for循环仍然需要执行,但是在while循环里面就根本不用执行了,这就是插入排序能够达到线性级别的关键.对比冒泡和选择排序,他们都是通过两层for循环进行的,但是插入排序的第二层循环是通过while并且有相应的终止条件,这就使得插入排序的性能比上面两者会相对好一点.当然了,这种情况只存在于序列已经基本有序的情况.
算法图解:
示例代码:
public static void main(String[] args) { int []num ={7,4,9,3,2,1,8,6,5,10}; long startTime=System.currentTimeMillis(); for(int i=1;i<num.length;i++) { int temp=num[i]; int j=i; while(j>0&&temp<num[j-1]) { num[j]=num[j-1]; j--; } if(j!=i) { num[j]=temp; } System.out.print("第"+i+"次排序结果:"); for(int k=0;k<num.length;k++) System.out.print(num[k]+" "); System.out.println(); } long endTime=System.currentTimeMillis(); System.out.println("程序运行时间： "+(endTime-startTime)+"ms"); }
复杂度分析:
理解完插入排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.
时间复杂度
时间复杂度我们从三个方面来评判,这里就必须要提一下我们上面所说的极端情况了
最佳情况
时间复杂度能够达到线性级别O(n)
平均情况
平均情况下我们的算法复杂度主要就是在进行元素的比较的过程.即进 temp<num[j-1]的过程,这个过程平均下来就是我们一层for循环的次数以及一层while循环,这个我们计算一下就能得出是n*(n-1)/2,我们去最大的次数,可以看到时间复杂度就是O(n*n)
最坏情况
最坏情况本质上和我们的平均情况是一样的,因为不管是平均情况还是最坏情况,都是只比较的次数也是一样的,所以这样算下来时间复杂度也是O(n*n)
空间复杂度
这个我们也可以看到我们整个排序的过程中值增加了两个个空间,这个空间就是我们定义的temp和j,所以选择排序的空间复杂度也是常量级别的即为O(1)
