C语言常见3种排序

主要是三种排序方法：冒泡排序、选择排序、插入排序。

文章目录

一、冒泡排序

1.代码：

2.工作原理： 

3.具体过程： 

二、选择排序

1.代码

2. 工作原理

3.具体过程：

三、插入排序 

1.代码

2.工作原理

3.具体过程

总结

---

一、冒泡排序

通过重复遍历待排序的列表，比较相邻元素并交换顺序错误的元素。(其名称源于较小的元素会像“气泡”一样逐渐“浮”到列表顶端。)

---

1.代码：

代码如下（示例）：

//冒泡排序
//从小到大
int main()
{int i = 0;//i表示趟数int j = 0;int a[5] = { 5,3,8,4,6 };for (i = 0; i < 5; i++)//至少4趟，这里也可以写成i<4{for (j = 0; j < 5-i-1; j++){if (a[j] > a[j + 1]){int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}}for (i = 0; i < 5; i++){printf("%d ", a[i]);}return 0;
}

2.工作原理： 

1. **比较相邻元素**：从列表的第一个元素开始，比较相邻的两个元素。
2. **交换元素**：如果顺序错误（如前一个元素大于后一个元素），则交换它们。
3. **重复遍历**：重复上述步骤，直到没有需要交换的元素，列表排序完成。 

3.具体过程： 

 1. **第一轮**：
   - 比较 5 和 3，交换，得 `[3, 5, 8, 4, 6]`
   - 比较 5 和 8，不交换
   - 比较 8 和 4，交换，得 `[3, 5, 4, 8, 6]`
   - 比较 8 和 6，交换，得 `[3, 5, 4, 6, 8]`
   - 第一轮结束，最大的元素 8 已“浮”到末尾。

2. **第二轮**：
   - 比较 3 和 5，不交换
   - 比较 5 和 4，交换，得 `[3, 4, 5, 6, 8]`
   - 比较 5 和 6，不交换
   - 第二轮结束，第二大的元素 6 已“浮”到倒数第二位。

3. **第三轮**：
   - 比较 3 和 4，不交换
   - 比较 4 和 5，不交换
   - 第三轮结束，列表已排序完成。

最终排序结果为 `[3, 4, 5, 6, 8]`。

### 时间复杂度
- **最坏情况**：O(n²)，列表完全逆序时。
- **平均情况**：O(n²)。
- **最好情况**：O(n)，列表已经有序时。

### 优点
- 实现简单。
- 对小规模数据有效。

### 缺点
- 效率低，尤其对大规模数据。
- 需要多次遍历和交换。

### 适用场景
适用于数据量小或对性能要求不高的场景。

---

二、选择排序

通过不断选择未排序部分的最小元素，并将其放到已排序部分的末尾。其核心思想是每次从未排序部分选出最小元素，与未排序部分的第一个元素交换。

---

1.代码

代码如下（示例）：

//选择排序
int main()
{int i = 0;//i表示趟数int j = 0;int a[5] = { 64,65,12,22,11 };for (i = 0; i < 5; i++)//选择排序次数{int min = i;//假设每一趟第一个元素是最小的for (j = i; j < 5 ; j++)//元素个数{if (a[min]>a[j]){min = j;	 }}int tmp = a[i];a[i] = a[min];a[min] = tmp;}for (i = 0; i < 5; i++){printf("%d ", a[i]);}return 0;
}

2. 工作原理

1. **找到最小元素**：在未排序部分中找到最小元素。
2. **交换元素**：将最小元素与未排序部分的第一个元素交换。
3. **重复步骤**：重复上述过程，直到所有元素排序完成。

3.具体过程：

1. **第一轮**：
   - 找到最小元素 11，与第一个元素 64 交换，得 `[11, 25, 12, 22, 64]`
   - 已排序部分为 `[11]`，未排序部分为 `[25, 12, 22, 64]`

2. **第二轮**：
   - 找到最小元素 12，与第一个元素 25 交换，得 `[11, 12, 25, 22, 64]`
   - 已排序部分为 `[11, 12]`，未排序部分为 `[25, 22, 64]`

