快速排序（quick sort）是由C.A.R.Hoare发明并命名的，这种排序被认为是目前最好的一种排序算法。快速排序基于交换排序，与同样的基于交换排序的冒泡排序法相比，其效果非常明显。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
本例中快速排序是通过函数quick_disk(FILE* fp,int count)中反复调用排序函数qs_disk(FILE* fp,int left,int right)实现快速排序。在qs_disk()中，通过函数get_name(fp,(long)(i+j)/2)返回中间值作为比较数进行快速排序。
下面是具体的源代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUM 4
struct data
{
char name[20];
char school[20];
char city[20];
char province[20];
}info;
struct data addrs[NUM]=
{
"OKBase","BIT","JiLin","JiLin",
"TongWei","BIT","ZhengJiang","JiangSu",
"SunYou","BIT","WeiFang","ShangDong",
"XiaoMing","PKU","TaiYuan","ShanXi"
};
/*对后面要用到的函数进行声明*/
void quick_disk(FILE *fp,int count);
void qs_disk(FILE *fp,int left,int right);
void exchangedata(FILE *fp,long i, long j);
char *get_name(FILE *fp, long rec);
void print_data(struct data *p);
struct data *get_data(FILE *fp,long rec);
int main(void)
{
int i;
FILE *fp; /*文件指针*/
/*以读写方式生成文本文件fp*/
if((fp = fopen("datalist.txt","w+")) == NULL)
{
printf("打开文件失败\n");
exit(1);
}
printf("将未排序的数据写入文件\n");
/*将数组Sdata[NUM]写入文件中*/
fwrite(addrs,sizeof(addrs),1,fp);
/*将文件中的数组Sdata[NUM]依次取出并打印*/
for(i=0;i<NUM;i++)
{
struct data *p;
p = get_data(fp,i); /*得到Sdata[i]的指针*/
print_data(p); /*将结构体Sdata[i]各个成员变量打印出*/
printf("\n");
}
fclose(fp); /*关闭文件指针*/
/*以二进制方式再次打开文件datalist.txt*/
if((fp=fopen("datalist.txt","rb+"))==NULL)
{
printf("不能以读写方式打开文件\n");
exit(1);
}
printf("将文件数据排序\n");
/*调用字符串排序函数将文本中的字符串结构体排序*/
quick_disk(fp,NUM);
printf("排序结束\n");
/*将排序结束后的数组数据打印出来*/
for(i=0;i<4;i++)
{
struct data *p;
p = get_data(fp,i);
print_data(p);
printf("\n");
}
fclose(fp);
return 0;
}
/*应用快速排序方法对字符串进行排序*/
void quick_disk(FILE *fp,int count)
{
qs_disk(fp,0,count-1);
}
/*排序函数*/
void qs_disk(FILE *fp,int left,int right)
{
long int i,j;
char x[30];
i = left;
j = right;
/*比较字符串x为Sdata数组中间一个结构变量的name成员变量*/
strcpy(x,get_name(fp,(long)(i+j)/2));
do
{ /*比较当前结构变量的name成员变量于比较字符串x的大小*/
while((strcmp(get_name(fp,i),x)<0)&&(i<right))
i++;
while((strcmp(get_name(fp,j),x)>0)&&(j>left))
j--;
if(i<=j)
{
exchangedata(fp,i,j); /*交换i和j对应的数据*/
i++;
j--;
}
}while(i<j);
if(left<j) /*反复调用此排序函数，直到j达到数据的最左端*/
qs_disk(fp,left,(int)j);
if(i<right) /*反复调用此排序函数，直到i达到数据的最右端*/
qs_disk(fp,(int)i,right);
}
/*交换i和j在文件中对应的数据*/
void exchangedata(FILE *fp,long i,long j)
{
char a[sizeof(info)],b[sizeof(info)];
fseek(fp,sizeof(info)*i,SEEK_SET); /*找到i在文件中对应的数据位置*/
fread(a,sizeof(info),1,fp); /*将该位置数据读到字符串数组a中*/
fseek(fp,sizeof(info)*j,SEEK_SET); /*找到j在文件中对应的数据位置*/
fread(b,sizeof(info),1,fp); /*将该位置数据读到字符串数组b中*/
fseek(fp,sizeof(info)*j,SEEK_SET); /*找到j在文件中对应的数据位置*/
fwrite(a,sizeof(info),1,fp); /*将刚才读入a中的数据写入到该位置*/
fseek(fp,sizeof(info)*i,SEEK_SET); /*找到i在文件中对应的数据位置*/
fwrite(b,sizeof(info),1,fp); /*将刚才读入b中的数据写入到该位置*/
/*完成文件中i和j处对应数据的交换*/
}
/*得到文件fp中变量rec对应的结构体变量的name成员变量*/
char *get_name(FILE *fp,long rec)
{
struct data *p;
p = &info;
rewind(fp);
/*找到该结构体变量得的位置*/
fseek(fp,rec*sizeof(struct data),SEEK_SET);
/*将其读到指针p*/
fread(p,sizeof(struct data),1L,fp);
return p->name; /*返回该结构体变量的name成员变量*/
}
/*得到文件fp中变量rec对应的结构体变量的指针*/
struct data *get_data(FILE *fp,long rec)
{
struct data *p;
p = &info;
rewind(fp);
/*找到该结构体变量得的位置*/
fseek(fp,rec*sizeof(info),SEEK_SET);
/*将其读到指针p*/
fread(p,sizeof(info),1,fp);
return p; /*返回该结构体指针*/
}
/*将指针p对应的结构体的各个成员变量打印出来*/
void print_data(struct data *p)
{
printf("姓名：%s\n",p->name);
printf("学校：%s\n",p->school);
printf("城市：%s\n",p->city);
printf("省 ：%s\n",p->province);
}
|
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://www.okbase.net/doc/details/4175