"这篇文档介绍了三种常见的排序方法：选择排序、插入排序以及交换排序，包括它们的基本思想、时间复杂度和简单的C/C++程序实现。这些排序算法的时间复杂度都是O(n^2)，适用于小规模数据或部分有序的数据排序。"
### 选择排序
选择排序是一种简单直观的排序算法。其基本思想是在每一轮排序中，从未排序的元素中找到最小（或最大）的元素，将其放到已排序序列的末尾。这个过程会重复n-1次，直到所有元素都有序。由于在排序过程中可能会改变相同元素的相对顺序，所以选择排序是不稳定的排序方法。其时间复杂度为O(n^2)。
```c
void selection_sort(int r[], int n) {
int i, j, min_idx;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++) {
if (r[j] < r[min_idx]) {
min_idx = j;
}
}
if (min_idx != i) {
int temp = r[i];
r[i] = r[min_idx];
r[min_idx] = temp;
}
}
}
```
### 插入排序
插入排序分为直接插入排序和二分插入排序。直接插入排序是将每个元素插入到已排序序列的正确位置，每趟排序后，未排序部分的元素减少一个。而二分插入排序则在插入时利用二分查找，提高插入效率。两种插入排序的时间复杂度也是O(n^2)。
```c
// 直接插入排序
void insert_sort(int r[], int n) {
int i, j, t;
for (i = 1; i < n; i++) {
t = r[i];
j = i - 1;
while (j >= 0 && r[j] > t) {
r[j + 1] = r[j];
j--;
}
r[j + 1] = t;
}
}
// 二分插入排序
void binary_insert_sort(int r[], int n) {
int i, low, mid, high, t;
for (i = 1; i < n; i++) {
t = r[i];
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (t < r[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (j = i - 1; j >= low; j--) {
r[j + 1] = r[j];
}
r[low] = t;
}
}
```
### 交换排序
交换排序中最典型的是冒泡排序，通过不断比较相邻元素并交换，使得每一轮排序后最大的元素“浮”到数组的末尾。同样，冒泡排序的时间复杂度为O(n^2)。
```c
// 冒泡排序
void bubble_sort(int r[], int n) {
int i, j, t;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (r[j] > r[j + 1]) {
t = r[j];
r[j] = r[j + 1];
r[j + 1] = t;
}
}
}
}
```
以上就是选择排序、插入排序（直接插入与二分插入）以及交换排序（冒泡排序）的基本概念、时间复杂度和C/C++实现。这三种排序算法都属于基础排序，虽然在最坏情况下时间复杂度较高，但它们的实现简单，易于理解，对于小规模数据或者部分有序的数据，表现还是可以接受的。
我的内容管理
展开
