选择排序

主要思想：每轮依次 从未排序部分选出一个最小的元素放置于未排序序列的第一个位置。

注意：

• PPT中没有统一，其实现刚好是反过来的，它每轮依次 从未排序部分选出一个最大的元素放置于未排序序列的最后一个位置

• PPT中选择排序反向实现，插入排序又正向实现，这边统一都改成正向实现，比较好对比

2.1 简单演示

• 白色背景表示未排序部分
• 灰色背景表示已排序部分
• 淡绿色指示下一个放置本轮最小元素的位置
• 淡黄色指示本轮最小元素

• 初始状态

  sort_base.png
  • 初始状态有n=7个元素，所以 第一轮需要从n个元素选出一个最小的与第一个元素交换；

• 排序过程

  select-sort.png
  • 每一轮都从未排序序列中选出一个最小的，与未排序序列中的第一个元素交换；
  • 共 需n - 1轮

2.2 实现分析

PPT中的实现与下述过程基本相似，但是PPT的代码实现是，每轮选一个最大的放在未排序列表的最后

对于一个长度位n的待排序数组A，我们作如下分析：

• 根据上面的演示分析，对于一个长度为n的数组，我们需要n-1轮对其排好序；

  => 在代码实现部分，轮数对应于第一个for循环：

  # 由于选择排序很直观就是一个从左往右的过程，所以一般第一个for循环都是正向遍历
  for i in range(n - 1)
  

• 对于第 i 轮，有m个数未排好序，对应于第二层for循环，具体表示如下（核心就是：如果本轮有m个数未排好序，我们就让初始索引为第一个数，然后依次比对剩下的m-1个数有没有比初值小的）：

  for i in range(n - 1):
      minValueIndex = i
      for j in range(i + 1, n):
          if A[j] < A[minValueIndex]:
              minValueIndex = j
  

• 最后在每轮结束后进行交换：

  for i in range(n - 1):
      minValueIndex = i
      for j in range(i + 1, n):
          if A[j] < A[minValueIndex]:
              minValueIndex = j
      if minValueIndex != i:
          A[i], A[minValueIndex] = A[minValueIndex], A[i]
  

2.3 实现

def selectSort(A):
    n = len(A)
    for i in range(n - 1):
        minValueIndex = i
        for j in range(i + 1, n):
            if A[j] < A[minValueIndex]:
                minValueIndex = j
        if minValueIndex != i:
            A[i], A[minValueIndex] = A[minValueIndex], A[i]

if __name__ == '__main__':
    A = [5, 7, 1, 3, 6, 2, 4]
    selectSort(A)
    print(A, "= [1, 2, 3, 4, 5, 6, 7]")