选择排序

选择排序（Selection sort）

  1.     选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

算法思路

  1. 初始状态：无序区为R[1..n]，有序区为空；
  2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
  3. n-1趟结束，数组有序化了。

动画演示

9.9 选择排序 - 图1

代码实现

  1. def SS(nums):
  2.     n = len(nums)
  3.     for i in range(0, n-1):
  4.         nummin = i      # 当前最小元素的下标
  5.         for j in range(i+1, n):     # 遍历无序序列
  6.             if nums[j] < nums[nummin]:      # 寻找最小值
  7.                 nummin = j      # 更改最小元素的下标
  8.         nums[i], nums[nummin] = nums[nummin], nums[i]       # 交换位置
  9.         print(nums)     # 打印排序过程
  10.     return nums
  12. print(SS(nums=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]))
    运行结果：

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

    排序过程：

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

[2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]
[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 15, 47, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 36, 26, 27, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 36, 27, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 44, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

复杂度分析

    时间复杂度分析：选择排序的比较次数是固定的，比对次数一定是

9.9 选择排序 - 图2%3D%5Cfrac%7Bn(n-1)%7D%7B2%7D%0A#card=math&code=%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D%7Bi%7D%3D1%2B2%2B%7B%5Ccdots%7D%2B%28n-1%29%3D%5Cfrac%7Bn%28n-1%29%7D%7B2%7D%0A)

次，时间复杂度为O(n^2)。

    空间复杂度分析：选择排序只需要一个变量来记录最小元素的下标，所以时间复杂度为O(1)。

优缺点

    优点：比冒泡排序稍优，主要是交换次数减少为O(n)。而且选择排序不需要占用额外的空间。

    缺点：对于任何序列的时间复杂度都是O(n^2)，所以有序序列与无序序列在利用选择排序时，所需时间一样。

性能改进

    我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。