???學院的保送研究生復試馬上就要開始了，復試中最能拉開距離的就是筆試，這也是我發揮個人能力的地方。為了萬無一失，我準備這幾天復習一下數據結構，今天復習的內容是排序算法。
???一般的排序算法大體上分為三類——插入排序、交換排序和選擇排序。
???插入排序的基本思想是將第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
}
?