插入排序课件

1、by,钱小丽,1,排序前：,排序后：,7,8,每次翻新牌时，新牌需要选择合适位置进行插入，从而形成,长度增加,1,的新的有序序列,直接插入排序基本思想是每一步将一个待排,序的记录，插入到前面已经排好序的有序序,列中去，直到插完所有元素为止。,STEP1,：从第一个元素开始，该元素可以认为已,经被排序；,STEP2,：取出下一个元素，在已经排序的元素序,列中从后向前扫描；,STEP3,：如果该元素（已排序）大于新元素，将,该元素移到下一位置；,STEP4,：重复步骤,3,，直到找到已排序的元素小,于或者等于新元素的位置；,将新元素插入到该位置后；,STEP5,：重复步骤,25,。,void in

2、sertionSort(T* data,int n) ,/data,为待排序数组,n,为数,组大小,T temp;,for (int i = 0; i n; i+),for (int j = i; j = 0; j-) ,if (dataj dataj - 1) ,temp = dataj;,dataj = dataj - 1;,dataj - 1 = temp;,最坏情况：,当待排序序列正好为逆序状态，首先遍历整个序列，之后一个个地将待插入元素放在已排,序的序列最前面，之后的所有元素都需要向后移动一位，所以比较和移动的时间复杂度都是,O(n),，再,加上遍历整个序列的复杂度，总复杂度为,O(

3、n2),。,最好情况：,当待排序序列正好为正序状态，则遍历完整个序列，当插入元素时，只比较一次就够了，,所以时间复杂度为,O(n),。,平均情况：,当被插入的元素放在已排序的序列中间位置时，为平均情况，比较和移动的时间复杂度为,O(n/2),，所以总的时间复杂度依然为,O(n2),。,稳定性,：,插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序,的小序列只有,1,个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已,经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置,。如果碰见一个和插入元素相等的，

4、那么插入元素把想插入的元素放在相等元素的后面。所以，相等元,素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。,15,折半插入算法是对直接插入排序算法的改进，,排序原理同直接插入算法：,把,n,个待排序的元素看成一个有序表和一个,无序表，开始时有序表中只有一个元素，无序,表中有,n-1,个元素；排序过程即每次从无序表中,取出第一个元素，将它插入到有序表中，使之,成为新的有序表，重复,n-1,次完成整个排序过程,。,与直接插入算法的区别在于：在有序表中,寻找待排序数据的正确位置时，使用了折半查,找,/,二分查找。,STEP1,：将待排序序列的第一个元素看做一个

5、有,序序列，把第二个元素到最后一个元素当成是未,排序序列。,STEP2,：从头到尾依次扫描未排序序列，将扫描,到的每个元素插入有序序列的适当位置，在查找,元素的适当位置时，采用了折半查找方法。（如,果待插入的元素与有序序列中的某个元素相等，,则将待插入元素插入到相等元素的后面。,void BinaryInsertSort(T* array, int n) /array,为待排序数组,n,为数组大小,int i, j, mid, low, high;,T temp;,for (i = 1; i n; i+),temp = arrayi; /,把第,i+1,个元素赋值给,temp(,数组从下标,0

6、,开始,),low = 0; /,初始化,low,，,arraylow,代表数组中第,1,个元素,high = i; /,初始化,high,，,arrayhigh,代表已插入的最后一个元,素,while (low = high) /,不断的折半,1/2 1/4 .,mid = (low + high) / 2; /,计算中间位置,if (temp arraymid) /,插入值大于中间值,low = mid + 1;,else /,插入值小于中间值,high = mid - 1;,for (j = i - 1; j = low; j-) /,将需要移动的数组向后移,arrayj + 1 = a

7、rrayj;,arraylow = temp;,/,将值插入到指定位置,最坏情况：,当待排序序列正好为逆序状态，首先遍历整个序列，之后一个个地将待插入元素放在已排,序的序列最前面，之后的所有元素都需要向后移动一位，所以比较和移动的时间复杂度都是,O(n),，再,加上遍历整个序列的复杂度，总复杂度为,O(n2),。,最好情况：,在插入第,i,个元素时，需要经过,log2(i)(,取下,)+1,次排序码比较，才能确定应插入的位置。,因此总复杂度为,O(nlogn),。,平均情况：,当被插入的元素放在已排序的序列中间位置时，为平均情况，比较和移动的时间复杂度为,O(n/2),，所以总的时间复杂度依然

8、为,O(n2),。,稳定性,：,折半插入排序是一种稳定的排序算法。,空间复杂度：,排序只需要一个位置来暂存元素，因此空间复杂度为,O(1),。,折半搜索比顺序搜索快，所以折半插入排序就平均性能而,言比直接插入排序要快。,它所需要的排序码比较次数与待排序元素的序列无关，仅,依赖于元素的个数。,当,n,较大时，折半插入排序算法比较次数比直接插入排序,要好得多，但是比最好的情况的话，直接插入排序要好得多（,此时直接插入排序只比较,1,次,),。,在元素的初始序列已经排好序或者接近排好序时，直接插,入排序比折半插入排序算法执行的排序码比较次数要少。,折半插入排序的元素移动次数与直接插入排序移动的次数,

9、相同，依赖于元素的初始排列。折半插入排序是一种稳定的排,序算法。,理论上来说，折半查找因减少比较次数而,提高性能，但是，在查找二分点的时间上,的损耗，导致了这个算法并不能比直接插,入排序优秀多少，除非你有十分确切的数,据大小和随机访问迭代器。,不能,22,算法先将要排序的一组数按某个增量,d,（,n/2,n,为,要排序数的个数）分成若干组，每组中记录的下,标相差,d.,对每组中全部元素进行直接插入排序，,然后再用一个较小的增量（,d/2,）对它进行分组,，在每组中再进行直接插入排序。当增量减到,1,时，进行直接插入排序后，排序完成。,先将整个待排序的记录序列分割成为若干子序,列分别进行直接插入

10、排序，具体算法描述：,STEP1,：选择一个增量序列,t1,，,t2,，,tk,，,其中,titj,，,tk=1,；,STEP2,：按增量序列个数,k,，对序列进行,k,趟排,序；,STEP3,：每趟排序，根据对应的增量,ti,，将待,排序列分割成若干长度为,m,的子序列，分别对,各子表进行直接插入排序。仅增量因子为,1,时，,整个序列作为一个表来处理，表长度即为整个,序列的长度。,void shell_sort(T* a, int n , int gap),/a,为待排序数组，,n,为数组长度，,gap,为增量,T temp;,while(gap-0),for(int i=0; igap;

11、i+),for(int j = i+gap; jn; j=j+gap),if(ajaj-gap),temp = aj;,int k = j-gap;,while(k=0,k = k-gap;,ak+gap = temp;,时间复杂度：,希尔排序的时间复杂度与增量选取有关，计算起来较为复杂至今未能给出算法的时间复,杂度的下界。,稳定性,：,希尔排序是进行多次直接插入排序的算法，由于多次插入排序，虽然每一次插入排序是稳定,的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中,移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。,空间复杂度：,希尔排序是对直接插入排序的优化，它的原理是加大插入排序中元素的间隔，并在这些有,间隔的元素中进行插入排序，从而使数据进行大幅度的移动，当进行过依次排序后，再减小间隔再一次,进行插入排序，直到间隔缩小为,1,。这样做的目的可以使得最后排序时整个序列基本有序，而无需再进,行过多的元素比较和移动次数，在这个过程中也只需