插入排序 C实现

1 year ago

source link: http://bean-li.github.io/insertsort/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

插入排序 C实现

首页分类标签留言关于订阅 2023-06-10

分类算法

标签算法

复习《算法：C语言实现》一书，本文实现了插入排序。插入排序的思路和人打牌的时候，摸牌，把新摸到的牌插入到指定位置很相似。

#ifndef _SORT_BASE_H_
#define _SORT_BASE_H_

typedef int Item ;

#define Key(A) (A)
#define less(A,B) (Key(A) < Key(B))
#define exch(A,B) { Item tmp = A; A=B ; B=tmp;}
#define compexch(A, B) if(less(B, A)) exch(A,B)


#endif

#ifndef _INSERTSORT_H
#define _INSERTSORT_H

#include "sort_base.h"

void insertsort_slow(Item a[], int l , int r)
{
    int i ,j ;
    for(i = l+1 ; i <=r ; i++)
        for(j = i; j > l; j--)
            compexch(a[j-1], a[j]);
}

void insertsort(Item a[], int l,  int r)
{
    int i ;

    //put minimal value to the leftmost position , as sentinel key
    for(i = r ; i  > l; i--)
        compexch(a[i-1], a[i]);

    for( i = l+2 ; i <=r ; i++)
    {
        int j = i ;
        Item v = a[i] ;

        /* no need add j-1 >= l condition, because a[0] is alreaay the most minimal value already*/
        /* use while for break immediately to skip useless compare*/
        while(less(v, a[j-1]))
        {
            a[j] = a[j-1] ;
            j-- ;
        }
        a[j] = v ;
    }
}

#endif

insertsort_slow 这个版本，更容易理解，但是效率不高。

内层循环是从右往左比较，而左边的子序列实际上已经是有序的了，当碰到关键字不大于整备插入的数据项的关键字的时候，其实没有继续比较了，缺少了break机制，增加了无谓的比较。
j > l 这个比较，大部分情况下是无用的，只有要插入的元素是最小的并且要插入数组的最前端的时候，该条件才有真正的意义。通常的一个改进思路是把最小的元素放在a[0] ,作为哨兵，只需要对a[1]~a[N]的元素进行排序即可。这种改进思路，可以大面积减少比较。

通过上述思路分析，将insertsort改进成最终的版本。

Recommend

blog.51cto.com 6 years ago
Cache

java插入排序-锦瑟无端五十弦-51CTO博客

插入排序的思想就和玩扑克是的摸牌一样，摸到一张牌放手上，再摸一张和之前的比较，大的就放后面，小的就放前面。一个数列我们把它分为两个区，一个是已经排序的区，一个是乱序区，选取第一个元素出来作为排序区的元素，然后从第二个元素开始往后作为乱序区，从第...

studygolang.com 4 years ago
Cache

从插入排序来理解 Go 的接口

根据插入排序的思想，我们很容易就可以完成插入排序的代码如下。 func insertionSort(data []int) { lo, hi := 0, len(data) - 1 for i := lo + 1; i < hi; i++ { for j := i; j > lo && data[j...