//list_array.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAX_NAME_SIZE 20
struct data_info {
char name[MAX_NAME_SIZE];
size_t age;
};
#define _NtoPTR(base, size, n)
((char *)(base) + (size) * (n))
#define NtoPTR(n) _NtoPTR(base, size, (n))
int cmp_int(const void *a, const void *b)
{
int *pa = (int *)a;
int *pb = (int *)b;
return *pa - *pb;
}
int cmp_age(const void *a, const void *b)
{
struct data_info *pa = (struct data_info *)a;
struct data_info *pb = (struct data_info *)b;
return pa->age - pb->age;
}
void swap(void *a, void *b, size_t size)
{
char *t = (char *)malloc(size);
assert(t != NULL);
static size_t count = 0;
printf("count = %lu
", ++count);
memcpy(t, a, size);
memcpy(a, b, size);
memcpy(b, t, size);
free(t);
}
/*1. 冒泡排序 */
void sort_bubble(void *base, size_t nmemb, size_t size,
int(*cmp)(const void *a, const void *b))
{
size_t start, end;
for (end = nmemb - 1; end > 0; --end) {
for (start = 0; start < end; ++start) {
if (cmp(NtoPTR(start), NtoPTR(start + 1)) > 0) {
swap(NtoPTR(start), NtoPTR(start + 1), size);
}
}
}
}
/*2. 选择排序*/
void sort_select(void *base, size_t nmemb, size_t size,
int (*cmp)(const void *a, const void *b))
{
size_t start,next;
size_t min;
for (start = 0; start < nmemb - 1; ++start) {
min = start;
for (next = start + 1; next < nmemb; ++next) {
if (cmp(NtoPTR(next), NtoPTR(min)) < 0) {
min = next;
}
}
if (min != start) {
swap(NtoPTR(min), NtoPTR(start), size);
}
}
}
/*3. 插入排序*/
void sort_insert(void *base, size_t nmemb, size_t size,
int (*cmp)(const void *a, const void *b))
{
assert(base != NULL);
assert(cmp != NULL);
if (nmemb < 2) {
return ;
}
char *buf = (char *)malloc(size);
assert(buf);
int i,j;
for (i = 1; i < nmemb; ++i) {
j = i - 1;
if (cmp(NtoPTR(i), NtoPTR(j)) >= 0) {
continue;
}
memcpy(buf, NtoPTR(i), size);
for (; j >= 0; --j) {
if (cmp(NtoPTR(j), buf) > 0) {
memcpy(NtoPTR(j + 1), NtoPTR(j), size);
}else {
break;
}
}
memcpy(NtoPTR(j + 1), buf, size);
}
free(buf);
}
void sort_shell(void *base, size_t nmemb, size_t size,
int (*cmp)(const void *a, const void *b))
{
/*增量序列*/
size_t step[] = {2, 1};
int i,j,k,offset;
char *buf = (char *)malloc(size);
assert(buf != NULL);
for (i = 0; i < sizeof(step) / sizeof(step[0]); ++i) {
/*offset: 标识起始序列元素的下标*/
for (offset = 0; offset < step[i]; ++offset) {
#ifdef DEBUG
{
printf("
offset = %d
", offset);
for (k = offset; k < nmemb; k += step[i]) {
printf("%d ", *((int *)NtoPTR(k)));
}
}
#endif
/*-----sorting ----*/
//insert sort
for (k = offset + step[i]; k < nmemb; k += step[i]) {
j = k - step[i];
if (cmp(NtoPTR(k), NtoPTR(j)) > 0) {
continue;
}
memcpy(buf, NtoPTR(k), size);
for (; j >= offset; j -= step[i]) {
if (cmp(NtoPTR(j), buf) > 0) {
memcpy(NtoPTR(j + step[i]), NtoPTR(j), size);
}else {
break;
}
}
memcpy(NtoPTR(j + step[i]), buf, size);
}
#ifdef DEBUG
{
printf("
--------
");
for (k = offset; k < nmemb; k += step[i]) {
printf("%d ", *((int *)NtoPTR(k)));
}
}
#endif
}
}
free(buf);
}
void __sort_merge(void *base, void *buf, size_t nmemb,
size_t size,
int (*cmp)(const void *, const void *))
{
//拆分
if (nmemb < 2) {
return ;
} else {
__sort_merge(base, buf, nmemb >> 1, size, cmp);
__sort_merge(_NtoPTR(base, size, nmemb >> 1),
buf, nmemb - (nmemb >> 1), size, cmp);
}
//合并并排序
int l,r,index;
l = 0;
r = nmemb / 2;
index = 0;
while ((l < nmemb / 2) && (r < nmemb)) {
if (cmp(NtoPTR(l), NtoPTR(r)) <= 0) {
memcpy(_NtoPTR(buf, size, index), NtoPTR(l), size);
++l;
} else {
memcpy(_NtoPTR(buf, size, index), NtoPTR(r), size);
++r;
}
++index;
}
/*剩余部分*/
if (l < nmemb / 2) {
memcpy(_NtoPTR(buf, size, index), NtoPTR(l),
size * (nmemb / 2 - l));
} else {
memcpy(_NtoPTR(buf, size, index), NtoPTR(r),
size * (nmemb - r));
}
//回写原有空间
memcpy(base, buf, size * nmemb);
}
void sort_merge(void *base, size_t nmemb, size_t size,
int (*cmp)(const void *, const void *))
{
char *buf = (char *)calloc(nmemb, size);
assert(buf != NULL);
__sort_merge(base, buf, nmemb, size, cmp);
free(buf);
}
unsigned int rand_mid(size_t nmemb)
{
unsigned int s[3] = {0};
time_t t;
time(&t);
srand((unsigned int)t);
s[0] = rand() % nmemb;
s[1] = rand() % nmemb;
s[2] = rand() % nmemb;
sort_select(s, 3, sizeof(s[0]), cmp_int);
return s[1];
}
void __sort_quick(void *base, char *buf, size_t nmemb,
size_t size,
int (*cmp)(const void *, const void *))
{
if (nmemb < 2) {
return ;
}
/* size_t pivot = 0; // TODO V1.0 */
size_t pivot = rand_mid(nmemb);
size_t r, l;
l = 0;
r = nmemb - 1;
memcpy(buf, NtoPTR(pivot), size);
memcpy(NtoPTR(pivot), NtoPTR(l), size);
while (l < r) {
for (; l < r; --r) {
if (cmp(NtoPTR(r), buf) < 0) {
memcpy(NtoPTR(l), NtoPTR(r), size);
++l;
break; //注意
}
}
for (; l < r; ++l) {
if (cmp(NtoPTR(l), buf) > 0) {
memcpy(NtoPTR(r), NtoPTR(l), size);
--r;
break;
}
}
}
//l 与 r 相遇
memcpy(NtoPTR(l), buf, size);
//尾递归
__sort_quick(base, buf, l, size, cmp);
__sort_quick(NtoPTR(l + 1), buf, nmemb - l - 1, size, cmp);
}
void sort_quick(void *base, size_t nmemb, size_t size,
int (*cmp)(const void *, const void *))
{
char *buf = (char *)malloc(size);
assert(buf != NULL);
__sort_quick(base, buf, nmemb, size, cmp);
free(buf);
}
int main()
{
#if 0
struct data_info s[] = {
{"tom", 18}, {"niko", 22}, {"frank", 17}, {"kevin", 28},
{"richard", 22}, {"mark", 20} , {"tube", 21}, {"jack", 23} };
int i;
for (i = 0; i < sizeof s / sizeof(s[0]); ++i) {
printf("%s:%lu
", s[i].name, s[i].age);
}
#endif
int s[] = {6, 5, 9, 3, 1, 7, 5, 9, 4};
int i;
for (i = 0; i < sizeof s/ sizeof s[0]; ++i) {
printf("%d ", s[i]);
}
printf("
");
printf("-------sorting------
");
void (*sort[])(void *base, size_t nmemb, size_t size,
int (*cmp)(const void *, const void *)) =
{
sort_bubble, //[0]
sort_select, //[1]
sort_insert, //[2]
sort_shell, //[3]
sort_merge, //[4]
sort_quick, //[5]
};
sort[5](s, sizeof s /sizeof s[0], sizeof(s[0]), cmp_int);
printf("
##list##
");
#if 0
for (i = 0; i < sizeof s / sizeof(s[0]); ++i) {
printf("%s:%lu
", s[i].name, s[i].age);
}
#endif
#if 1
for (i = 0; i < sizeof s / sizeof(s[0]); ++i) {
printf("%d ", s[i]);
}
printf("
");
#endif
return 0;
}