1. Introduction

1.绪论

In this tutorial, we’ll learn Selection Sort, see its implementation in Java, and analyze its performance.

在本教程中，我们将学习选择排序，查看其在Java中的实现，并分析其性能。

2. Algorithm Overview

2.算法概述

Selection Sort begins with the element in the 1^st position of an unsorted array and scans through subsequent elements to find the smallest element. Once found, the smallest element is swapped with the element in the 1^st position.

选择排序从未排序数组的1^st位置的元素开始，并扫描后续元素以找到最小的元素。一旦找到，最小的元素将与第1¹个位置的元素互换。

The algorithm then moves on to the element in the 2^nd position and scans through subsequent elements to find the index of the 2^nd smallest element. Once found, the second smallest element is swapped with the element in the 2^nd position.

然后，该算法转向2^nd位置的元素，并扫描随后的元素以找到2^nd最小的元素的索引。一旦找到，第二小的元素将与2^nd位置的元素互换。

This process goes on until we reach the n-1^th element of the array, which puts the n-1^th smallest element in the n-1^th position. The last element automatically falls in place, in the n-1^th iteration, thereby sorting the array.

这个过程一直持续到我们到达数组的n-1^第个元素，这样就把n-1^第个最小的元素放在n-1^第个位置。最后一个元素自动落位，在n-1^第次迭代中，从而对数组进行排序。

We find the largest element instead of the smallest element to sort the array in descending order.

我们找到最大的元素而不是最小的元素，对数组进行降序排序。

Let’s see an example of an unsorted array and sort it in ascending order to visually understand the algorithm.

让我们看一个未排序数组的例子，并按升序排序，以直观地理解该算法。

2.1. An Example

2.1.一个例子

Consider the following unsorted array:

考虑以下未经排序的数组。

int[] arr = {5, 4, 1, 6, 2}

int[] arr = {5, 4, 1, 6, 2 }

Iteration 1

迭代1。

Considering the above working of the algorithm, we start with the element in 1^st position – 5 – and scan through all subsequent elements to find the smallest element – 1. We then swap the smallest element with the element in 1^st position.

考虑到上述算法的工作原理，我们从1^st位置的元素–5开始，扫描所有后续的元素，找到最小的元素–1。然后我们将最小的元素与1^st位置的元素交换。

The modified array nows looks like:

修改后的阵列现在看起来像。

{1, 4, 5, 6, 2}

Total comparisons made: 4

进行的比较总数：4

Iteration 2

迭代2。

In the second iteration, we move on to the 2^nd element – 4 – and scan through subsequent elements to find the second smallest element – 2. We then swap the second smallest element with the element in 2^nd position.

在第二次迭代中，我们移动到2^nd元素–4–并扫描随后的元素，找到第二小的元素–2。然后我们将第二小的元素与2^nd位置的元素交换。

The modified array now looks like:

修改后的阵列现在看起来像。

{1, 2, 5, 6, 4}

{1, 2, 5, 6, 4 }

Total comparisons made: 3

进行的比较总数：3

Continuing similarly, we have the following iterations:

类似地继续下去，我们有以下迭代。

Iteration 3

迭代3。

{1, 2, 4, 6, 5}

{1, 2, 4, 6, 5 }

Total comparisons made: 2

进行的比较总数：2

Iteration 4

迭代4

{1, 2, 4, 5, 6}

Total comparisons made: 1

进行的比较总数：1

3. Implementation

3.实施

Let’s implement Selection Sort using a couple of for loops:

让我们用几个for循环来实现选择排序。

public static void sortAscending(final int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minElementIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minElementIndex] > arr[j]) {
                minElementIndex = j;
            }
        }

        if (minElementIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minElementIndex];
            arr[minElementIndex] = temp;
        }
    }
}

Of course, to reverse it we could do something quite similar:

当然，为了扭转这种局面，我们可以做一些非常类似的事情。

public static void sortDescending(final int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int maxElementIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[maxElementIndex] < arr[j]) {
                maxElementIndex = j;
            }
        }

        if (maxElementIndex != i) {
            int temp = arr[i];
            arr[i] = arr[maxElementIndex];
            arr[maxElementIndex] = temp;
        }
    }
}

And with a bit more elbow grease, we could combine these using Comparators.

而只要再多花点心思，我们就可以使用Comparators来组合这些。

4. Performance Overview

4.性能概述

4.1. Time

4.1.时间

In the example that we saw earlier, selecting the smallest element required a total of (n-1) comparisons followed by swapping it to the 1^st position. Similarly, selecting the next smallest element required total (n-2) comparisons followed by swapping in the 2^nd position, and so on.

在我们之前看到的例子中，选择最小的元素共需要(n-1)比较，然后将其交换到1^st位置。类似地，选择下一个最小的元素需要总共(n-2)比较，然后在2^nd位置进行交换，以此类推。

Thus, starting from index 0, we perform n-1, n-2, n-3, n-4 …. 1 comparisons. The last element automatically falls in place due to previous iterations and swaps.

因此，从索引0开始，我们进行n-1, n-2, n-3, n-4 ….1的比较。由于之前的迭代和交换，最后一个元素自动落位。

Mathematically, the sum of the first n-1 natural numbers will tell us how many comparisons we need in order to sort an array of size n using Selection Sort.

从理论上讲，前n-1个自然数之和将告诉我们需要多少次比较才能用选择排序法对一个大小为n的数组进行排序。

The formula for the sum of n natural numbers is n(n+1)/2.

n自然数之和的公式为n(n+1)/2。

In our case, we need the sum of first n-1 natural numbers. Therefore, we replace n with n-1 in the above formula to get:

在我们的例子中，我们需要前n-1个自然数之和。因此，我们用n-1代替上述公式中的n，得到：

(n-1)(n-1+1)/2 = (n-1)n/2 = (n^2-n)/2

As n^2 grows prominently as n grows, we consider the higher power of n as the performance benchmark, making this algorithm have a time complexity of O(n^2).

由于n^2随着n的增长而突出增长，我们考虑将n的高次方作为性能基准，使得该算法的时间复杂性为O(n^2)。

4.2. Space

4.2.空间

In terms of auxiliary space complexity, Selection Sort requires one extra variable to hold the value temporarily for swapping. Therefore, Selection Sort’s space complexity is O(1).

在辅助空间复杂度方面，选择排序需要一个额外的变量来暂时保存值以进行交换。因此，选择排序的空间复杂性是O(1)。

5. Conclusion

5.总结

Selection Sort is a very simple sorting algorithm to understand and implement. Unfortunately, its quadratic time complexity makes it an expensive sorting technique. Also, since the algorithm has to scan through each element, the best case, average case, and worst-case time complexity is the same.

选择排序是一种非常简单的排序算法，易于理解和实现。不幸的是，其二次方时间复杂度使其成为一种昂贵的排序技术。此外，由于该算法必须扫描每个元素，最佳情况、平均情况和最坏情况下的时间复杂度是相同的.。

Other sorting techniques like Insertion Sort and Shell Sort also have quadratic worst-case time complexity, but they perform better in best and average cases.

其他排序技术，如插入排序和壳排序也有二次最坏情况下的时间复杂性，但它们在最佳和平均情况下表现更好。

Check out the complete code for Selection Sort over on GitHub.

请在GitHub上查看选择排序的完整代码。