putchar('\\n'); return OK; }//outputList
static int partition (PSqList p, int (*comp) (void *, void *), int low, int high)
{//交换顺序表[low...high]记录,枢轴记录到位，并返回其值，此时在它之前的记录不大于它，在它之后的记录不小于它
RedType tmp = p->list[low]; //用于存储中轴
while (low < high) {
while (low < high && comp (&(p->list[high]), &(tmp)) >= 0) high--;
p->list[low] = p->list[high];
while (low < high && comp (&(p->list[low]), &(tmp)) <= 0) low++;
p->list[high] = p->list[low]; }
p->list[low] = tmp;
return low; }//partition
static int QSort (PSqList p, int (*comp)(void *, void *),int low, int high) {//对顺序表p的子序列list[low,high]进行排序 if (low >= high) return 0;
int pivotloc = 0;
pivotloc = partition(p,comp, low, high); QSort (p, comp, low, pivotloc - 1); QSort (p, comp, pivotloc +1, high); return OK; }//QSort
int quickSort (PSqList p, int (*comp)(void *, void *)) {//对表p进行快速排序
QSort (p,comp,0,p->length-1); return OK; }//quickSort
/*这是main.cpp文件*/ #include
int comp(void * d1, void * d2);
int main (int argc, char * argv) {
int status; PSqList test;
test = (PSqList)malloc(sizeof(SqList)); int n = 0 ;
printf(\请输入第一组待排序的数的个数(输入0结束循环)：\
while (1) {
while (scanf(\ {
puts(\输入有误！请重新输入！\ while(getchar() != '\\n'); }
if (n == 0) //结束 break;
if (status = inputList(test, n) != 0) {
puts(\输入的数字有误！\ while(getchar() != '\\n'); //exit(status); }
quickSort(test,comp); outputList(test);
printf(\请输入下一组待排序的数的个数(输入0结束循环)：\ }
free(test); return 0; }
int comp(void * d1, void * d2) {//比较函数
return (((PRedType)d1)->data - ((PRedType)d2)->data );
}
//堆排序
/*这是heap_sort.h文件*/ #ifndef heap_sort
#define heap_sort
#define MAXSIZE 100 typedef int KeyType;
typedef struct {
KeyType data; //其他的属性 }RedType,* PRedType;
typedef struct {
RedType list[MAXSIZE]; int length; }SqList, * PSqList;
#define K_T \ //用于输入输出 如 printf(K_T, p->list[i].data);
#define OK 0
#define P_NULL 1 #define TOOBIG 2
#define NUM_ERROR 3
int inputList (PSqList p,int length); int outputList (PSqList p);
int heapSort(PSqList p, int (*comp)(void *,void *)); #endif
/*这是heap_sort.cpp文件*/ #include
int inputList (PSqList p,int length) {//输入序列
if (p == NULL)
return P_NULL; //1，指针是空的 if (length > MAXSIZE)
return TOOBIG; //2，要输入的序列太多 srand(time(NULL)); int i = 0;
for (i = 0; i < length; i++)
p->list[i].data = rand()000;
//if (scanf(K_T,&(p->list[i].data)) != 1)
// return NUM_ERROR; //3，输入的数字有误 p->length = length; return OK; //0 }
int outputList (PSqList p) {//输出序列
if (p == NULL)
return P_NULL;
int i = 0;
for (i =0; i < p->length; i++)
printf (K_T\ putchar('\\n'); return OK; }//outputList
int heapAdjust (PSqList p, int (*comp)(void *, void *), int s, int m)
{//已知p->list[s...m]中记录的关键字除[s]外，均满足堆的定义，本函数调整第s个关键字，是[s...m]成为一个大顶堆（对给定的比较函数而言） int i;
RedType tmp; tmp = p->list[s];
//第i个元素的打一个后继为2*i+1，[0]存放着第一个元素 for (i = 2*s+1; i <= m; i=2*s+1) {
if (i < m && comp(&(p->list[i+1]),&(p->list[i])) > 0 ) i++;
if (comp(&(p->list[i]),&(tmp)) < 0) break;
p->list[s] = p->list[i]; s = i; }
p->list[s] = tmp; return 0;
}//headAdjust
int heapSort (PSqList p, int (*comp)(void *, void *)) {
RedType tmp; int i;
for (i = p->length/2-1; i >= 0; i--)
heapAdjust(p, comp, i,p->length-1);
for (i = p->length-1; i > 0; i--) {
tmp = p->list[i];
p->list[i] = p->list[0]; p->list[0] = tmp;
heapAdjust(p, comp, 0, i-1); }
return OK; }//heapSort
/*这是main.cpp文件*/ #include
int main (int argc, char * argv) {
int status; PSqList test;
test = (PSqList)malloc(sizeof(SqList)); int n = 0 ;
printf(\请输入第一组待排序的数的个数(输入0结束循环)：\
while (1) {
while (scanf(\ {
puts(\输入有误！请重新输入！\ while(getchar() != '\\n'); }
if (n == 0) //结束
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库几种排序算法的代码实现(2)在线全文阅读。
相关推荐：