rec_qsort.txt

使用递归实现的快速排序法

//**************************************
//     
//INCLUDE files for :Recursive ANSI/ISO 
//     quicksort 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: Recursive ANSI/ISO quicksort fu
//     nction
// Description:Quicksort integer array b
//     y Raymond Gardner.
// By: Bob Stout (republished under Open
//     Content License)
//

/* +++Date last modified: 05-Jul-1997 */
/*
** quicksort.c -- quicksort integer array
**
** public domain by Raymond Gardner 12/91
*/
#include "snipsort.h"
static void swap(int *a, int *b)


    {
    register int t;
    t = *a;
    *a = *b;
    *b = t;
}
void quicksort(int v[], unsigned n)


    {
    unsigned i, j, ln, rn;
    while (n > 1)


        {
        swap(&v[0], &v[n/2]);
        for (i = 0, j = n; ; )


            {
            do
            --j;
            while (v[j] > v[0]);
            do
            ++i;
            while (i < j && v[i] < v[0]);
            if (i >= j)
            break;
            swap(&v[i], &v[j]);
        }
        swap(&v[j], &v[0]);
        ln = j;
        rn = n - ++j;
        if (ln < rn)


            {
            quicksort(v, ln);
            v += j;
            n = rn;
        }
        else


            {
            quicksort(v + j, rn);
            n = ln;
        }
    }
}