### 数据结构课程各种排序算法比较
#### 插入排序（Insertion Sort）
**基本思想**：
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
**排序过程**：
以数组`[49, 38, 65, 97, 76, 13, 27, 49]`为例：
- 初始化：`[49] 38 65 97 76 13 27 49`
- 第一次插入：`[38, 49] 65 97 76 13 27 49`
- 第二次插入：`[38, 49, 65] 97 76 13 27 49`
- ……
- 最终排序结果：`[13, 27, 38, 49, 49, 65, 76, 97]`
**伪代码**：
```pascal
Procedure InsertSort(Var R: FileType);
// 对R[1..N]按递增序进行插入排序,R[0]是监视哨 //
Begin
for I := 2 to N do // 依次插入R[2],...,R[n] //
begin
R[0] := R[I]; J := I - 1;
while R[0] < R[J] do // 查找R[I]的插入位置 //
begin
R[J + 1] := R[J]; // 将大于R[I]的元素后移 //
J := J - 1;
end;
R[J + 1] := R[0]; // 插入R[I] //
end;
End; // InsertSort //
```
#### 选择排序（Selection Sort）
**基本思想**：
选择排序是在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，直到所有元素均排序完毕。
**排序过程**：
以数组`[49, 38, 65, 97, 76, 13, 27, 49]`为例：
- 第一次选择：`13 [38, 65, 97, 76, 27, 49, 49]`
- 第二次选择：`13, 27 [38, 65, 97, 76, 49, 49]`
- 第三次选择：`13, 27, 38 [65, 97, 76, 49, 49]`
- ……
- 最终排序结果：`[13, 27, 38, 49, 49, 65, 76, 97]`
**伪代码**：
```pascal
Procedure SelectSort(Var R: FileType); // 对R[1..N]进行直接选择排序 //
Begin
for I := 1 to N - 1 do // 做N-1趟选择排序 //
begin
K := I;
for J := I + 1 to N do
// 在当前无序区R[I..N]中选最小的元素R[K] //
begin
if R[J] < R[K] then K := J;
end;
if K <> I then // 交换R[I]和R[K] //
begin
Temp := R[I];
R[I] := R[K];
R[K] := Temp;
end;
end;
End; // SelectSort //
```
#### 冒泡排序（Bubble Sort）
**基本思想**：
冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
**排序过程**：
以数组`[49, 38, 65, 97, 76, 13, 27, 49]`为例：
- 第一次冒泡：`[13, 27, 38, 49, 49, 65, 76, 97]`
- 第二次冒泡：`[13, 27, 38, 49, 49, 65, 76, 97]`
- 第三次冒泡：`[13, 27, 38, 49, 49, 65, 76, 97]`
- ……
- 最终排序结果：`[13, 27, 38, 49, 49, 65, 76, 97]`
**伪代码**：
```pascal
Procedure BubbleSort(Var R: FileType) // 从下往上扫描的冒泡排序 //
Begin
for I := 1 to N - 1 do // 做N-1趟排序 //
begin
NoSwap := True; // 置未排序的标志 //
for J := N - 1 downto 1 do // 从底部往上扫描 //
begin
if R[J + 1] < R[J] then // 交换元素 //
begin
Temp := R[J + 1];
R[J + 1] := R[J];
R[J] := Temp;
NoSwap := False;
end;
end;
if NoSwap then Return; // 本趟排序中未发生交换，则终止算法 //
end;
End; // BubbleSort //
```
#### 计数排序（Counting Sort）
**基本思想**：
计数排序适用于一定范围内的整数排序。它利用一个额外的数组`C`来记录每个整数出现的次数。然后根据这些信息将原数组`A`排序。
**实现过程**：
假设要排序的数组`A = [4, 2, 2, 8, 3, 3, 1]`，其中数字范围为`1~8`。
- 初始化数组`C = [0, 0, 0, 0, 0, 0, 0, 0]`。
- 统计`A`中各数字出现的次数，并更新`C`。
- 重新构建排序后的数组。
#### 快速排序（Quick Sort）
**基本思想**：
快速排序使用分治法策略来把一个序列分为较小和较大的两个子序列。具体来说，选择一个“基准”元素，通过一趟排序将待排记录分割成独立的两部分，其中一部分的所有记录都比另一部分的所有记录都要小，然后再按此方法对这两部分分别进行快速排序，整个排序过程可以递归进行。
**排序过程**：
以数组`[49, 38, 65, 97, 76, 13, 27, 49]`为例：
- 选择基准元素`49`。
- 比`49`小的元素移到左边：`[38, 13, 27, 49] 49 [65, 97, 76, 49]`
- 递归地处理左右两边的子数组。
- 最终排序结果：`[13, 27, 38, 49, 49, 65, 76, 97]`
以上几种排序算法各有特点，插入排序和冒泡排序的时间复杂度较高，但它们的实现相对简单；选择排序和计数排序在特定场景下表现较好；而快速排序作为一种高效的排序算法，在大多数情况下都能取得很好的效果。
