我发现我果然不适合用脑子去想问题，写这东西实在是太烧脑了。为了能够写出这份代码，我浪费了整整一个下午打游戏的时光和半个晚上，想想真是可惜，我美好的周末啊。
这份代码实现了一个排序，就是标准库中的牌序，那个支援各种数据的牌序。我这里也实现了。至少测试通过了基本类型。
入口引数和标准库的qsort完全相同，分别是数组地址，数组长度，数组中每个元素占据的字节数和比较函式。
#include <stdio.h>
/*
Parameter:
arr : address of array
len : sizeof(array/array[0])
size: sizeof(array[0])
func: this func return 1 (first arg first) -1 (second arg first)
*/
void myqsort(void *arr,int len,int size,int (*func)(const void *,const void *)){
void *i, *j;
int k;
i = (void *)((int)arr + size);
j = (void *)((int)arr + (len-1)*size);
if(len == 1 || len == 0)return;
while(i <= j){
/* 寻找要交换的元素 */
while( func(arr,i) < 0 && i < j){
i = (void*)((int)i + size);
}
while( func(arr,j) > 0 && j >= i){
j = (void*)((int)j - size);
}
/* 交换之 */
if( j > i ){
for(k=0; k<size/sizeof(char); k++){
char x = *((char *)(i)+k);
*((char *)i+k) = *((char *)j+k);
*((char *)j+k) = x;
}
}
i = (void*)((int)i + size);
}
/* 交换 arr[0] 和 j */
if( arr != j ){
for(k=0; k<size/sizeof(char); k++){
char x = *((char *)(j)+k);
*((char *)j+k) = *((char *)arr+k);
*((char *)arr+k) = x;
}
}
/* 继续快排 */
myqsort(arr,((int)j-(int)arr)/size,size,func);
myqsort((void*)((int)j+size),((int)arr + (len-1)*size-(int)j)/size,size,func);
}
#define T double
T a[] = {1.5,1.4,3.2,4.2,5.4,9.1,8.1,8.3,8.2};
int cmp(const void *a,const void *b){
return *(T *)a > *(T *)b ? 1 : -1;
}
int main(){
int i = 0;
for(i=0; i<sizeof(a)/sizeof(a[0]); i++){
printf("%g ",(double)a[i]);
}
printf("\n");
myqsort(a,sizeof(a)/sizeof(a[0]),sizeof(a[0]),cmp);
for(i=0; i<sizeof(a)/sizeof(a[0]); i++){
printf("%g ",(double)a[i]);
}
printf("\n");
return 0;
}
我写得肯定还有能够改进的部分，也许还有我不清楚的bug。还请诸君见笑。
改写了交换的写法。参考了一些其他人写法，将最后一个函式呼叫改为使用goto。
#include <stdio.h>
#include <inttypes.h>
/*
Swap a and b:
global : _w(uint8_t)
*/
static uint8_t _w;
#define swap_(a,b,_width) for(_w=0; _w<_width; _w++){ \
char __x = *((char*)(a)+_w); \
*((char *)a+_w) = *((char *)b+_w); \
*((char *)b+_w) = __x; \
}
#define swap(a,b) swap_(&(a),&(b),sizeof(a)/sizeof(char))
/*
Parameter:
arr : address of array
len : sizeof(array/array[0])
size: sizeof(array[0])
func: this func return 1 (first arg first) -1 (second arg first)
*/
void myqsort(void *arr,int len,int size,int (*func)(const void *,const void *)){
void *i, *j;
int len2;
loop:
i = (void *)((int)arr + size);
j = (void *)((int)arr + (len-1)*size);
while(i <= j){
/* 寻找要交换的元素 */
while( func(arr,i) < 0 && i < j){
i = (void*)((int)i + size);
}
while( func(arr,j) > 0 && j >= i){
j = (void*)((int)j - size);
}
/* 交换之 */
if( j > i ){
swap_(i,j,size/sizeof(char));
}
i = (void*)((int)i + size);
}
/* 交换 arr[0] 和 j */
if( arr != j ){
swap_(arr,j,size/sizeof(char));
}
/* 继续快排 */
len2 = ((int)j-(int)arr)/size;
if(len2 > 1){
myqsort(arr,len2,size,func);
}
len2 = ((int)arr + (len-1)*size-(int)j)/size;
if(len2 > 1){
/* myqsort((void*)((int)j+size),len2,size,func); */
/* 使用 goto 节省一次函式呼叫 */
len = len2;
arr = (void*)((int)j+size);
goto loop;
}
}
#define T int
T a[] = {1.5,1.4,3.2,4.2,0.0,5.4,9.1,8.1,8.3,8.2};
int cmp(const void *a,const void *b){
return *(T *)a < *(T *)b ? 1 : -1;
}
debug(){
double a = 10.4, b = 2.8;
struct{
int x,y;
}p1 = {1,2}, p2 = {3,4};
printf("%g %g\n",(double)a,(double)b);
swap(a,b);
printf("%g %g\n",(double)a,(double)b);
printf("(%g,%g) (%g,%g)\n",(double)p1.x,(double)p1.y,(double)p2.x,(double)p2.y);
swap(p1,p2);
printf("(%g,%g) (%g,%g)\n",(double)p1.x,(double)p1.y,(double)p2.x,(double)p2.y);
}
int main(){
int i = 0;
debug();
for(i=0; i<sizeof(a)/sizeof(a[0]); i++){
printf("%g ",(double)a[i]);
}
printf("\n");
myqsort(a,sizeof(a)/sizeof(a[0]),sizeof(a[0]),cmp);
for(i=0; i<sizeof(a)/sizeof(a[0]); i++){
printf("%g ",(double)a[i]);
}
printf("\n");
return 0;
}
加入的debug函式是用来测试swap的。关于swap函式可以参考我写的另一篇文章。