【转】插入排序（I）Insert Sort

插入排序（I）

直接插入排序

　　直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的有序的表中，从而得到一个新的、记录数增1的有序表。

　　当前元素的前面元素均为有序，要插入时，从当前元素的左边开始往前找（从后往前找），比当前元素大的元素均往右移一个位置，最后把当前元素放在它应该呆的位置就行了。

直接插入排序过程实例

　　比如对 21、25、49、25、16、8这些数排序：

 

                    

直接插入排序分析

　　移动、比较的次数可作为衡量时间复杂性的标准。

　　最优情况：如果原始的输入序列为正序：

　　比较次数：n-1

　　移动次数：0

　　最差情况：如果原始的输入序列为逆序：

　　比较次数：(n+2)(n-1)/2

　　移动次数：(n+4)(n-1)/2

　　所以直接插入排序的时间复杂度为O(n²)。

 

直接插入排序代码

直接插入排序

typedef int ElemType;
//假设记录类型为int，并且记录关键字就是其本身
void InsertSort(ElemType A[], int n)
{
    ElemType x;
    for(int i=1;i<n;++i)
    {
        x=A[i];
        int j=i-1;
        while(A[j]>x)
        {
            A[j+1]=A[j];
            j--;
        }
        A[j+1]=x;
    }
}

 

其他插入排序

　　直接插入排序算法在n比较小的时候很好，但是当n增大了以后就不宜采用直接插入排序。

　　在直接插入排序的基础上，从减少“比较”和“移动”这两种操作的次数着眼，可得到下列插入排序的算法。

折半插入排序

　　由于插入的基本操作是在一个有序的表中进行查找和插入，所以其中这个“查找”操作可以利用折半查找来实现。

　　折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为O(n²)。

2-路插入排序

　　2-路插入排序是在折半插入排序的基础上再改进之，目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。

　　具体做法是：另设一个同类型的数组d，将第一个元素复制过去，将这个第一个元素看做在排好序的序列中处于中间位置的记录（并且一直把它作为此标准），然后把d看做一个循环向量，设置两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。插入元素时，先将当前元素和d[0]比较，如果该元素比d[0]小，则插入到d[0]之前的有序表中，如果比d[0]大，则插入到d[0]之后的有序表中。

　　在2-路插入排序中，移动记录的次数约为n²/8，并且当第一个元素是待排序记录中关键字最小或最大的记录时，2-路插入排序就完全失去了它的优越性。

 

表插入排序

#define SIZE 100  //静态链表容量
typedef struct
{
    Rcd rc;        //记录项
     int next;        //指针项
}SLNode;        //表结点类型
typedef struct
{
    SLNode r[SIZE];    //0号元素为表头结点
    int length;        //链表当前长度
}SLinkListType;        //静态链表类型

 

　　以上述静态链表类型作为待排序记录序列的存储结构，并且，为了插入方便起见，设数组中下标为0的结点为表头结点，并令表头结点记录的关键字为最大整数。

　　则表插入排序的过程描述如下：首先将静态链表中数组下标为1的结点和表头结点构成一个循环链表，然后依次将下标为2至n的结点按记录关键字非递减有序插入到循环链表中。

　　表插入排序的时间复杂度仍是O(n²)。

　　表插入排序的结果只是求得一个有序链表，只能对它进行顺序查找，不能进行随机查找。为了能实现有序表的折半查找，需要对记录进行重新排列。

　　重排记录的做法：顺序扫描有序链表，将链表中第i个结点移动至数组的第i个分量中。