3. **第三轮**：
   - 找到最小元素 22，与第一个元素 25 交换，得 `[11, 12, 22, 25, 64]`
   - 已排序部分为 `[11, 12, 22]`，未排序部分为 `[25, 64]`

4. **第四轮**：
   - 找到最小元素 25，已在正确位置，无需交换。
   - 已排序部分为 `[11, 12, 22, 25]`，未排序部分为 `[64]`

5. **第五轮**：
   - 最后一个元素 64 已在正确位置。
   - 最终排序结果为 `[11, 12, 22, 25, 64]`
 

### 时间复杂度
- **最坏情况**：O(n²)，列表完全逆序时。
- **平均情况**：O(n²)。
- **最好情况**：O(n²)，即使列表已经有序，仍需进行相同次数的比较。

### 优点
- 实现简单。
- 对小规模数据有效。

### 缺点
- 效率低，尤其对大规模数据。
- 需要多次遍历和交换。

### 适用场景
适用于数据量小或对性能要求不高的场景。

---

三、插入排序 

通过构建有序序列，逐步将未排序部分的元素插入到已排序部分的适当位置。其核心思想是将每个未排序元素插入到已排序部分的正确位置，直到所有元素排序完成。

---

1.代码

代码如下（示例）：

int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);// 插入排序（直接写在 main 里）for (int i = 1; i < n; i++) {int key = arr[i];  // 当前要插入的元素int j = i - 1;    // 已排序部分的最后一个位置// 把比 key 大的元素往后移while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;  // 插入到正确位置}// 输出排序后的数组printf("Sorted array: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

外层循环：从第 2 个元素（`i = 1`）开始遍历数组，因为第一个元素默认是“已排序”的。 

内层循环：从 `i - 1` 开始往前找，如果 `arr[j] > key`，就把 `arr[j]` 往后移一位。
                  直到找到 `arr[j] <= key` 的位置，然后把 `key` 插入到 `j + 1` 的位置。

---

2.工作原理

1. **初始状态**：将第一个元素视为已排序部分，其余元素为未排序部分。
2. **插入元素**：从未排序部分取出第一个元素，与已排序部分的元素从后向前比较，找到合适的位置插入。
3. **重复步骤**：重复上述过程，直到所有元素排序完成。

3.具体过程

1. **第一轮**：
   - 已排序部分为 `[12]`，未排序部分为 `[11, 13, 5, 6]`
   - 取出 11，与 12 比较，插入到 12 前面，得 `[11, 12, 13, 5, 6]`
   - 已排序部分为 `[11, 12]`，未排序部分为 `[13, 5, 6]`

2. **第二轮**：
   - 取出 13，与 12 比较，插入到 12 后面，得 `[11, 12, 13, 5, 6]`
   - 已排序部分为 `[11, 12, 13]`，未排序部分为 `[5, 6]`

3. **第三轮**：
   - 取出 5，与 13、12、11 比较，插入到 11 前面，得 `[5, 11, 12, 13, 6]`
   - 已排序部分为 `[5, 11, 12, 13]`，未排序部分为 `[6]`

4. **第四轮**：
   - 取出 6，与 13、12、11、5 比较，插入到 5 后面，得 `[5, 6, 11, 12, 13]`
   - 已排序部分为 `[5, 6, 11, 12, 13]`，未排序部分为空

### 时间复杂度
- **最坏情况**：O(n²)，列表完全逆序时。
- **平均情况**：O(n²)。
- **最好情况**：O(n)，列表已经有序时。

### 优点
- 实现简单。
- 对小规模数据或基本有序的数据有效。

### 缺点
- 效率低，尤其对大规模数据。
- 需要多次比较和移动。

### 适用场景
适用于数据量小或基本有序的数据集。

---

总结

主要是三种排序方法：冒泡排序、选择排序、插入排序。

以及它们的工作原理，具体的工作流程，时间复杂度空间复杂度和适用场景