[管理]快速排序函数

[管理]快速排序函数 快速排序函数 /* * 前几天想到 快排函数qsort 想要了解函数功能是如何实现的故去看其源代码 * 很遗憾的是 无法理清其源代码功能实现的原理 故打算自己写一个快排函数 之后再看 * 在两天之后完成此函数 * 能力有限 此函数的时间效率和空间效率可能 不如 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 库自带的快排函数 * 另外此函数中可能存在其他未曾发现的 (内存)错误 若有发现者还望能提醒下本人。本人不胜感激。 * 此函数无偿作为c或c++学习爱好者学习之用，勿用于其他 * 编写时间 : 2012-07-06 * 完成时间 : 2012-07-08 * 最后修改时间: 2012-07-13 * 版本 : version 1.1 * 代码编写者 : 枫亭水榭 /**//**//**//**//**//**//**//**//**//**/ //--------------函数说明-------------------// void swap(char *a, char *b,int type_size); //内存空间内容交换 void short_sort(void *data,int lenght,int type_size, //小规模排序 int cmp(const void *a,const void *b)); void position_set(char data[],int lenght,int type_size, // 中间项确定中间值确定 int cmp(const void *a,const void *b)); void quick_sort_design(char data[],int lenght,int type_size, //大规模快速排序 -- 递归函数 int cmp(const void *a,const void *b)); /**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**/ //-----------------函数形参设置说明-------------------- /* * char *a : 交换单元的地址 * char *b :交换单元的地址 * int type_size : 数组元素所占用内存空间的大小(字节) * int cmp(const void *a,const void *b) : 比较函数 返 回值为 1 时交换 0 和 -1 是不变 * char data[] :数组的地址 * int lenght :数组元素个数 /**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**/ //----------------------用户快速排序调用函数----------- int qsort_design(void *data,int lenght,int type_size, int cmp(const void *a,const void *b)) { data = (char *)data; int count = 0; if (lenght < 2) return count; else if( lenght < 9) { short_sort(data,lenght,type_size,cmp); return ++count; } while(!complete(data, lenght, type_size, cmp)) { count++; // printf("%d\n", count); quick_sort_design(data,lenght,type_size,cmp); } return count; } void quick_sort_design(char data[],int lenght,int type_size, int cmp(const void *a,const void *b)) { char *mid = data + (int)((lenght-1)/2) * type_size; char *low = data; char *high = data + (lenght-1) * type_size; char *low_temp = low; char *high_temp = high; // printf("111\n"); if (lenght < 2) return; else if( lenght < 9) { short_sort(data,lenght,type_size,cmp); return; } position_set(data,lenght,type_size, cmp); low_temp = low; high_temp = high; while( low_temp < high_temp ) { // printf("quick_sort:\n"); while( low_temp < mid && cmp(low_temp,mid) <= 0) { low_temp += type_size; } while( mid < high_temp && cmp(mid, high_temp) <= 0) { high_temp -= type_size; } if( low_temp < high_temp && cmp(low_temp,high_temp) > 0) { swap(low_temp,high_temp,type_size); } } quick_sort_design(data,lenght/2,type_size,cmp); if (lenght % 2 == 0) mid += type_size; quick_sort_design(mid,lenght/2,type_size, cmp);/**/ return; } //使中间项尽量靠近中间值 void position_set(char data[],int lenght,int type_size, int cmp(const void *a,const void *b)) { char *mid = data + (lenght/2) * type_size; char *low = data; char *high = data + (lenght-1) * type_size; do { // printf("position:\n%x:%lf\t%x:%lf\t\%x:%lf\n", // low,*((double*)low),mid,*((double*)mid),high,*((double*)high)); if( cmp(low, mid) > 0) swap(low, mid, type_size); if( cmp(mid, high) > 0) swap(mid, high, type_size); }while( cmp(low,mid) > 0 || cmp(mid,high) > 0); return; } // 小规模排序时使用 void short_sort(void *data,int lenght,int type_size,int cmp(const void *a,const void *b)) { int i = 0; int j = 0; char *pa; char *pb; data = (char *)data; for (i = lenght-1; i > 0; i--) // 冒泡排序 { for(j = 0; j < i; j++) { pa = data+j*type_size; pb = data+(j+1)*type_size; if( cmp( pa, pb) > 0) { // printf("%x %x\n",pa,pb); swap(pa, pb,type_size); } } } } int complete(char data[],int lenght,int type_size, int cmp(const void *a,const void *b)) { int i = 0; char *current = data; // printf("if complete? \n"); for (i = 0; i < lenght - 1; i++) { if ( cmp(current, current+type_size) > 0 ) { // printf("not complete!\n"); return 0; } current += type_size; // printf("current address %x\n",current); } // printf("complete!\n"); return 1; } void swap(char *a, char *b,int type_size) { int width = type_size; char temp; // printf("swap ->>>%x:%lf\t%x:%lf",a,*(double *)a,b,*(double *)b); if (a == b) return ; while(width--) { temp = *a; *a++ = *b; *b++ = temp; } //每次交换一个字节的内容 }