logo标签列表

需要帮助理解选择排序算法

javaarrayssorting
5

昨天我在课上收到了这项任务，当时我认为我理解了选择排序的过程，但现在我有点不确定。我认为每次排序后，左边的数字会变得有序，并且直到右边的所有数字都被先排序后才不再被检查。

以下是指示和我的答案:

显示选择排序算法每次排序后的结果数组。如果算法在执行给定的排序前停止，请留下该排序空白。

Original Array: 30 8 2 25 27 20 
PASS 1: 8 30 2 25 27 20 
PASS 2: 8 2 30 25 27 20 
PASS 3: 8 2 25 30 27 20 
PASS 4: 8 2 25 27 30 20 
PASS 5: 8 2 25 27 20 30

有人能告诉我我是否做对了吗？

（该句涉及内容与IT技术无关）
先在YouTube上搜索并观看视频， https://en.wikipedia.org/wiki/File:Selection-Sort-Animation.gif - Saeed
5个回答
3

伪代码示例：

Repeat until no unsorted elements remain:
    Search the unsorted part of the data to find the smallest value
    Swap the smallest found value with the first element of the unsorted part

根据这个，您的数据列表将会...
Original Array: 30 8 2 25 27 20

P1: [2] 8 30 25 27 20 // smallest(2), swap this with the first value(30)

P2: [2 8] 30 25 27 20 // smallest(8), don't need to swap 

P3: [2 8 20] 25 27 30 // smallest(20), swap this with the first ele of unsorted list(30)

P4: [2 8 20 25] 27 30 // smallest(25), don't need to swap

P5: [2 8 20 25 27] 30 // smallest(27), don't need to swap

P6: [2 8 20 25 27 30] // smallest(30), don't need to swap... sorted!

由于最后一个元素已经排序好了，因此不需要进行PASS 6操作。

可以查看哈佛大学的CS50课程视频（Havard University很好地解释了这个过程）：https://www.youtube.com/watch?v=3hH8kTHFw2A

3

我很高兴你尝试了它

算法是：

repeat (numOfElements - 1) times

  set the first unsorted element as the minimum

  for each of the unsorted elements

    if element < currentMinimum

      set element as new minimum

  swap minimum with first unsorted position

输出结果将会是:

Pass 1 : 2 8 30 25 27 20
Pass 2 : 2 8 30 25 27 20
Pass 3 : 2 8 20 25 27 30
Pass 4 : 2 8 20 25 27 30
Pass 5 : 2 8 20 25 27 30

您可以提供自定义输入，它将向您展示逐步输出的步骤： https://visualgo.net/bn/sorting 希望这能有所帮助:D
祝您学习顺利！
2

如果您查看结果，显然您没有正确地完成它。8不小于2！ :)

拿第一个项目：30。找到最小值：2。交换它。

PASS 1: 2 | 8 30 25 27 20

列表的第一部分现在已经排序（用管道符号表示）。
接下来看这个元素：8。找到最小值-实际上8就是最小值，不需要进行任何交换。
PASS 2: 2 8 | 30 25 27 20

接下来是：30。找到最小值：20。交换它。

PASS 3: 2 8 20 | 25 27 30

接下来看看这个数字：25。它是最小值，不需要进行交换。

PASS 4: 2 8 20 25 | 27 30

接下来看一下27这个数字。它是最小值，不需要进行交换。

PASS 5: 2 8 20 25 27 | 30

接下来的项目是30。它是最小值。不需要交换。
列表现在已经排序。
2
我注意到你的数组中最小的元素是2。因此，在第一次遍历中，它应该在数组的开头。请参考以下示例。
示例1： arr[] = 64 25 12 22 11
// 在arr [0 ... 4]中找到最小的元素，并将其放在开头 11 25 12 22 64
// 在arr [1 ... 4]中找到最小的元素，并将其放在arr [1 ... 4]的开头 11 12 25 22 64
// 在arr [2 ... 4]中找到最小的元素，并将其放在arr [2 ... 4]的开头 11 12 22 25 64
// 在arr [3 ... 4]中找到最小的元素，并将其放在arr [3 ... 4]的开头 11 12 22 25 64
参考1: https://www.hackerearth.com/practice/algorithms/sorting/selection-sort/tutorial/ 参考文献2: https://www.tutorialspoint.com/data_structures_algorithms/selection_sort_algorithm.htm
0
### Step 1 − Set MIN to location 0 or any high Value
### Step 2 − Search the minimum element in the list
### Step 3 − Swap with value at index of minimum
### Step 4 − Repeat until iteration gets over
<code>

    final int[] intArr = new int[]{14, 33, 27, 10, 35, 19, 42, 44};
    int index = -1;
    boolean isMin;
    for (int i = 0; i < intArr.length; i++) {
      int min = 999999999;
      isMin = false;
      for (int j = i + 1; j < intArr.length; j++) {
        if (intArr[j] < min && intArr[i] >= intArr[j]) {
          min = intArr[j];
          index = j;
          isMin = true;
        }
      }
      if (isMin) {
        intArr[index] = intArr[i];
        intArr[i] = min;
      }
    }
    Arrays.stream(intArr).forEach(System.out::println);
</code>
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接