Data Structures Algorithms 简明教程

Selection Sort Algorithm

选择排序是一种简单的排序算法。此排序算法与插入排序类似，是一种基于原地的比较算法，其中该列表被分成两部分，左侧的已排序部分和右侧的未排序部分。最初，已排序部分为空，未排序部分是整个列表。

Selection sort is a simple sorting algorithm. This sorting algorithm, like insertion sort, is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

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

The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundaries by one element to the right.

此算法不适用于大型数据集，因为其平均和最坏情况的复杂度为 O(n2) ，其中 n 为项数。

This algorithm is not suitable for large data sets as its average and worst case complexities are of O(n2), where n is the number of items.

Selection Sort Algorithm

这种类型的排序称为选择排序，因为它通过重复排序元素来工作。也就是说：我们首先找到数组中最小的值并将其与第一个位置的元素交换，然后找到第二小的元素并将其与第二个位置的元素交换，我们继续以这种方式进行处理，直到整个数组排序。

This type of sorting is called Selection Sort as it works by repeatedly sorting elements. That is: we first find the smallest value in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and we continue the process in this way until the entire array is sorted.

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 x

Analysis

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

Selection sort is among the simplest of sorting techniques and it works very well for small files. It has a quite important application as each item is actually moved at the most once.

分区排序是一种用于对具有非常大的对象（记录）和小型键的文件进行排序的方法。最坏的情况发生在数组已经按降序排序并且我们希望按升序对其进行排序时。

Section sort is a method of choice for sorting files with very large objects (records) and small keys. The worst case occurs if the array is already sorted in a descending order and we want to sort them in an ascending order.

尽管如此，选择排序算法所需的时间对于要排序的数组的原始顺序并不是很敏感：在每种情况下，测试 if 𝑨[𝒋] < A[j] < min x 的执行次数完全相同。

Nonetheless, the time required by selection sort algorithm is not very sensitive to the original order of the array to be sorted: the test if 𝑨[𝒋] < A[j] < min x is executed exactly the same number of times in every case.

选择排序花费大部分时间来尝试查找未排序数组中最小元素。它清楚地显示了选择排序与冒泡排序之间的相似性。

Selection sort spends most of its time trying to find the minimum element in the unsorted part of the array. It clearly shows the similarity between Selection sort and Bubble sort.

Bubble sort selects the maximum remaining elements at each stage, but wastes some effort imparting some order to an unsorted part of the array.
Selection sort is quadratic in both the worst and the average case, and requires no extra memory.

对于 i 从 1 到 n - 1 ，执行一次交换和 n - i 次比较，因此总共有 n - 1 次交换和

For each i from 1 to n - 1, there is one exchange and n - i comparisons, so there is a total of n - 1 exchanges and

(n − 1) + (n − 2) + …+2 + 1 = n(n − 1)/2 次比较。

(n − 1) + (n − 2) + …+2 + 1 = n(n − 1)/2 comparisons.

无论输入数据是什么，这些观察都成立。

These observations hold, no matter what the input data is.

最坏的情况下，这可能是二次的，但在平均情况下，该数量是 O(n log n) 。它暗示了 running time of Selection sort is quite insensitive to the input 。

In the worst case, this could be quadratic, but in the average case, this quantity is O(n log n). It implies that the running time of Selection sort is quite insensitive to the input.

Example

考虑以下描绘的数组作为一个示例。

Consider the following depicted array as an example.

对于已排序列表中的第一个位置，整个列表按顺序扫描。14 当前存储在第一个位置，我们在整个列表中搜索，发现 10 是最低值。

For the first position in the sorted list, the whole list is scanned sequentially. The first position where 14 is stored presently, we search the whole list and find that 10 is the lowest value.

所以我们用 10 替换 14。在一次迭代后，10（恰好是列表中的最小值）出现在已排序列表的第一个位置。

So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the list, appears in the first position of the sorted list.

对于 33 所在的第二个位置，我们开始线性扫描列表的其余部分。

For the second position, where 33 is residing, we start scanning the rest of the list in a linear manner.

我们发现 14 是列表中的第二低值，它应该出现在第二个位置。我们交换这些值。

We find that 14 is the second lowest value in the list and it should appear at the second place. We swap these values.

经过两次迭代，最小的两个值按顺序排列在开头。

After two iterations, two least values are positioned at the beginning in a sorted manner.

相同的过程应用于数组中的其余项目 −

The same process is applied to the rest of the items in the array −

Implementation

选择排序算法在以下四种不同的编程语言中实现。给定的程序选择数组的最小数，并将其与第一个索引中的元素交换。第二个最小数与第二个索引中存在的元素交换。该过程一直持续到达到数组末尾。

The selection sort algorithm is implemented in four different programming languages below. The given program selects the minimum number of the array and swaps it with the element in the first index. The second minimum number is swapped with the element present in the second index. The process goes on until the end of the array is reached.