插入排序pppt课件.pptVIP

插入排序,by钱小丽,1,理解和熟悉三种排序的基本思想和过程,掌握插入排序算法的时间复杂度、空间复杂度以及稳定性,能根据各种内部排序方法的优缺点及不同场合选择合适的排序方法,学习要点,什么是排序？,什么是排序？,什么是排序？,排序前：,排序后：,排序算法相关说明,直接插入排序,折半插入排序,希尔排序,总结与回顾,目录,7,第1章直接插入排序,8,（一）课程导入,直接插入排序,每次翻新牌时，新牌需要选择合适位置进行插入，从而形成长度增加1的新的有序序列,直接插入排序,（二）基本思想,直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。,直接插入排序,（三）实现步骤,STEP1：从第一个元素开始，该元素可以认为已经被排序；STEP2：取出下一个元素，在已经排序的元素序列中从后向前扫描；STEP3：如果该元素（已排序）大于新元素，将该元素移到下一位置；STEP4：重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；STEP5：重复步骤25。,直接插入排序,（四）算法代码,voidinsertionSort(T*data,intn)/data为待排序数组,n为数组大小Ttemp;for(inti=0;i=0;j-)if(dataj=low;j-)/将需要移动的数组向后移arrayj+1=arrayj;arraylow=temp;/将值插入到指定位置,折半插入排序,（四）性能分析,最坏情况：当待排序序列正好为逆序状态，首先遍历整个序列，之后一个个地将待插入元素放在已排序的序列最前面，之后的所有元素都需要向后移动一位，所以比较和移动的时间复杂度都是O(n)，再加上遍历整个序列的复杂度，总复杂度为O(n2)。,最好情况：在插入第i个元素时，需要经过log2(i)(取下)+1次排序码比较，才能确定应插入的位置。因此总复杂度为O(nlogn)。,平均情况：当被插入的元素放在已排序的序列中间位置时，为平均情况，比较和移动的时间复杂度为O(n/2)，所以总的时间复杂度依然为O(n2)。,稳定性：折半插入排序是一种稳定的排序算法。,空间复杂度：排序只需要一个位置来暂存元素，因此空间复杂度为O(1)。,折半插入排序,（五）折半排序与直接插入排序比较,折半插入排序,思考,理论上来说，折半查找因减少比较次数而提高性能，但是，在查找二分点的时间上的损耗，导致了这个算法并不能比直接插入排序优秀多少，除非你有十分确切的数据大小和随机访问迭代器。,真的能提高性能吗？,不能,第3章希尔排序,22,希尔排序,（一）基本思想,算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。,希尔排序,（二）实现步骤,先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：STEP1：选择一个增量序列t1，t2，tk，其中titj，tk=1；STEP2：按增量序列个数k，对序列进行k趟排序；STEP3：每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。,希尔排序,（三）算法代码,voidshell_sort(T*a,intn,intgap)/a为待排序数组，n为数组长度，gap为增量Ttemp;while(gap-0)for(inti=0;i=0,希尔排序,希尔排序,（四）性能分析,时间复杂度：希尔排序的时间复杂度与增量选取有关，计算起来较为复杂至今未能给出算法的时间复杂度的下界。,稳定性：希尔排序是进行多次直接插入排序的算法，由于多次插入排序，虽然每一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。,空间复杂度：希尔排序是对直接插入排序的优化，它的原理是加大插入排序中元素的间隔，并在这些有间隔的元素中进行插入排序，从而使数据进行大幅度的移动，当进行过依次排序后，再减小间隔再一次进行插入排序，直到间隔缩小为1。这样做的目的可以使得最后排序时整个序列基本有序，而无需再进行过多的元素比较和移动次数，在这个过程中也只