您的位置:首页 > 编程学习 > C# > 正文

C#插入排序

更多 时间:2014-8-10 类别:编程学习 浏览量:715

C#插入排序

C#插入排序

一、插入排序的种类

 

包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)。属于稳定排序的一种(通俗地讲,就是两个相等的数不会交换位置) 。

 

二、插入排序算法原理

 

插入即表示将一个新的数据插入到一个有序数组中,并继续保持有序。例如有一个长度为N的无序数组,进行N-1次的插入即能完成排序

第一次,数组第1个数认为是有序的数组,将数组第二个元素插入仅有1个有序的数组中;

第二次,数组前两个元素组成有序的数组,将数组第三个元素插入由两个元素构成的有序数组中.....

第N-1次,数组前N-1个元素组成有序的数组,将数组的第N个元素插入由N-1个元素构成的有序数组中,则完成了整个插入排序。

 

三、算法分析

 

平均时间复杂度:O(n2)

空间复杂度:O(1)  (用于记录需要插入的数据)

 

四、插入排序稳定性

 

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素

比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。

所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

 

五、C#插入排序算法

 

  • C# 代码   复制
  •  
  • 
     
              /// <summary>
            /// 插入排序(升序)
            /// </summary>
            public static int[] InsertionSort(int[] needSortArray)
            {
                for (int i = 1; i < needSortArray.Length; i++)
                {
                    int key = needSortArray[i];// 相当于[当前牌],这里赋给key起临时保存的作用
    
                    // 将当前牌与手中的牌依次比较
                    int j = i - 1;
                    while (j >= 0 && key < needSortArray[j])
                    {
                        // 将元素后移
                        needSortArray[j + 1] = needSortArray[j];
                        j--;
                    }
    
                    // j+1(因为上边的while循环多做了一次判断)即为当前牌插入的位置
                    needSortArray[j + 1] = key;
                }
    
                return needSortArray;
            }
    
    		
  •  

    六、插入排序算法实例

     

    以下面5个无序的数据为例:

     

    65 27 59 64 58

    第1次插入: 27 65 59 64 58

    第2次插入: 27 59 65 64 58

    第3次插入: 27 59 64 65 58

    第4次插入: 27 58 59 64 65

     

    七、算法优化

     

    插入排序中,总是先寻找插入位置,然后在实行挪动和插入过程;寻找插入位置采用顺序查找的方式(从前向后或者从后向前),既然需要插入的数组已经是有序的,那么可以采用二分查找方法来寻找插入位置,提高算法效率,但算法的时间复杂度仍为O(n2)。

     

  •  
  • C# 代码   复制
  •  
  • 
      //查找数值iData在长度为iLen的pDataArray数组中的插入位置
    int FindInsertIndex(int *pDataArray, int iLen, int iData)
    {
        int iBegin = 0;
        int iEnd = iLen - 1;
        int index = -1;    //记录插入位置
        while (iBegin <= iEnd)
        {
            index = (iBegin + iEnd) / 2;
            if (pDataArray[index] > iData)
                iEnd = index - 1;
            else
                iBegin = index + 1; 
        }
        if (pDataArray[index] <= iData)
            index++;
        return index;
    }
    
    /********************************************************
    *函数名称:BinaryInsertSort
    *参数说明:pDataArray 无序数组;
    *           iDataNum为无序数据个数
    *说明:    二分查找插入排序
    *********************************************************/
    void BinaryInsertSort(int* pDataArray, int iDataNum)
    {
        for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入
        {
            int index = FindInsertIndex(pDataArray, i, pDataArray[i]);    //二分寻找插入的位置
            
            if (i != index)    //插入位置不为i,才挪动、插入
            {
                int j = i;
                int temp = pDataArray[i];
                while (j > index)    //挪动位置
                {
                    pDataArray[j] = pDataArray[j-1];
                    j--;
                }
                pDataArray[j] = temp;    //插入
            }
        }
    }
    
    		
  •  

    标签:排序
    您可能感兴趣