学院的保送研究生复试马上就要开始了，复试中最能拉开距离的就是笔试，这也是我发挥个人能力的地方。为了万无一失，我准备这几天复习一下数据结构，今天复习的内容是排序算法。
一般的排序算法大体上分为三类——插入排序、交换排序和选择排序。
插入排序的基本思想是将第N个记录插入到前面(N-1)个有序的记录当中。直接插入排序、折半插入排序和系尔排序都是属于插入排序。
直接插入排序：
1
void
InsertSort(RcdType r[],
int
n)
2
{
3
int
i,j;
4
for
(i
=
2
;i
<=
n;i
++
)
{
5
r[
0
]
=
r[i];
6
j
=
i
-
1
;
7
while
(r[
0
].key
<
r[j].key)
{
8
r[j
+
1
]
=
r[j];
9
j
--
;
10
}
11
r[j
+
1
]
=
r[
0
];
12
}
13
}
折半插入排序：
1
void
BinSort(RcdType r[],
int
n)
2
{
3
int
i,j,mid,low,high;
4
for
(i
=
2
;i
<=
n;i
++
)
{
5
r[
0
]
=
r[i];
6
low
=
1
;
7
high
=
i
-
1
;
8
while
(low
<=
high)
{
9
mid
=
(low
+
high)
/
2
;
10
if
(r[
0
].key
<
r[mid].key) high
=
mid
-
1
;
11
else
low
=
mid
+
1
;
12
}
13
for
(j
=
i
-
1
;j
>=
low;j
--
)
14
r[j
+
1
]
=
r[j];
15
r[low]
=
r[
0
];
16
}
17
}
交换排序算法的基本思想是按照某种顺序比较两个记录的关键字大小，然后根据需要交换两个记录的位置。冒泡排序和快速排序都是属于交换排序。
冒泡排序：
1
void
BubbleSort(RcdType r[],
int
n)
2
{
3
int
i,j,flag;
4
for
(i
=
1
;i
<
n;i
++
)
{
5
flag
=
1
;
6
for
(j
=
1
;j
<=
n
-
i;j
++
)
{
7
if
(r[j
+
1
].key
<
r[j].key)
{
8
falg
=
0
;
9
r[
0
]
=
r[j];
10
r[j]
=
r[j
+
1
];
11
r[j
+
1
]
=
r[
0
];
12
}
13
}
14
if
(flag)
break
;
15
}
16
}
快速排序：
1
void
QuickSort(RcdType r[],
int
low,
int
high)
2
{
3
int
i,j;
4
i
=
low;
5
j
=
high;
6
r[
0
]
=
r[i];
7
while
(i
<
j)
{
8
while
(i
<
j
&&
r[j].key
>=
r[
0
].key) j
--
;
9
if
(i
<
j) r[i
++
]
=
r[j];
10
while
(i
<
j
&&
r[i].key
<=
r[
0
].key) i
++
;
11
if
(i
<
j) r[j
--
]
=
r[
0
];
12
}
13
r[i]
=
r[
0
];
14
if
(low
<
i
-
1
) QuickSort(r,low,i
-
1
);
15
if
(high
>
i
+
1
) QuickSort(r,i
+
1
,high);
16
}
选择排序算法的思想是根据某中方法选择一个关键字最大的记录或者关键字最小的记录，放到适当的位置。简单选择排序和堆排序都是属于选择排序算法。
简单选择排序：
1
void
SelectSort(RcdType r[],
int
n)
2
{
3
int
i,j,p;
4
for
(i
=
1
;i
<
n;i
++
)
{
5
p
=
i;
6
for
(j
=
i
+
1
;j
<=
n;j
++
)
{
7
if
(r[j].key
<
r[p].key) p
=
j;
8
}
9
if
(p
!=
i)
{
10
r[
0
]
=
r[p];
11
r[p]
=
r[i];
12
r[i]
=
r[
0
];
13
}
14
}
15
}
堆排序：
1
void
Heap(RcdType r[],
int
i,
int
m)
2
{
3
int
j;
4
j
=
2
*
i;
5
r[
0
]
=
r[i];
6
while
(j
<=
m)
{
7
if
(j
<
m
&&
r[j
+
1
].key
<
r[j].key) j
++
;
8
if
(r[j].key
<
r[
0
].key)
{
9
r[i]
=
r[j];
10
i
=
j;
11
j
=
i
*
2
;
12
}
else
{
13
j
=
m
+
1
;
14
}
15
}
16
r[i]
=
r[
0
];
17
}
18
19
void
HeapSort(RcdType r[],
int
n)
20
{
21
int
i,j;
22
//
初始化堆
23
for
(i
=
n
/
2
;i
>=
1
;i
--
)
{
24
Heap(r,i,n);
25
}
26
//
输出
27
for
(i
=
n;i
>=
1
;i
--
)
{
28
printf(
"
%d\t
"
,r[
1
].key);
29
r[
1
]
=
r[i];
30
Heap(r,
1
,i
-
1
);
31
}
32
}