quicksort.txt

quick sort例子

//**************************************
//     
//INCLUDE files for :ANSI/ISO quicksort-
//     compatible shellsort function
//**************************************
//     
/* +++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: ANSI/ISO quicksort-compatible s
//     hellsort function
// Description:Fast, small, qsort()-comp
//     atible Shell sort.
// By: Bob Stout (republished under Open
//     Content License)
//
//This code is copyrighted and has// limited warranties.Please see http://
//     www.1CPlusPlusStreet.com/xq/ASP/txtCodeI
//     d.618/lngWId.3/qx/vb/scripts/ShowCode.ht
//     m//for details.//**************************************
//     

/* +++Date last modified: 05-Jul-1997 */
/*
** ssort() -- Fast, small, qsort()-compatible Shell sort
**
** by Ray Gardner, public domain5/90
*/
#include <stddef.h>
#include "snipsort.h"
void ssort (void *base,
size_t nel,
size_t width,
int (*comp)(const void *, const void *))


    {
    size_t wnel, gap, wgap, i, j, k;
    char *a, *b, tmp;
    wnel = width * nel;
    for (gap = 0; ++gap < nel;)
    gap *= 3;
    while ( gap /= 3 )


        {
        wgap = width * gap;
        for (i = wgap; i < wnel; i += width)


            {
            for (j = i - wgap; ;j -= wgap)


                {
                a = j + (char *)base;
                b = a + wgap;
                if ( (*comp)(a, b) <= 0 )
                break;
                k = width;
                do


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