-
Cách Dùng: Tương tự hàm
qsort
trong thư viện stdlib.h
binary_insert_sort(mảng, số lượng phần tử, kích thước 1 phần tử, hàm so sánh);
-
độ phức tạp:
- trung bình: O(n^2)
- xấu nhất: O(n^2)
- tốt nhất: O(n)
- bộ nhớ: O(n)
-
source code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>
#define __sort
#define type void*
typedef int (*_sort_cmp_fn_t)(const type,const type);
inline void _sort_swap(type a,type b,int size){
if(size>16){
type t=malloc(size);
assert(t!=0);
memcpy(t,a,size);
memcpy(a,b,size);
memcpy(b,t,size);
free(t);
}else{
char tmp[size];
memcpy(tmp,a,size);
memcpy(a,b,size);
memcpy(b,tmp,size);
}
}
#define A(i) ((a)+(i)*(size))
inline int binary_insert_sort_find(const type x,type a,const int n,
int size,_sort_cmp_fn_t cmp){
int l,r,c;
type cx;
l=0;
r=n-1;
c=r>>1;
if(cmp(x,A(0))<0){
return 0;
}else if(cmp(x,A(r))>0){
return r;
}
cx=A(c);
while(1){
const int val=cmp(x,cx);
if(val<0){
if(c-l<=1) return c;
r=c;
}else{
if(r-c<=1) return c+1;
l=c;
}
c=l+((r-l)>>1);
cx=A(c);
}
}
inline void binary_insert_sort_start(type a,const int start,const int n,
_sort_cmp_fn_t cmp,int size){
register int i,j,location;
type x=malloc(size);
assert(x!=0);
for(i=start;i<n;++i){
if(cmp(A(i-1),A(i))<=0) continue;
memcpy(x,A(i),size);
location=binary_insert_sort_find(x,a,i,size,cmp);
for(j=i-1;j>=location;--j){
memcpy(A(j+1),A(j),size);
}
memcpy(A(location),x,size);
}
free(x);
}
inline void binary_insert_sort(type a,const int n, int size,_sort_cmp_fn_t cmp){
if(n<=1) return;
binary_insert_sort_start(a,1,n,cmp,size);
}
#undef A
#undef type
#undef __sort
typedef struct{
char name[20];
int level;
} user;
void show(user *a,int n){
int i;
for(i=0;i<n;++i){
printf("%d %s\n",a[i].level,a[i].name);
}
}
int cmp(const void *a,const void *b){
const user *x=a,*y=b;
if(x->level!=y->level) return x->level-y->level;
return strcmp(x->name,y->name);
}
int main(){
user a[]={
{"gio",2},
{"ltd",3},
{"honey_moon",2},
{"nhim_xu",3}
};
int s=sizeof(user);
int n=sizeof(a)/s;
int i;
binary_insert_sort(a,n,s,cmp);
show(a,n);
return 0;
}
#output
2 gio
2 honey_moon
3 ltd
3 nhim_xu