网站建设相关的,wordpress 文章行距,域名空间商,微信怎么开自己的公众号0. 简介 选择排序#xff08;Selection Sort#xff09;是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小#xff08;或最大#xff09;的一个元素#xff0c;存放在序列的起始位置#xff0c;直到全部待排序的数据元素排完。选择排序是不稳…0. 简介 选择排序Selection Sort是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。 1. 选择排序的实现
选择排序的基本思想
在未排序的序列中找到最小或最大的元素存放到排序序列的起始位置。再从剩余未排序的元素中继续寻找最小或最大的元素然后放到已排序的序列的末尾。以此类推直到所有元素均排序完毕。
选择排序过程演示 2. 选择排序时空间复杂度分析
选择排序的时间复杂度和空间复杂度如下 时间复杂度 无论数据状况如何选择排序都需要进行 n-1 趟选择每趟选择都需要进行 n-i 次比较i 是当前趟数所以总的时间复杂度是 O(n^2)。 空间复杂度 选择排序是原地排序只需要一个额外空间用于临时交换元素所以空间复杂度是 O(1)。
总结选择排序的时间复杂度是 O(n^2)空间复杂度是 O(1)。 3. 选择排序C语言代码
C代码实现
#include stdio.h void selectionSort(int arr[], int n) { int i, j, minIndex, temp; for (i 0; i n-1; i) { // 外层循环控制选择的趟数 minIndex i; // 记录最小值的索引初始化为当前趟的起始位置 for (j i1; j n; j) { // 内层循环在未排序的元素中查找最小值 if (arr[j] arr[minIndex]) { minIndex j; // 更新最小值的索引 } } // 交换找到的最小值与当前趟的起始位置的值 temp arr[minIndex]; arr[minIndex] arr[i]; arr[i] temp; }
} int main() { int arr[] {64, 34, 25, 12, 22, 11, 90}; // 待排序的数组 int n sizeof(arr)/sizeof(arr[0]); // 数组的长度 selectionSort(arr, n); // 对数组进行选择排序 printf(Sorted array: \n); for (int i0; i n; i) { // 输出排序后的数组 printf(%d , arr[i]); } printf(\n); return 0;
}
代码解释
selectionSort 函数接收一个整数数组和它的长度作为参数。外层循环负责保证选择的趟数。例如有7个数字就需要选择6趟。内层循环负责在未排序的元素中查找最小值。minIndex 用于记录当前找到的最小值的索引初始化为当前趟的起始位置。如果发现有更小的数就更新 minIndex。内层循环结束后我们已经找到了当前未排序部分的最小值然后将其与当前趟的起始位置的值进行交换。这样当前趟的起始位置就有了正确的值。外层循环继续进行直到所有元素都排好序。 4. 选择排序代码运行结果
代码运行结果
