基本排序算法之冒泡排序C实现
基本排序算法之选择排序C实现
基本排序算法之插入排序C实现
基本排序算法之希尔排序C实现
基本排序算法之快速排序C实现
基本排序算法之归并排序C实现
基本排序算法之堆排序C实现
- /*
-
* file: main.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-19
-
*/
-
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <time.h>
-
#include <string.h>
-
-
#include "sorts.h"
-
-
int compare(const int *d1, const int *d2)
-
{
-
if (*d1 < *d2)
-
return -1;
-
else if (*d1 > *d2)
-
return 1;
-
else
-
return 0;
-
}
-
-
-
#define CNTOFARRAY(x) (sizeof(x)/sizeof(x[0]))
-
-
#define ARRAY_MAX 10
-
#define DATA_MAX 100
-
-
typedef void (*sort_func)(void*, size_t, size_t, CMP_FUNC, SWAP_FUNC);
-
-
void test_random(sort_func fsort)
-
{
-
int rdata, rsize, i, j;
-
int *pnew=0;
-
srand ((unsigned)time(NULL));
-
-
for (i = 0; i < 10; i++) {
-
rsize = rand()%ARRAY_MAX+1;
-
pnew = malloc(sizeof(int) * rsize);
-
__assert(pnew);
-
for (j = 0; j < rsize; j++) {
-
rdata = rand()%DATA_MAX;
-
rdata = rand()%2 ? -rdata : rdata;
-
pnew[j] = rdata;
-
}
-
printf("------------------------------\n");
-
fsort(pnew, rsize, sizeof(int), compare, 0);
-
if(pnew) free(pnew);
-
}
-
}
-
typedef struct sort_s {
-
char *p;
-
sort_func f;
-
}sort_t;
-
-
#define sort_init(s) {#s,s}
-
-
void main()
-
{
-
int i;
-
void *p1,*p2,*p3,*p4,*p5;
-
const int a1[]={9,7,-2,10,-3,2,8,7,1,0};
-
const int a2[]={1,1,1,1,1,1};
-
const int a3[]={3};
-
const int a4[]={5,2};
-
const int a5[]={49,38,65,97,76,13,27,49,55,04};
-
-
sort_t sorts[] = {
-
sort_init(bubble_sort),
-
sort_init(select_sort),
-
sort_init(insert_sort),
-
sort_init(shell_sort),
-
sort_init(quick_sort),
- sort_init(merge_sort),
- sort_init(heap_sort),
-
};
-
-
-
p1 = malloc(sizeof(a1));
-
p2 = malloc(sizeof(a2));
-
p3 = malloc(sizeof(a3));
-
p4 = malloc(sizeof(a4));
-
p5 = malloc(sizeof(a5));
-
__assert (p1 && p2 && p3 && p4 && p5);
-
-
for (i=0; i < CNTOFARRAY(sorts); i++) {
-
memcpy(p1, a1, sizeof(a1));
-
memcpy(p2, a2, sizeof(a2));
-
memcpy(p3, a3, sizeof(a3));
-
memcpy(p4, a4, sizeof(a4));
-
memcpy(p5, a5, sizeof(a5));
-
printf("==========> %s start ==========\n", sorts[i].p);
-
sorts[i].f(p1, CNTOFARRAY(a1), sizeof(a1[0]), compare, 0);
-
printf("---------------------------------------------\n");
-
sorts[i].f(p2, CNTOFARRAY(a2), sizeof(a2[0]), compare, 0);
-
printf("---------------------------------------------\n");
-
sorts[i].f(p3, CNTOFARRAY(a3), sizeof(a3[0]), compare, 0);
-
printf("---------------------------------------------\n");
-
sorts[i].f(p4, CNTOFARRAY(a4), sizeof(a4[0]), compare, 0);
-
printf("---------------------------------------------\n");
-
sorts[i].f(p5, CNTOFARRAY(a5), sizeof(a5[0]), compare, 0);
-
-
printf("================ random test ... ============\n");
-
test_random(sorts[i].f);
-
printf("==========> %s end ! ==========\n", sorts[i].p);
-
}
-
-
free(p1);
-
free(p2);
-
free(p3);
-
free(p4);
-
free(p5);
-
}
---------------------------------------------------------------------------------------------
- /*
-
* file: sorts.h
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-19
-
*/
-
-
#ifndef __SORTS_H__
-
#define __SORTS_H__
-
-
#include <stdio.h>
-
#include <stdlib.h>
-
-
#ifndef __assert
-
#define __assert(x)
-
#endif
-
-
typedef int (*CMP_FUNC)(const void *d1, const void *d2);
-
typedef void (*SWAP_FUNC)(void *d1, void *d2, unsigned int size);
-
-
int cmp_dft(const void *d1, const void *d2);
-
void swap_dft(void *d1, void *d2, unsigned int size);
-
-
void dump_all(void *base, size_t num, size_t size);
-
int verify(void *base, size_t num, size_t size, CMP_FUNC cmpf);
-
-
void bubble_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf);
-
-
void select_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf);
-
-
void insert_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf);
-
-
void shell_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf);
-
-
void quick_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf);
-
void merge_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf);
-
void heap_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf);
-
#endif
----------------------------------------------------------------------------------------------
- /*
-
* file: sorts.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-19
-
*/
-
-
#include "sorts.h"
-
-
void swap_dft(void *d1, void *d2, unsigned int size)
-
{
-
char t;
-
while (size--)
-
{
-
t = *(char*)d1;
-
*((char*)d1)++ = *(char*)d2;
-
*((char*)d2)++ = t;
-
}
-
}
-
-
void dump_dft(void *d1)
-
{
-
printf("%d ", *(int*)d1);
-
}
-
-
void dump_all(void *base, size_t num, size_t size)
-
{
-
unsigned int i;
-
__assert(base);
-
-
for (i=0; i < num; i++) {
-
dump_dft((char*)base+i*size);
-
}
-
printf("\n");
-
}
-
-
int verify(void *base, size_t num, size_t size, CMP_FUNC cmpf)
-
{
-
unsigned int i, c;
-
int flag=0, r;
-
__assert(base);
-
-
for (i=0; i < num-1; i++) {
-
c = i*size;
-
r = cmpf((char*)base+c, (char*)base+c+size);
-
if (!flag && r)
-
{
-
flag = (flag=r)<0 ? -1 : 1;
-
}
-
if(r!=0 && r!=flag) return -1;
-
}
-
return 0;
-
}
----------------------------------------------------------------------------------------------
- /*
-
* file: bubble_sort.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-19
-
*/
-
-
#define DEBUG
-
-
#include "sorts.h"
-
-
#ifdef DEBUG
-
#define __dump(b,n,sz) dump_all(b,n,sz)
-
#define __verify(b,n,sz,cmp) \
-
{ \
-
if(verify(b, n, sz, cmp)!=0) \
-
printf("\n==>verification failed!\n"); \
-
}
-
#else
-
#define __dump(b,n,sz)
-
#define __verify(b,n,sz,cmp)
-
#endif
-
-
static void __swap(void *d1, void *d2, size_t size)
-
{
-
unsigned int t = *(unsigned int *)d1;
-
*(unsigned int *)d1 = *(unsigned int *)d2;
-
*(unsigned int *)d2 = t;
-
}
-
-
void bubble_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
unsigned int i, j, c;
-
__assert(base && cmpf);
-
if (!swapf)
-
swapf = (size == 4 ? __swap : swap_dft);
-
__dump(base, num, size);
-
for (i = 1; i < num; i++){
-
for (j = 0; j < num-i; j++){
-
c = j*size;
-
if (cmpf((char*)base+c, (char*)base+c+size) > 0)
-
swapf((char*)base+c, (char*)base+c+size, size);
-
}
-
__dump(base, num, size);
-
}
-
__verify(base, num, size, cmpf);
-
}
----------------------------------------------------------------------------------------------
- /*
-
* file: select_sort.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-19
-
*/
-
-
#define DEBUG
-
-
#include "sorts.h"
-
-
#ifdef DEBUG
-
#define __dump(b,n,sz) dump_all(b,n,sz)
-
#define __verify(b,n,sz,cmp) \
-
{ \
-
if(verify(b, n, sz, cmp)!=0) \
-
printf("\n==>verification failed!\n"); \
-
}
-
#else
-
#define __dump(b,n,sz)
-
#define __verify(b,n,sz,cmp)
-
#endif
-
-
static void __swap(void *d1, void *d2, size_t size)
-
{
-
unsigned int t = *(unsigned int *)d1;
-
*(unsigned int *)d1 = *(unsigned int *)d2;
-
*(unsigned int *)d2 = t;
-
}
-
-
void select_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
unsigned int i, j;
-
void *pmark;
-
__assert(base && cmpf);
-
if (!swapf)
-
swapf = (size == 4 ? __swap : swap_dft);
-
__dump(base, num, size);
-
for (i = 0; i < num-1; i++) {
-
pmark = (char*)base+i*size;
-
for (j = i+1; j < num; j++) {
-
if (cmpf(pmark, (char*)base+j*size)>0)
-
pmark = (char*)base+j*size;
-
}
-
swapf(pmark, (char*)base+i*size, size);
-
__dump(base, num, size);
-
}
-
__verify(base, num, size, cmpf);
-
}
----------------------------------------------------------------------------------------------
- /*
-
* file: insert_sort.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-19
-
*/
-
-
#define DEBUG
-
-
#include "sorts.h"
-
-
#ifdef DEBUG
-
-
#define __dump(b,n,sz) dump_all(b,n,sz)
-
-
#define __verify(b,n,sz,cmp) \
-
{ \
-
if(verify(b, n, sz, cmp)!=0) \
-
printf("\n==>verification failed!\n"); \
-
}
-
-
#else
-
-
#define __dump(b,n,sz)
-
#define __verify(b,n,sz,cmp)
-
-
#endif
-
-
-
static void __swap(void *d1, void *d2, size_t size)
-
{
-
unsigned int t = *(unsigned int *)d1;
-
*(unsigned int *)d1 = *(unsigned int *)d2;
-
*(unsigned int *)d2 = t;
-
}
-
-
void insert_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
unsigned int i, j, c;
-
__assert(base && cmpf);
-
if (!swapf)
-
swapf = (size == 4 ? __swap : swap_dft);
-
__dump(base, num, size);
-
for (i = 1; i < num; i++){
-
for (j = i; j > 0; j--){
-
c = j*size;
-
if (cmpf((char*)base+c, (char*)base+c-size) < 0)
-
swapf((char*)base+c, (char*)base+c-size, size);
-
else
-
break;
-
}
-
__dump(base, num, size);
-
}
-
__verify(base, num, size, cmpf);
-
}
----------------------------------------------------------------------------------------------
- /*
-
* file: shell_sort.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-19
-
*/
-
-
#define DEBUG
-
-
#include "sorts.h"
-
-
#ifdef DEBUG
-
#define __dump(b,n,sz) dump_all(b,n,sz)
-
#define __verify(b,n,sz,cmp) \
-
{ \
-
if(verify(b, n, sz, cmp)!=0) \
-
printf("\n==>verification failed!\n"); \
-
}
-
#else
-
#define __dump(b,n,sz)
-
#define __verify(b,n,sz,cmp)
-
#endif
-
-
static void __swap(void *d1, void *d2, size_t size)
-
{
-
unsigned int t = *(unsigned int *)d1;
-
*(unsigned int *)d1 = *(unsigned int *)d2;
-
*(unsigned int *)d2 = t;
-
}
-
-
static void __shell_once(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf, unsigned int scale)
-
{
-
unsigned int i, j, c, d, q=0;
-
//printf("---> scale : %d \n", scale);
-
while (q < scale) {
-
for (i = q+scale; i < num; i = i+scale){
-
for (j = i; j >= scale; j = j-scale){
-
c = j*size;
-
d = scale*size;
-
if (cmpf((char*)base+c, (char*)base+c-d) < 0)
-
swapf((char*)base+c, (char*)base+c-d, size);
-
else
-
break;
-
}
-
}
-
q++;
-
}
-
__dump(base, num, size);
-
}
-
-
void shell_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
unsigned int s = num;
-
__assert(base && cmpf);
-
if (!swapf)
-
swapf = (size == 4 ? __swap : swap_dft);
-
__dump(base, num, size);
-
while ((s=(s)>>1) >= 1) {
-
__shell_once(base, num, size, cmpf, swapf, (s&0x01)?s:s+1);
-
}
-
__verify(base, num, size, cmpf);
-
}
----------------------------------------------------------------------------------------------
- /*
-
* file: quick_sort.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-19
-
*/
-
-
#define DEBUG
-
-
#include "sorts.h"
-
-
#ifdef DEBUG
-
-
#define __dump(b,n,sz) dump_all(b,n,sz)
-
-
#define __verify(b,n,sz,cmp) \
-
{ \
-
if(verify(b, n, sz, cmp)!=0) \
-
printf("\n==>verification failed!\n"); \
-
}
-
-
#else
-
-
#define __dump(b,n,sz)
-
#define __verify(b,n,sz,cmp)
-
-
#endif
-
-
-
static void __swap(void *d1, void *d2, size_t size)
-
{
-
unsigned int t = *(unsigned int *)d1;
-
*(unsigned int *)d1 = *(unsigned int *)d2;
-
*(unsigned int *)d2 = t;
-
}
-
-
-
static unsigned int __quick_once(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
unsigned int i=0, j=num-1;
-
while (1) {
-
while (i<j && cmpf((char*)base+i*size, (char*)base+j*size) <= 0)
-
j--;
-
if (i==j) break;
-
swapf((char*)base+i*size, (char*)base+j*size, size);
-
i++;
-
while (i<j && cmpf((char*)base+i*size, (char*)base+j*size) <= 0)
-
i++;
-
if (i==j) break;
-
swapf((char*)base+i*size, (char*)base+j*size, size);
-
j--;
-
}
-
return i;
-
}
-
-
static void __quick_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
unsigned int k;
-
__assert(base && cmpf);
-
if (!swapf)
-
swapf = (size == 4 ? __swap : swap_dft);
-
if (num > 1)
-
{
-
k = __quick_once(base,num,size,cmpf,swapf);
-
__quick_sort(base, k, size, cmpf, swapf);
-
__quick_sort((char*)base+(k+1)*size, num-k-1, size, cmpf, swapf);
-
}
-
}
-
-
void quick_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
__dump(base, num, size);
-
__quick_sort(base, num, size, cmpf, swapf);
-
__dump(base, num, size);
-
__verify(base, num, size, cmpf);
-
}
----------------------------------------------------------------------------------------------
- /*
-
* file: merge_sort.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-19
-
*/
-
-
#define DEBUG
-
-
#include "sorts.h"
-
-
#ifdef DEBUG
-
-
#define __dump(b,n,sz) dump_all(b,n,sz)
-
-
#define __verify(b,n,sz,cmp) \
-
{ \
-
if(verify(b, n, sz, cmp)!=0) \
-
printf("\n==>verification failed!\n"); \
-
}
-
-
#else
-
-
#define __dump(b,n,sz)
-
#define __verify(b,n,sz,cmp)
-
-
#endif
-
-
#define __malloc(x) malloc(x)
-
#define __free(x) free(x)
-
#define __memcpy(d,s,c) memcpyx(d,s,c)
-
-
static void *memcpyx(void *dest, const void*src, size_t n)
-
{
-
char *dest1 = dest;
-
const char *src1 = src;
-
while(n--)
-
*dest1++ = *(char*)src1++;
-
return dest;
-
}
-
-
static void __swap(void *d1, void *d2, size_t size)
-
{
-
unsigned int t = *(unsigned int *)d1;
-
*(unsigned int *)d1 = *(unsigned int *)d2;
-
*(unsigned int *)d2 = t;
-
}
-
-
/*
-
* [0 ... m] [m+1 ... num-1]
-
*/
-
static void __merge(void *base, size_t num, size_t size, size_t m,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
unsigned int i=0, j=m+1, c;
-
void *ptmp, *pold;
-
pold = ptmp = __malloc(num*size);
-
-
__assert(base && ptmp && m <= num);
-
// printf("----------> m: %d\n", m);
-
while (i<=m && j<num) {
-
c = cmpf((char*)base+i*size, (char*)base+j*size)<=0 ? i++ : j++;
-
__memcpy(ptmp, (char*)base+c*size, size);
-
ptmp = (char*)ptmp+size;
-
}
-
if (i<=m)
-
__memcpy(ptmp, (char*)base+i*size, (m-i+1)*size);
-
if (j<num)
-
__memcpy(ptmp, (char*)base+j*size, (num-j)*size);
-
__memcpy(base, pold, num*size);
-
-
// __dump(base, num, size);
-
__free(pold);
-
}
-
-
-
void merge_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
unsigned int i, c, step=1;
-
__assert(base && cmpf);
-
if (!swapf)
-
swapf = (size == 4 ? __swap : swap_dft);
-
__dump(base, num, size);
-
while (step < num)
-
{
-
for(i = 0; i < num; i += 2*step)
-
{
-
c = (i+2*step)>num?num-i:step*2;
-
__merge((char*)base+i*size, c, size, step-1, cmpf, swapf);
-
}
-
step *= 2;
-
}
-
__dump(base, num, size);
-
__verify(base, num, size, cmpf);
-
}
----------------------------------------------------------------------------------------------
- /*
-
* file: heap_sort.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-19
-
*/
-
-
#define DEBUG
-
-
#include "sorts.h"
-
-
#ifdef DEBUG
-
-
#define __dump(b,n,sz) dump_all(b,n,sz)
-
-
#define __verify(b,n,sz,cmp) \
-
{ \
-
if(verify(b, n, sz, cmp)!=0) \
-
printf("\n==>verification failed!\n"); \
-
}
-
-
#else
-
-
#define __dump(b,n,sz)
-
#define __verify(b,n,sz,cmp)
-
-
#endif
-
-
-
static void __swap(void *d1, void *d2, size_t size)
-
{
-
unsigned int t = *(unsigned int *)d1;
-
*(unsigned int *)d1 = *(unsigned int *)d2;
-
*(unsigned int *)d2 = t;
-
}
-
-
/*
-
* i is the first position of array need to adjust ...
-
*/
-
void heap_adjust(void *base, size_t num, size_t size, int i,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
unsigned int nchild, c;
-
void *pmark;
-
int t1, t2;
-
for (; 2*i+1 < num; i=nchild)
-
{
-
pmark=(char*)base+i*size;
-
nchild = 2*i+1;
-
c = nchild*size;
-
if (nchild < num-1 && cmpf((char*)base+c, (char*)base+c+size) < 0)
-
{
-
++nchild;
-
c += size;
-
}
-
t1 = *(int*)pmark;
-
t2 = *(int*)((char*)base+c);
-
if (cmpf(pmark, (char*)base+c) < 0)
-
swapf(pmark, (char*)base+c, size);
-
else
-
break;
-
}
-
__dump(base, num, size);
-
}
-
-
void heap_sort(void *base, size_t num, size_t size,
-
CMP_FUNC cmpf, SWAP_FUNC swapf)
-
{
-
int i;
-
__assert(base && cmpf);
-
if (!swapf)
-
swapf = (size == 4 ? __swap : swap_dft);
-
__dump(base, num, size);
-
-
for (i=num/2-1; i>=0; --i)
-
{
-
heap_adjust(base, num, size, i, cmpf, swapf);
-
}
-
for (i=num-1; i>0; --i)
-
{
-
swapf((char*)base, (char*)base+i*size, size);
-
heap_adjust(base, i, size, 0, cmpf, swapf);
-
}
-
__dump(base, num, size);
-
__verify(base, num, size, cmpf);
-
}
结束!
附件:
algorithm_sorts.rar
阅读(4824) | 评论(0) | 转发(0) |