insertionsort2.txt

insertion排序

//**************************************
//     
//INCLUDE files for :Insertion sort func
//     tion
//**************************************
//     
/* +++Date last modified: 05-Jul-1997 */
/*
** Header file for SNIPPETS sorting functions
*/
#ifndef SNIPSORT__H
#define SNIPSORT__H
#include <stddef.h>
#include "dirport.h"
/*
** Prototypes
*/
#ifdef __STDC__
#define strsort _strsort
#endif
void hugesort(void HUGE *basep, unsigned nel,
unsigned width,
int (*comp)(void HUGE *, void HUGE *)); /* Hugesort.C */
void*sortl(void *list, void *(*getnext)(void *),
void (*setnext)(void *, void *),
int (*compare)(void *, void *)); /* Ll_Qsort.C */
void isort(void *base, size_t nmemb, size_t size,
int (*comp)(const void *, const void *));/* Rg_Isort.C */
void qsort(void *, size_t, size_t,
int (*)(const void *, const void *));/* Rg_Qsort.C */
void swap_chars(char *, char *, size_t); /* Rg_Qsort.C */
void quicksort(int v[], unsigned n); /* Rgiqsort.C */
void ssort (void *base, size_t nel, size_t width,
int (*comp)(const void *, const void *));/* Rg_Ssort.C */
void strsort(char **v, unsigned n);/* Strsort.C */
/*
** File: LL_MSORT.C
*/


    typedef struct list_struct {
    struct list_struct *next;
    char *key;
    /* other stuff */
} list;
list *lsort (list *p);
#endif /* SNIPSORT__H */
 
//**************************************
//     
// Name: Insertion sort function
// Description:isort() -- insertion sort
//     by Raymond Gardner. qsort() compatible, 
//     but uses insertion sort algorithm.
// By: Bob Stout (republished under Open
//     Content License)
//

/* +++Date last modified: 05-Jul-1997 */
/*
** isort() -- insertion sort
**
** Raymond Gardnerpublic domain2/93
**
** qsort() compatible, but uses insertion sort algorithm.
*/
#include <stddef.h> /* for size_t definition */
#include "snipsort.h"
void isort(void *base, size_t nmemb, size_t size,
int (*comp)(const void *, const void *))


    {
    char *i, *j, *lim;
    lim = (char *)base + nmemb * size;/* pointer past end of array */
    for ( j = (char *)base, i = j+size; i < lim; j = i, i += size )


        {
        for ( ; comp((void *)j, (void *)(j+size)) > 0; j -= size )


            {
            char *a, *b;
            char tmp;
            size_t k = size;
            a = j;
            b = a + size;
            do


                {
                tmp = *a;
                *a++ = *b;
                *b++ = tmp;
            } while ( --k );
            if ( j == (char *)base )
            break;
        }
    }
}