排序方法
冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行，直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤:
比较相邻元素: 从第一个元素开始，比较相邻的元素，如果第一个比第二个大（升序排序）或者小（降序排序），就交换它们的位置。
重复步骤 1: 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（升序）或最小（降序）的数。
缩小范围: 忽略已经排序好的最后一个元素，重复步骤 1 和 2，直到没有任何一对数字需要比较。
示例 (升序排序):
假设要排序的数组是 [5, 1, 4, 2, 8]
第一轮:
[5, 1]->[1, 5][5, 4]->[4, 5][5, 2]->[2, 5][5, 8]->[5, 8]
结果:[1, 4, 2, 5, 8]
第二轮:
[1, 4]->[1, 4][4, 2]->[2, 4][4, 5]->[4, 5]
结果:[1, 2, 4, 5, 8]
第三轮:
[1, 2]->[1, 2][2, 4]->[2, 4]
结果:[1, 2, 4, 5, 8]
第四轮:
[1, 2]->[1, 2]
结果:[1, 2, 4, 5, 8]
C代码实现 (升序):
#include <stdio.h>
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) { // 外层循环控制排序轮数
for (int j = 0; j < n - 1 - i; j++) { // 内层循环控制每轮比较次数
if (arr[j] > arr[j + 1]) { // 如果当前元素大于下一个元素
int temp = arr[j]; // 交换两个元素
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
关键点:
- 外层循环控制轮数，总共需要
n-1轮。 - 内层循环控制每轮的比较次数，随着轮数增加，比较次数减少。
n - 1 - i避免了对已经排好序的元素进行不必要的比较。
改进:
可以添加一个标志位，如果在一轮比较中没有进行任何交换，说明数组已经有序，可以提前结束排序。
希望这个解释能够帮助你理解冒泡排序。
选择排序
（Selection Sort）是一种简单直观的排序算法。它的工作原理是每次从未排序的部分中找到最小（或最大）的元素，然后将其与未排序部分的第一个元素交换位置。重复这个过程，直到整个数组排序完成。
算法步骤:
找到最小元素: 从未排序部分的第一个元素开始，遍历剩余未排序的元素，找到其中最小的元素。
交换位置: 将找到的最小元素与未排序部分的第一个元素交换位置。
缩小未排序部分: 将未排序部分的起始位置向后移动一位。
重复步骤 1-3: 重复上述步骤，直到整个数组排序完成。
示例 (升序排序):
假设要排序的数组是 [64, 25, 12, 22, 11]
第一轮:
- 未排序部分:
[64, 25, 12, 22, 11] - 最小元素:
11 - 交换:
[11, 25, 12, 22, 64]
第二轮:
- 未排序部分:
[25, 12, 22, 64] - 最小元素:
12 - 交换:
[11, 12, 25, 22, 64]
第三轮:
- 未排序部分:
[25, 22, 64] - 最小元素:
22 - 交换:
[11, 12, 22, 25, 64]
第四轮:
- 未排序部分:
[25, 64] - 最小元素:
25 - 交换:
[11, 12, 22, 25, 64]
C 代码实现 (升序):
#include <stdio.h>
void selection_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i; // 假设当前位置的元素是最小的
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j; // 更新最小元素的索引
}
}
// 交换最小元素和当前位置的元素
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selection_sort(arr, n);
printf("排序后的数组: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
关键点:
- 外层循环控制已排序部分的末尾位置。
- 内层循环在未排序部分中查找最小元素。
- 每次交换都将一个元素放入其最终的排序位置。
时间复杂度: O(n^2) - 无论数组是否有序，都需要进行 n*(n-1)/2 次比较。
空间复杂度: O(1) - 选择排序是原地排序算法，只需要常数个额外空间。
希望这个解释能够帮助你理解选择排序。