网站每天更新的内容是内链吗,台州网页设计公司,品牌设计网站怎么做,健康网站建设与管理大家好#xff0c;今天我们来聊聊选择排序#xff08;Selection Sort#xff09;算法。这是一个非常简单的排序算法#xff0c;适合用来学习排序的基本思路和操作。选择排序在许多排序算法中以其直观和易于实现的特点著称#xff0c;虽然它的效率不如其他高效算法#xf…大家好今天我们来聊聊选择排序Selection Sort算法。这是一个非常简单的排序算法适合用来学习排序的基本思路和操作。选择排序在许多排序算法中以其直观和易于实现的特点著称虽然它的效率不如其他高效算法如快速排序和归并排序但它仍然是学习和理解排序算法的一个很好的起点。
一、什么是选择排序
选择排序是一种简单的排序算法其基本思想是每次从未排序的部分中选出最小的元素将它与未排序部分的第一个元素交换位置。这样每一轮选择都会将一个最小元素放到数组的前面直到整个数组排序完成。
选择排序的步骤
从数组的第一个元素开始假设当前元素为最小值。从剩余的未排序部分中找到最小的元素。如果找到的最小元素小于当前元素交换它们的位置。将未排序部分的最小元素交换到当前元素的位置。继续对剩余部分进行选择排序直到整个数组有序。
二、选择排序的工作原理
假设我们有一个数组 [64, 34, 25, 12, 22, 11, 90]我们来演示一下选择排序的过程 第一轮选择 假设 64 是最小的元素遍历数组的剩余部分找到最小值 11与 64 交换得到 [11, 34, 25, 12, 22, 64, 90]。 第二轮选择 假设 34 是最小的元素遍历剩余部分找到最小值 12与 34 交换得到 [11, 12, 25, 34, 22, 64, 90]。 第三轮选择 假设 25 是最小的元素遍历剩余部分找到最小值 22与 25 交换得到 [11, 12, 22, 34, 25, 64, 90]。 第四轮选择 假设 34 是最小的元素遍历剩余部分找到最小值 25与 34 交换得到 [11, 12, 22, 25, 34, 64, 90]。 第五轮选择 假设 34 是最小的元素遍历剩余部分找到最小值 34不需要交换得到 [11, 12, 22, 25, 34, 64, 90]。 第六轮选择 假设 64 是最小的元素遍历剩余部分找到最小值 64不需要交换得到 [11, 12, 22, 25, 34, 64, 90]。 第七轮选择 最后剩下的元素是 90它已经排到最后不需要交换。
最终排序后的数组为 [11, 12, 22, 25, 34, 64, 90]。
三、选择排序的时间复杂度
选择排序的时间复杂度是 O(n²)其中 n 是数组的元素数量。原因如下
每一轮需要遍历未排序部分的所有元素找到最小的元素并交换它。第一轮遍历需要 n-1 次比较第二轮需要 n-2 次比较依此类推总共需要 n(n-1)/2 次比较。由于这是一种双重循环结构因此其时间复杂度为 O(n²)。
最好情况
即使数组已经有序选择排序仍然会进行完整的遍历时间复杂度仍然是 O(n²)。
最坏情况
当数组是逆序时选择排序依然需要进行完整的遍历时间复杂度为 O(n²)。
四、选择排序的空间复杂度
选择排序是原地排序算法它只需要常数级的额外空间来存储临时变量用于交换元素。因此它的空间复杂度为 O(1)。
下面是一个用 Java 实现的选择排序代码
public static void selectsort(int[] arr) {int index 0;int max arr[index];for (int j 0; j arr.length - 1; j) {//循环一次选择一个最大值for (int i 1; i arr.length - j; i) {index arr[i] max ? i : index;max arr[index];}//交换最大值与未排序元素的最后一个swap(arr, index, arr.length - j - 1);//注意重置最大值与索引index 0;max arr[index];}}public static void swap(int[] arr, int a, int b) {int temp arr[a];arr[a] arr[b];arr[b] temp;}
输入数组 {64, 34, 25, 12, 22, 11, 90}程序的输出是
11 12 22 25 34 64 90
