网上书城网站开发说明书,备案ip 查询网站查询网站查询,响应式网站怎样做,淘客网站让别人做#x1f345;关注博主#x1f397;️ 带你畅游技术世界#xff0c;不错过每一次成长机会#xff01; #x1f4d9;C 语言百万年薪修炼课程 通俗易懂#xff0c;深入浅出#xff0c;匠心打磨#xff0c;死磕细节#xff0c;6年迭代#xff0c;看过的人都说好。 文章目… 关注博主️ 带你畅游技术世界不错过每一次成长机会 C 语言百万年薪修炼课程 通俗易懂深入浅出匠心打磨死磕细节6年迭代看过的人都说好。 文章目录 如何在 C 语言中进行选择排序一、选择排序的基本思想二、选择排序的算法步骤三、选择排序的 C 语言实现四、选择排序的时间复杂度和空间复杂度分析一时间复杂度二空间复杂度 五、选择排序的稳定性六、选择排序的适用场景七、选择排序与其他排序算法的比较一与冒泡排序的比较二与插入排序的比较三与快速排序的比较 八、示例分析九、优化思路一减少交换次数二利用已排序部分的信息 十、总结 如何在 C 语言中进行选择排序
选择排序Selection Sort是一种简单直观的排序算法。它首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。 一、选择排序的基本思想
遍历整个数组找出最小的元素。将最小的元素与数组的第一个元素交换位置。在剩余的未排序元素中重复上述步骤直到整个数组都被排序。 二、选择排序的算法步骤
以下是选择排序的详细步骤
假设要对数组 arr[] 进行排序数组的长度为 n
从数组的第一个元素开始即 i 0 。对于每个 i从 i 1 到 n - 1 中找到最小的元素并记录其索引 min_index 。如果 min_index 不等于 i则交换 arr[i] 和 arr[min_index] 。增加 i重复步骤 2 和 3直到 i n - 2 。 三、选择排序的 C 语言实现
#include stdio.h// 交换两个元素的值
void swap(int* a, int* b) {int temp *a;*a *b;*b temp;
}// 选择排序函数
void selectionSort(int arr[], int n) {int i, j, min_index;for (i 0; i n - 1; i) {min_index i;for (j i 1; j n; j)if (arr[j] arr[min_index])min_index j;if (min_index! i)swap(arr[i], arr[min_index]);}
}// 打印数组函数
void printArray(int arr[], int size) {for (int i 0; i size; i)printf(%d , arr[i]);printf(\n);
}// 测试案例
int main() {int arr[] {64, 25, 12, 22, 11};int n sizeof(arr) / sizeof(arr[0]);printf(排序前的数组为: );printArray(arr, n);selectionSort(arr, n);printf(排序后的数组为: );printArray(arr, n);return 0;
}在上述代码中我们首先定义了一个 swap 函数用于交换两个元素的值。
selectionSort 函数实现了选择排序的逻辑。外层循环控制排序的轮数内层循环用于在每一轮中找到最小的元素。
printArray 函数用于打印数组的元素。
在 main 函数中我们创建了一个待排序的数组并调用相应的函数进行排序和打印。 四、选择排序的时间复杂度和空间复杂度分析
一时间复杂度
选择排序的平均时间复杂度和最坏时间复杂度都为 O(n^2)。这是因为无论数组的初始状态如何对于每个元素都需要进行比较和交换操作总共需要进行 n - 1 轮比较和交换每一轮比较和交换的操作数量都与数组的长度 n 成正比。
二空间复杂度
选择排序的空间复杂度为 O(1)。因为它只在交换元素时使用了固定的额外空间而不需要额外的数组或其他数据结构来存储数据。 五、选择排序的稳定性
选择排序是一种不稳定的排序算法。这是因为在选择最小元素并与当前位置交换时如果有两个相同的元素它们的相对顺序可能会发生改变。
例如对于数组 [5, 5, 2]第一次选择最小元素 2 并与第一个位置的 5 交换得到 [2, 5, 5]两个 5 的相对顺序发生了变化。 六、选择排序的适用场景
选择排序适用于小型数据集或者对算法的简单性要求较高的场景。由于其时间复杂度较高在处理大型数据集时性能通常不如其他更高效的排序算法如快速排序、归并排序等。 七、选择排序与其他排序算法的比较
一与冒泡排序的比较
选择排序和冒泡排序都是简单的排序算法它们的时间复杂度都为 O(n^2)。然而在每一轮的操作中冒泡排序需要进行多次相邻元素的比较和交换而选择排序只需要进行一次最小元素的选择和交换。因此在通常情况下选择排序的性能略优于冒泡排序。
二与插入排序的比较
插入排序在对于近乎有序的数组时性能较好其平均时间复杂度可以接近 O(n)。而选择排序无论数组的初始状态如何时间复杂度都为 O(n^2)。因此在数组近乎有序的情况下插入排序更优。
三与快速排序的比较
快速排序的平均时间复杂度为 O(nlogn)是一种效率很高的排序算法。与选择排序相比快速排序在处理大型数据集时具有明显的优势。 八、示例分析
让我们通过一个具体的示例来详细分析选择排序的过程。
假设有数组 [9, 5, 7, 2, 6]
第一轮
初始状态[9, 5, 7, 2, 6]首先假设第一个元素 9 是最小的然后从第二个元素开始比较。经过比较发现 2 是最小的所以将 2 与 9 交换位置。第一轮结束后数组变为 [2, 5, 7, 9, 6]
第二轮
此时从第二个元素开始假设 5 是最小的。比较剩余元素发现没有比 5 更小的所以位置不变。第二轮结束后数组仍为 [2, 5, 7, 9, 6]
第三轮
从第三个元素开始假设 7 是最小的。比较剩余元素发现 6 更小所以将 6 与 7 交换位置。第三轮结束后数组变为 [2, 5, 6, 9, 7]
第四轮
从第四个元素开始假设 9 是最小的。比较剩余元素发现 7 更小所以将 7 与 9 交换位置。第四轮结束后数组变为 [2, 5, 6, 7, 9]排序完成。
通过这个示例我们可以清晰地看到选择排序每一轮的操作过程以及如何逐步将数组排序。 九、优化思路
虽然选择排序的基本算法已经比较简单直接但在某些情况下仍然可以考虑一些优化思路
一减少交换次数
在找到最小元素的索引后先不立即进行交换而是在一轮比较结束后如果最小元素的索引与当前位置不同再进行一次交换。这样可以在一定程度上减少交换的次数特别是在数组中元素重复较多的情况下。
二利用已排序部分的信息
在后续的轮次中可以利用已经排序好的部分缩小搜索最小元素的范围。但这种优化在选择排序中效果可能不太显著因为选择排序的核心思想是每次选择未排序部分的最小元素。 十、总结
选择排序是一种简单但效率相对较低的排序算法。它的优点是实现简单易于理解空间复杂度低。缺点是时间复杂度较高在处理大规模数据时性能不佳。在实际应用中应根据具体情况选择合适的排序算法。如果数据量较小或者对算法的简单性要求较高选择排序可以是一个可行的选择。但对于大规模数据的排序通常会优先考虑更高效的排序算法如快速排序、归并排序等。 相关推荐
C 语言百万年薪修炼课程 通俗易懂深入浅出匠心打磨死磕细节6年迭代看过的人都说好。博客首页-关注博主️ 带你畅游技术世界不错过每一次成长机会CSDN专栏-C语言修炼技术社区-墨松科技
