冒泡排序
冒泡排序很容易理解，外面的一层循环仅仅是为了执行n次，里面的一层循环是从最后面开始，将数与前面一个数进行比较，如果后面的数小于前面的数，那么交换，这样两两交换，得到了数组前面第一个已排序好的最小的数。重复n次则可将数组排序好，值得注意的是，思考这样一个问题，当进行了最外层循环的k（k
快速排序
下面给出快速排序的算法
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
//冒泡排序算法
#include "seqlist.cpp"
void BubbleSort(RecType R[],int n)
{
int i,j,k;
RecType tmp;
for (i=0;i<n-1;i++)
{
for (j=n-1;j>i;j--) //比较,找出本趟最小关键字的记录
if (R[j].key<R[j-1].key)
{
tmp=R[j]; //R[j]与R[j-1]进行交换,将最小关键字记录前移
R[j]=R[j-1];
R[j-1]=tmp;
}
printf(" i=%d: ",i);
DispList(R,n);
}
}
int main()
{
int n=10;
RecType R[MAXL];
KeyType a[]={9,8,7,6,5,4,3,2,1,0};
CreateList(R,a,n);
printf("排序前:"); DispList(R,n);
BubbleSort(R,n);
printf("排序后:"); DispList(R,n);
return 1;
}
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
//改进的冒泡排序算法
#include "seqlist.cpp"
void BubbleSort1(RecType R[],int n)
{ int i,j;
bool exchange;
RecType tmp;
for (i=0;i<n-1;i++)
{ exchange=false; //一趟前exchange置为假
for (j=n-1;j>i;j--) //归位R[i],循环n-i-1次
if (R[j].key<R[j-1].key) //相邻两个元素反序时
{ tmp=R[j]; //将这两个元素交换
R[j]=R[j-1];
R[j-1]=tmp;
exchange=true; //一旦有交换，exchange置为真
}
printf(" i=%d: ",i);
DispList(R,n);
if (!exchange) //本趟没有发生交换，中途结束算法
return;
}
}
int main()
{
int n=10;
RecType R[MAXL];
KeyType a[]={0,1,7,2,5,4,3,6,8,9};
CreateList(R,a,n);
printf("排序前:"); DispList(R,n);
BubbleSort1(R,n);
printf("排序后:"); DispList(R,n);
return 1;
}
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
//快速排序算法
#include "seqlist.cpp"
int count=0;
int partition(RecType R[],int s,int t) //一趟划分
{
int i=s,j=t;
RecType tmp=R[i]; //以R[i]为基准
while (i<j) //从两端交替向中间扫描,直至i=j为止
{ while (j>i && R[j].key>=tmp.key)
j--; //从右向左扫描,找一个小于tmp.key的R[j]
R[i]=R[j]; //找到这样的R[j],放入R[i]处
while (i<j && R[i].key<=tmp.key)
i++; //从左向右扫描,找一个大于tmp.key的R[i]
R[j]=R[i]; //找到这样的R[i],放入R[j]处
}
R[i]=tmp;
return i;
}
void QuickSort(RecType R[],int s,int t) //对R[s..t]的元素进行快速排序
{ int i;
RecType tmp;
if (s<t) //区间内至少存在两个元素的情况
{ count++;
i=partition(R,s,t);
DispList(R,10); //调试用
QuickSort(R,s,i-1); //对左区间递归排序
QuickSort(R,i+1,t); //对右区间递归排序
}
}
/*
int main()
{
int i,n=10;
RecType R[MAXL];
KeyType a[]={15,18,29,12,35,32,27,23,10,20};
CreateList(R,a,n);
printf("排序前:"); DispList(R,n);
QuickSort(R,0,n-1);
printf("排序后:"); DispList(R,n);
return 1;
}
*/
int main()
{
int i,n=10;
RecType R[MAXL];
KeyType a[]={6,8,7,9,0,1,3,2,4,5};
CreateList(R,a,n);
printf("排序前:"); DispList(R,n);
QuickSort(R,0,n-1);
printf("排序后:"); DispList(R,n);
printf("count=%d\n",count);
return 1;
}
你好