Data Structures Algorithms 简明教程
Selection Sort Algorithm
选择排序是一种简单的排序算法。此排序算法与插入排序类似，是一种基于原地的比较算法，其中该列表被分成两部分，左侧的已排序部分和右侧的未排序部分。最初，已排序部分为空，未排序部分是整个列表。
从未排序数组中选择最小的元素并与最左边的元素交换，该元素将成为已排序数组的一部分。此过程继续将未排序数组边界向右移动一个元素。
此算法不适用于大型数据集，因为其平均和最坏情况的复杂度为 O(n2) ，其中 n 为项数。
Selection Sort Algorithm
这种类型的排序称为选择排序，因为它通过重复排序元素来工作。也就是说：我们首先找到数组中最小的值并将其与第一个位置的元素交换，然后找到第二小的元素并将其与第二个位置的元素交换，我们继续以这种方式进行处理，直到整个数组排序。
1. Set MIN to location 0.
2. Search the minimum element in the list.
3. Swap with value at location MIN.
4. Increment MIN to point to next element.
5. Repeat until the list is sorted.Pseudocode
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 xAnalysis
选择排序是所有排序技术中最简单的，它对小文件非常有效。它有一个非常重要的应用程序，因为每个项实际上最多移动一次。
分区排序是一种用于对具有非常大的对象（记录）和小型键的文件进行排序的方法。最坏的情况发生在数组已经按降序排序并且我们希望按升序对其进行排序时。
尽管如此，选择排序算法所需的时间对于要排序的数组的原始顺序并不是很敏感：在每种情况下，测试 if 𝑨[𝒋] < A[j] < min x 的执行次数完全相同。
选择排序花费大部分时间来尝试查找未排序数组中最小元素。它清楚地显示了选择排序与冒泡排序之间的相似性。
-
冒泡排序在每个阶段都选择最大的剩余元素，但在未排序数组的一部分中浪费了一些精力来施加一些顺序。
-
选择排序在最坏和平均情况下都是二次的，并且不需要额外的内存。
对于 i 从 1 到 n - 1 ，执行一次交换和 n - i 次比较，因此总共有 n - 1 次交换和
(n − 1) + (n − 2) + …+2 + 1 = n(n − 1)/2 次比较。
无论输入数据是什么，这些观察都成立。
最坏的情况下，这可能是二次的，但在平均情况下，该数量是 O(n log n) 。它暗示了 running time of Selection sort is quite insensitive to the input 。
