[排序算法]图解插入排序–直接插入排序

本文:http://www.paymoon.com:8001/index.php/2016/11/03/insertsort/

排序思路:每次将一个待排序的元素与已排序的元素进行逐一比较,直到找到合适的位置按大小插入。

第一趟比较示图:

算法实现:

结果:

算法分析:1.当元素的初始序列为正序时,仅外循环要进行n-1趟排序且每一趟只进行一次比较,没有进入if语句不存在元素之间的交换(移动)。此时比较次数(Cmin)和移动次数(Mmin)达到                  最小值。

                 Cmin = n-1    Mmin = 0;

                此时时间复杂度为O(n)。

              2.当元素的初始序列为反序时,每趟排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移(arr[j+1] = arr[j]),i个元素后移移动次数当然也就为i                    了,再加上temp = arr[i]与arr[j+1] = temp的两次移动,每趟移动的次数为i+2,此时比较次数(Cmin)和移动次数(Mmin)达到最小值。

                 Cmax = 1+2+…+(n-1) = n*(n-1)/2 = O(n2)

                 Mmax = (1+2)+(2+2)+…+(n-1+2) = (n-1)*(n+4)/2 = O(n2)  (i取值范围1~n-1)

                 此时时间复杂度为O(n2)。

              3.在直接插入排序中只使用了i,j,temp这3个辅助元素,与问题规模无关,所以空间复杂度为O(1).

              4.在整个排序结束后,即使有相同元素它们的相对位置也没有发生变化,

                  如:5,3,2,3排序过程如下

                     A–3,5,2,3

                     B–2,3,5,3

                     C–2,3,3,5

                   排序结束后两个元素3的相对位置没有发生改变,所以直接插入排序是一种稳定排序

原文:http://www.cnblogs.com/MOBIN/p/4679208.html

本文:http://www.paymoon.com:8001/index.php/2016/11/03/insertsort/

2 thoughts on “[排序算法]图解插入排序–直接插入排序

发表评论

电子邮件地址不会被公开。