内部排序—直接插入排序

Dear 丶 2022-06-15 11:49 172阅读 0赞

直接插入排序是一种简单的排序方法，具体做法是：在插入第i个记录时，R1、R2…Ri-1已经排好序，这时候将Ri的关键字Ki依次与关键字Ki-1、Ki-2等进行比较，从而找到应该插入的位置并将Ri插入，插入位置及其后的记录依次向后移动。  
直接插入排序法在最好的情况下（待排序列已按照关键码有序）每趟排序只需要做1次比较而且不需要移动元素，因此n个元素排序时的总比较次数为n-1次，总的移动次数为0次。在最坏的情况下（元素已经逆序排序），在进行第j趟排序时，待插入的记录需要和前面的每个记录进行比较，比较次数为j(设置监视哨时，包括与监视哨的一次比较)或j-1（不设置监视哨），移动次数为j+1。 直接插入排序时一种稳定的排序算法，时间复杂度为O(n2)。在排序过程中仅需要一个元辅助空间，空间复杂度为O(1)。

///  /// 直接插入排序 不带哨兵排序 /// 思想：默认认为第一个是有序的，从待排序的数组中依次取一个元素和已排序的比较 /// 
    /// 待排序数组
    /// 
      
    private int[] InsertSort(int[] arrData)
    {
        int temp=0;
        //从第二个元素开始循环
        for(int i=1;i
      
       =0 && temp
       
        arrData[0];j--)     
                {  
                    arrData[j+1]=arrData[j];  
                }  
                arrData[j]=arrData[0]; 
            }
        }  
        return arrData;
    }

带哨兵的插入排序中的哨兵元素有两个作用：  
1、暂时存放待插入的元素  
2、防止数组下标越界，当待插入的元素小于已排序的子数组中的最小元素时，j=-1,越界，而采用哨兵，arrData\[0\] < arrData\[j\],当j=0时，就结束循环，不会出现越界（for循环只有一次判断，提高了效率）。  
但是带哨兵的插入排序存在一个问题：  
有方法传进来的数组时原始数组，则插入第一个元素时，a\[0\]会被覆盖，造成最终排完序的数组缺少了原始数组的第一个元素（bug）。  
如何消除此bug:  
1、在调用此方法之前，将数组做下处理，使其右移一个元素的位置，空出来的第0个元素初始化为0（或不做初始化）  
2、在调用方法时，做上述处理  
无哨兵的插入排序，无上述问题，但在效率上会稍低，for循环中有两个判断条件。