共计 2722 个字符，预计需要花费 7 分钟才能阅读完成。
大家好，我是易安！
明天咱们开始每日一算的篇章，明天带来的是抉择算法。
抉择排序 是一种简略而高效的排序算法，它通过从列表的未排序局部中反复抉择最小（或最大）元素并将其挪动到列表的已排序局部来工作。该算法重复从列表的未排序局部中抉择最小（或最大）的元素，并将其与未排序局部的第一个元素替换。对列表中残余的未排序局部反复此过程，直到整个列表排序结束。抉择排序的一种变体称为“双向选择排序”，它通过在最小元素和最大元素之间交替遍历元素列表，这种形式在某些状况下能够更快。
抉择排序算法
该算法在给定数组中保护两个子数组。
- 曾经排序的子数组。
- 残余的子数组未排序。
在抉择排序的每次迭代中，从未排序的子数组中选取最小元素（思考升序）并将其挪动到已排序子数组的结尾。
每次迭代后，已排序的子数组大小减少一，未排序的子数组大小缩小一。
在 N（数组的大小）次迭代之后，咱们将失去一个排序的数组。
抉择排序流程图：
抉择排序原理？
让咱们以上面的数组为例：arr[] = {64, 25, 12, 22, 11}
第一步：
- 对于排序数组中的第一个地位，整个数组从索引 0 到 4 顺次遍历。以后寄存 64的第一个地位，遍历整个数组后显然 11 是最低值。
64 25 12 22 11
- 因而，将 64 替换为 11。通过一次迭代后，恰好是数组中最小值的 11 往往会呈现在排序列表的第一个地位。
11 25 12 22 64 第二步：
- 对于存在 25 的第二个地位，再次按程序遍历数组的其余部分。
11 25 12 22 64
- 遍历后发现 12 是数组中倒数第二的值，应该呈现在数组的第二位，因而替换这些值。
11 12 25 22 64 第三步：
- 当初，对于第三位，再次出现 25 的 中央遍历数组的其余部分并找到数组中第三小的值。
11 12 25 22 64
- 遍历时，22是第三小的值，它应该呈现在数组的第三位，因而将 22 与第三位的元素替换。
11 12 22 25 64 第四步：
- 同样，对于第四个地位，遍历数组的其余部分，找到数组中第四小的元素
- 因为 25 是第四低的值，因而它将排在第四位。
11 12 22 25 64 第五步：
- 最初，数组中存在的最大值主动搁置在数组的最初一个地位
- 后果数组是排序后的数组。
11 12 22 25 64
实战演练
请依照以下步骤实现代码：
- 将最小值 (min_idx ) 初始化为地位 0。
- 遍历数组，找到数组中的最小元素。
- 在遍历时，如果找到任何小于min_idx 的元素，则替换两个值。
- 而后，递增 min_idx 以指向下一个元素。
- 反复直到数组被排序。
上面是上述办法的实现：
- java版本
import java.io.*;
public class SelectionSort
{void sort(int arr[])
{
int n = arr.length;
// 逐渐挪动未排序数组的边界
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;
// 将找到的最小元素与第一个元素进行替换
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
// 打印排序后的数组后果
void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();}
public static void main(String args[])
{SelectionSort ob = new SelectionSort();
int arr[] = {64,25,12,22,11};
ob.sort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}输入
排序数组：11 12 22 25 64抉择排序的复杂度剖析：
工夫复杂度：抉择排序的工夫复杂度为 O(N 2)，因为有两个嵌套循环：
- 一个循环一个一个地抉择 Array 的一个元素 = O(N)
- 将该元素与每个其余数组元素进行比拟的另一个循环 = O(N)
因而整体复杂度 = O(N) O(N) = O(NN) = O(N 2)
辅助空间： O(1) 作为惟一应用的额定内存用于长期变量，同时替换数组中的两个值。抉择排序永远不会进行超过 O(N) 次替换，并且在内存写入是一项代价昂扬的操作时十分有用。
抉择排序算法是否稳固？
稳定性 ：默认实现 不稳固。然而，它能够变得稳固。这个后续再讲。
抉择排序算法的长处：
- 简略易懂。
- 保留具备雷同键的我的项目的绝对程序，这意味着它是稳固的。
- 实用于小型数据集。
- 它实用于各种类型的数据类型。
- 抉择排序是一种就地排序算法，这意味着它不须要任何额定的内存来对列表进行排序。
- 它具备 O(n^2) 的最佳状况和均匀状况工夫复杂度，使其对于小型数据集十分无效。
- 很容易批改为按升序或降序排序。
- 它能够很容易地在硬件中实现，使其实用于实时利用。
- 它也能够用作更无效的排序算法中的子程序。
- 它不须要任何非凡的内存或辅助数据结构，使其成为轻量级解决方案。
- 该算法能够轻松并行，容许在多核处理器上进行高效排序。
- 它能够在无限的内存环境中应用，因为它须要起码的额定内存。
- 它易于了解，使其成为教学目标的热门抉择。
- 它实用于对惟一键很少的数据进行排序，因为它在这种状况下体现良好。
抉择排序算法的毛病：
- 抉择排序在最坏和均匀状况下的工夫复杂度为 O(n^2)。
- 在大型数据集上成果不佳。
- 抉择排序算法须要屡次迭代列表，因而会导致不均衡分支。
- 抉择排序的缓存性能很差，因而对缓存不敌对。
- 不是自适应的，这意味着它没有利用列表可能曾经排序或局部排序的事实
- 对于具备慢速随机存取存储器 (RAM) 的大型数据集来说不是一个好的抉择
- 它不是比拟排序，也没有像合并排序或疾速排序那样的任何性能保障。
- 它的缓存性能很差
- 因为其高分支预测错误率，它可能导致分支预测不佳
- 它有很多写操作，导致在存储速度慢的零碎上性能不佳。
- 它不是可并行算法，这意味着它不能轻易拆分以在多个处理器或内核上运行。
- 它不能很好地解决具备许多反复项的数据，因为它会进行许多不必要的替换。
- 在大多数状况下，它能够被其余算法（如疾速排序和堆排序）超过。
总结：
- 抉择排序是一种简略易懂的排序算法，其工作原理是从列表的未排序局部反复抉择最小（或最大）的元素并将其挪动到列表的已排序局部。
- 对列表中残余的未排序局部反复此过程，直到整个列表排序结束。
- 在最坏和均匀状况下，它的工夫复杂度为 O(n^2)，这使得它对于大型数据集的效率较低。
- 抉择排序是一种稳固的排序算法。
- 它可用于对不同类型的数据进行排序。
- 它在特定应用程序中很有用，例如小型数据集和内存受限零碎。
本文由 mdnice 多平台公布