设计与分析 - 选择排序

选择排序是一种简单的排序算法。这种排序算法与插入排序一样，是一种基于就地比较的算法，其中列表被分为两部分，左端的已排序部分和右端的未排序部分。最初，已排序的部分是空的，未排序的部分是整个列表。

从未排序的数组中选择最小的元素并与最左边的元素交换，该元素成为排序数组的一部分。这一过程继续将未排序的数组边界向右移动一个元素。

该算法不适合大型数据集，因为其平均和最坏情况复杂度为O(n 2 )，其中n是项目数。

选择排序算法

这种类型的排序称为选择排序，因为它通过重复对元素进行排序来工作。即：我们先找到数组中最小的值与第一个位置的元素交换，然后找到次小的元素与第二个位置的元素交换，如此下去，直到整个数组已排序。

步骤 1 - 将 MIN 设置为位置 0

步骤 2 - 搜索列表中的最小元素

步骤 3 - 与位置 MIN 处的值进行交换

步骤 4 - 增加 MIN 以指向下一个元素

步骤 5 - 重复直到列表排序

伪代码

Algorithm: Selection-Sort (A)
fori← 1 to n-1 do
   min j ←i;
   min x ← A[i]
   for j ←i + 1 to n do
      if A[j] < min x then
         min j ← j
         min x ← A[j]
   A[min j] ← A [i]
   A[i] ← min x

分析

选择排序是最简单的排序技术之一，对于小文件非常有效。它有一个非常重要的应用，因为每个项目实际上最多被移动一次。

节排序是一种用于对具有非常大的对象（记录）和小键的文件进行排序的方法。如果数组已经按降序排序，而我们想按升序排序，则会出现最坏的情况。

尽管如此，选择排序算法所需的时间对要排序的数组的原始顺序不是很敏感：测试 if