一、什么是选择排序选择排序Selection Sort是一种简单直观的排序算法它的核心思想是每次从未排序的部分中找到最小或最大的元素放到已排序部分的末尾重复这个过程直到所有元素排序完成。简单来说选择排序就像按身高排队先从所有人里找到最矮的站到队伍最前面再从剩下的人里找到最矮的站到已排好的队伍后面重复这个过程直到所有人都排好。二、选择排序的核心步骤选择排序的核心步骤可以分为以下几步遍历未排序部分从第一个元素开始遍历整个数组找到最小值下标在未排序的部分中找到最小值的下标交换位置将最小值与当前遍历位置的元素交换重复继续遍历下一个位置直到所有元素排序完成。三、选择排序的代码实现1. 基础版本#include stdio.h // 交换两个元素 void swap(int* a, int* b) { int temp *a; *a *b; *b temp; } // 选择排序 void selectionSort(int arr[], int n) { for (int i 0; i n - 1; i) { int minIndex i; // 记录最小值的下标 // 遍历未排序部分找到最小值 for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } // 交换当前位置与最小值位置的元素 swap(arr[i], arr[minIndex]); } } // 打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 2, 6, 1, 4, 3}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); selectionSort(arr, n); printf(排序后); printArray(arr, n); // 输出1 2 3 4 5 6 return 0; }2. 优化版本同时找最小值和最大值可以同时找到最小值和最大值减少遍历次数#include stdio.h // 交换两个元素 void swap(int* a, int* b) { int temp *a; *a *b; *b temp; } // 优化的选择排序同时找最小值和最大值 void optimizedSelectionSort(int arr[], int n) { int left 0, right n - 1; while (left right) { int minIndex left; int maxIndex right; // 遍历找到最小值和最大值的下标 for (int i left; i right; i) { if (arr[i] arr[minIndex]) { minIndex i; } if (arr[i] arr[maxIndex]) { maxIndex i; } } // 交换最小值到左边 swap(arr[left], arr[minIndex]); // 如果最大值在left位置交换后需要更新maxIndex if (maxIndex left) { maxIndex minIndex; } // 交换最大值到右边 swap(arr[right], arr[maxIndex]); // 缩小未排序部分的范围 left; right--; } } // 打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 2, 6, 1, 4, 3}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); optimizedSelectionSort(arr, n); printf(排序后); printArray(arr, n); // 输出1 2 3 4 5 6 return 0; }四、选择排序的时间复杂度和空间复杂度时间复杂度O (n²)因为需要两层循环每层循环的时间复杂度都是 O (n)空间复杂度O (1)只需要常数级别的额外空间稳定性不稳定因为交换操作可能会改变相同元素的相对位置。五、选择排序的优缺点优点实现简单代码逻辑清晰容易理解和实现空间复杂度低不需要额外的内存空间交换次数少最多进行 n-1 次交换适合交换成本高的场景。缺点时间复杂度高O (n²)不适合大规模数据排序不稳定可能会改变相同元素的相对位置效率低即使数组已经有序仍然需要 O (n²) 的时间复杂度。六、选择排序的实际应用场景选择排序虽然效率不高但在以下场景中仍然有用小规模数据排序当数据量较小时选择排序的实现简单性能可以接受交换成本高的场景比如排序的元素是大型对象交换操作成本高选择排序的交换次数少更适合教学和学习选择排序是理解排序算法的基础适合初学者学习排序的基本思想。七、总结选择排序是一种简单直观的排序算法它的核心思想是每次从未排序的部分中找到最小或最大的元素放到已排序部分的末尾重复这个过程直到所有元素排序完成。选择排序的时间复杂度是 O (n²)空间复杂度是 O (1)虽然效率不高但实现简单交换次数少适合小规模数据排序和教学学习。希望这篇文章能帮助你理解选择排序的原理和实现 8.选择排序：最直白的排序算法
一、什么是选择排序选择排序Selection Sort是一种简单直观的排序算法它的核心思想是每次从未排序的部分中找到最小或最大的元素放到已排序部分的末尾重复这个过程直到所有元素排序完成。简单来说选择排序就像按身高排队先从所有人里找到最矮的站到队伍最前面再从剩下的人里找到最矮的站到已排好的队伍后面重复这个过程直到所有人都排好。二、选择排序的核心步骤选择排序的核心步骤可以分为以下几步遍历未排序部分从第一个元素开始遍历整个数组找到最小值下标在未排序的部分中找到最小值的下标交换位置将最小值与当前遍历位置的元素交换重复继续遍历下一个位置直到所有元素排序完成。三、选择排序的代码实现1. 基础版本#include stdio.h // 交换两个元素 void swap(int* a, int* b) { int temp *a; *a *b; *b temp; } // 选择排序 void selectionSort(int arr[], int n) { for (int i 0; i n - 1; i) { int minIndex i; // 记录最小值的下标 // 遍历未排序部分找到最小值 for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } // 交换当前位置与最小值位置的元素 swap(arr[i], arr[minIndex]); } } // 打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 2, 6, 1, 4, 3}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); selectionSort(arr, n); printf(排序后); printArray(arr, n); // 输出1 2 3 4 5 6 return 0; }2. 优化版本同时找最小值和最大值可以同时找到最小值和最大值减少遍历次数#include stdio.h // 交换两个元素 void swap(int* a, int* b) { int temp *a; *a *b; *b temp; } // 优化的选择排序同时找最小值和最大值 void optimizedSelectionSort(int arr[], int n) { int left 0, right n - 1; while (left right) { int minIndex left; int maxIndex right; // 遍历找到最小值和最大值的下标 for (int i left; i right; i) { if (arr[i] arr[minIndex]) { minIndex i; } if (arr[i] arr[maxIndex]) { maxIndex i; } } // 交换最小值到左边 swap(arr[left], arr[minIndex]); // 如果最大值在left位置交换后需要更新maxIndex if (maxIndex left) { maxIndex minIndex; } // 交换最大值到右边 swap(arr[right], arr[maxIndex]); // 缩小未排序部分的范围 left; right--; } } // 打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 2, 6, 1, 4, 3}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); optimizedSelectionSort(arr, n); printf(排序后); printArray(arr, n); // 输出1 2 3 4 5 6 return 0; }四、选择排序的时间复杂度和空间复杂度时间复杂度O (n²)因为需要两层循环每层循环的时间复杂度都是 O (n)空间复杂度O (1)只需要常数级别的额外空间稳定性不稳定因为交换操作可能会改变相同元素的相对位置。五、选择排序的优缺点优点实现简单代码逻辑清晰容易理解和实现空间复杂度低不需要额外的内存空间交换次数少最多进行 n-1 次交换适合交换成本高的场景。缺点时间复杂度高O (n²)不适合大规模数据排序不稳定可能会改变相同元素的相对位置效率低即使数组已经有序仍然需要 O (n²) 的时间复杂度。六、选择排序的实际应用场景选择排序虽然效率不高但在以下场景中仍然有用小规模数据排序当数据量较小时选择排序的实现简单性能可以接受交换成本高的场景比如排序的元素是大型对象交换操作成本高选择排序的交换次数少更适合教学和学习选择排序是理解排序算法的基础适合初学者学习排序的基本思想。七、总结选择排序是一种简单直观的排序算法它的核心思想是每次从未排序的部分中找到最小或最大的元素放到已排序部分的末尾重复这个过程直到所有元素排序完成。选择排序的时间复杂度是 O (n²)空间复杂度是 O (1)虽然效率不高但实现简单交换次数少适合小规模数据排序和教学学习。希望这篇文章能帮助你理解选择排序的原理和实现