当前位置：首页 > news >正文

插入类排序

news 来源：原创 2024/4/28 16:27:50

2019独角兽企业重金招聘Python工程师标准>>>

插入类排序的基本思路是在一个已经排好序的子记录上，每一步将下一个待排序的记录插入到已经排好序的记录子集中，直到将所有待排序记录全部插入为止。

1.直接插入排序

直接插入排序是最基本的插入排序算法，它的一趟操作是将第i个记录插入到前面i-1个已经排好序的记录中，在查找记录i的插入位置时，也在进行元素的移动。假设有一个待排序队列r[1,length]，则整个排序过程需要n-1次趟。直接插入算法的实现如下：

 
    1void insSort(int *r, int length)

    2{

    3    int i, j;

    4 

    5    printf("Sorting:\n");

    6    for ( i = 2; i <= length; i++) {

    7        r[0] = r[i];

    8        j = i - 1;

    9 

    10        while (r[0] < r[j]) {

    11            r[j + 1] = r[j];

    12            j--;

    13        }

    14 

    15        r[j + 1] = r[0];

    16 

    17        output(r, length);

    18    }

    19}

具体实现时，用一维数组来存储待排序的序列，其中0号元素备份待插入的记录。

2.折半插入排序

折半插入排序法与直接插入法类似，区别在于确定元素i插入的位置时利用折半查找法。每一趟排序的过程是先用折半查找法确定插入位置，再逐个进行元素的移动。

 
    1void binSort(int *r, int length)

    2{

    3    int i, j;

    4    int low ,high, mid;

    5 

    6    printf("Sorting:\n");

    7    for ( i = 2; i <= length; i++) {

    8        r[0] = r[i];

    9        low = 1;

    10        high = i - 1;

    11 

    12        while (low <= high) {

    13            mid = (low + high) / 2;

    14            if (r[0] < r[mid])

    15                high = mid - 1;

    16            else

    17                low = mid + 1;

    18        }

    19 

    20        for (j = i - 1; j >= low; j--) 

    21            r[j + 1] = r[j];

    22        r[high + 1] = r[0];

    23        output(r, length);

    24 

    25    }

    26}

与直接插入法类似，数组r中的0号元素也备份了待插入的元素i。当确定了记录i的位置时，此时存在low=high+1这样的关系，接下来将low到i-1之间的元素都后移一位，最终记录i刚好插入空出来的位置中。

3.希尔排序

整个希尔排序的过程由若干次希尔插入组成，具体次数由增量数组delta中的元素个数n确定。在每一次的希尔插入算法中，将待排序的记录序列分成d 个稀疏子序列，每个稀疏子序列中元素之间的间隔正好为d。希尔插入算法就是将每一个子序列都按照直接插入法排列成有序，从而使得整个序列基本有序。上述过程会重复n次，就是希尔排序算法的整个过程。

 
    1void shellSort(int *r, int length, int *delta, int n)

    2{

    3    int i;

    4    for ( i = 0; i < n; i++) {

    5        shellInsert(r, length, delta[i]);

    6    }

    7}

第i趟希尔排序中，每个稀疏子序列中元素的间隔由delta[i]决定。但希尔算法的最后一趟排序，元素的间隔必需是1。因为最后一次希尔排序就相当于直接插入排序，但是此时整个记录序列已经几乎有序，因此移动的次数会大大减少。

 
    1void shellInsert(int *r, int length, int d)

    2{

    3    int i, j;

    4    int k;

    5     

    6    for (i = 1 + d; i <= length; i++) {

    7        if (r[i] < r[i - d]) {

    8            r[0] = r[i];

    9             

    10            for (j = i - d; j > 0 && r[0] < r[j]; j -= d) {

    11                r[j + d] = r[j];

    12            }

    13            r[j + d] = r[0];

    14        }

    15    }

    16    output(r, length);

    17}

虽然希尔插入算法中需要依次将d个子序列排成有序，但是实际的实现过程却从第一个子序列的第二个记录(d+1)开始依次遍历整个序列，因为每个序列中的元素都是由间隔d控制的，因此就相当于每个子序列各自排序。内部的for循环相当于对每个子序列进行直接插入排序，从当前的记录i(保存在r[0] 中)开始，依次扫描当前子序列之前的元素(每个元素的间隔为d，因此每次循环j都减少d)以确保插入何时的位置。

转载于:https://my.oschina.net/u/174242/blog/72942