Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
SelectionSort.playground
README.markdown
README_en.markdown
SelectionSort.swift

README.markdown

选择排序(Selection Sort)

目标:将数组从低到高(或从高到低)排序。

您将获得一系列需要按正确顺序排列的数字。 选择排序算法将数组分为两部分:数组的开头是排序的,数组的其余部分是仍然需要排序的数字。

[ ...sorted numbers... | ...unsorted numbers... ]

这类似于插入排序,但区别在于如何将新数字添加到已排序部分。

它的工作原理如下:

  • 找到数组中的最小数字。 从索引0开始,遍历数组中的所有数字,并追踪最小数字的位置。
  • 使用索引0处的数字交换最小数字。现在,已排序部分仅包含索引0处的数字。
  • 转到索引1处。
  • 找到数组其余部分中的最小数字。 从索引1开始查看。再次循环直到数组结束并追踪最小数字。
  • 使用索引1处的数字交换最小数字。现在,已排序部分包含两个数字,索引0和索引1。
  • 转到索引2处。
  • 从索引2开始,找到数组其余部分中的最小数字,并将其与索引2处的数字交换。现在,数组从索引0到2已排序; 此范围包含数组中的三个最小数字。
  • 并继续,直到没有数字需要排序。

这种排序方式之所以被称为“选择”排序,是因为在每个步骤中,都是在数组的其余部分里搜索选择下一个最小数字。

例子

假设要排序的数字是[5,8,3,4,6]。 用|符号表示数组的已排序部分的结束位置(讲述插入排序时也是如此表示的)。

最初,排序部分为空:

[| 5, 8, 3, 4, 6 ]

现在我们找到数组中的最小数字。 从|栏开始向右扫描数组,找到数字3

要将此数字放入已排序的位置,将它与|旁边的数字5交换(然后把|向右移动一位):

[ 3 | 8, 5, 4, 6 ]
  *      *

排序部分现在是[3],其余部分是[8,5,4,6]

再一次,我们从|栏开始寻找最低的数字。 我们找到4并用8与之交换得到(同样把|向右移动一位):

[ 3, 4 | 5, 8, 6 ]
     *      *

每一步,|栏都会向右移动一个位置。 我们再次查看数组的其余部分,找到5是最小数字。 没有必要与自己交换,只需|栏前进:

[ 3, 4, 5 | 8, 6 ]
        *

重复此过程,直到数组都排序了。 请注意,|栏左侧的所有内容始终按排序顺序排列,并且始终包含数组中的最小数字。 最后,我们最终得到:

[ 3, 4, 5, 6, 8 |]

选择排序是原地排序,因为所有内容都发生在同一个数组中而不使用额外的内存。您也可以将其实现为 稳定排序,以便相同的元素不会相互交换(请注意,下面给出的版本不稳定)。

代码

这是Swift中选择排序的一个实现:

func selectionSort(_ array: [Int]) -> [Int] {
  guard array.count > 1 else { return array }  // 1

  var a = array                    // 2

  for x in 0 ..< a.count - 1 {     // 3

    var lowest = x
    for y in x + 1 ..< a.count {   // 4
      if a[y] < a[lowest] {
        lowest = y
      }
    }

    if x != lowest {               // 5
      a.swapAt(x, lowest)
    }
  }
  return a
}

将此代码放在 playground 测试:

let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
selectionSort(list)

代码逐步说明:

  1. 如果数组为空或仅包含单个元素,则无需排序。

  2. 生成数组的副本。 这是必要的,因为我们不能直接在Swift中修改array参数的内容。 与Swift的sort()函数一样,selectionSort()函数将返回排完序的原始数组拷贝

  3. 函数内有两个循环。 外循环依次查看数组中的每个元素; 这就是向前移动|栏的原因。

  4. 内循环实现找到数组其余部分中的最小数字。

  5. 使用当前数组索引数字交换最小数字。 if判断是必要的,因为你不能在Swift中swap()同一个元素。

译注:Swift中的数组没有swap()方法,只有swapAt()方法,而且swapAt()交换同一个元素是没有问题的。这可能是Swift版本更新的问题。

总结:对于数组的每个元素,选择排序使用数组其余部分中的最小值交换位置。结果,数组从左到右排序。(你也可以从右到左进行,在这种情况下你总是寻找数组中最大的数字。试一试!)

注意: 外循环以索引a.count - 2结束。 最后一个元素将自动处于正确的位置,因为此时没有剩下其他较小的元素了。

源文件SelectionSort.swift是一个使用泛型的函数版本,因此您也可以使用它来对字符串和其他数据类型进行排序。

性能

选择排序很容易理解,但执行速度慢 O(n^2)。它比插入排序更糟,但优于冒泡排序。查找数组其余部分中的最低元素很慢,特别是因为内部循环将重复执行。

堆排序使用与选择排序相同的原则,但使用了一种快速方法在数组的其余部分中查找最小值。 堆排序性能是 O(nlogn)

扩展阅读

选择排序的维基百科

作者:Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron