处理步骤

步骤是从原始数据中依次找出最小数据并放入到较前面的位置，步骤分析，

  • 拿第一个数据和第一个数据后的所有数据做比较，找到第一个数据和剩余数据中最小的数据并做位置替换
  • 拿第二个数据和和第二个数据之后的所有数据做比较，同样是找到最小值并替换位置
  • 重复此步骤

  • 直到全部结束，至此排序结束

    演示过程

    选择排序的过程如下：

  • ezgif-3-c5f52a8a27d0.gif

    代码实现

  • python ```python

    选择排序

    class SelectionSort: def init(self, data: list):

    1.   assert len(data) > 0, "data length must > 0"
    2.   self.__data = data

    def sort(self) -> list:

    1.   for i in range(len(self.__data)):
    2.       # 查找 data[i:len(data)]中的最小元素 ,在查找前可以假定data[i]最小
    3.       min_index = i
    4.       for j in range(i + 1, len(self.__data)):
    5.           # 剩余数据中存在比当前值小的值 替换最小下标
    6.           if self.__data[j] < self.__data[min_index]:
    7.               min_index = j
    8.       if min_index != i:
    9.           self.__swap(i, min_index)
    10.   return self.__data

    交换数组中位置为 i 和 j 的数据

    def __swap(self, i: int, j: int):

    1.   self.__data[i], self.__data[j] = self.__data[j], self.__data[i]

if name == ‘main‘: selectSort = SelectionSort([1, 8, 7, 2, 3, 9, 5]) print(selectSort.sort())

  2. - go go代码基本和python的实现过程一致
  3. ```go
  4. package main
  6. import (
  7.     "fmt"
  8.     "math/rand"
  9.     "time"
  10. )
  12. type Sort interface {
  13.     sort()
  14.     swap(int ,int)
  15. }
  17. type SelectSort struct {
  18.     // 待排序和排序后的数据
  19.     Data []int
  20. }
  22. func Data(num int,max int,isSort bool) []int {
  23.     /*
  24.      num 数据量
  25.      max 取值范围 0 - max
  26.      isSort 是否有序
  27.     */
  28.     var array []int
  29.     if isSort{
  30.         for i := 0; i < num; i++ {
  31.             array = append(array, num)
  32.         }
  33.     }else {
  34.         for i := 0; i < num; i++ {
  35.             array = append(array, rand.Intn(max))
  36.         }
  37.     }
  39.     return array
  41. }
  43. // 统计算法执行时间 可用于做算法执行时间对比
  44. func TimeTools(sort Sort,funcName string,dataNum int) {
  46.     startTime := time.Now()
  47.     sort.sort()
  48.     elapsed := time.Since(startTime)
  49.     fmt.Printf("%s --> data: %d times %v \n",funcName,dataNum,elapsed)
  52. }
  54. func (sort *SelectSort) sort()  {
  56.     for i:=0;i<len(sort.Data);i++{
  57.         for j:=i+1;j<len(sort.Data);j++{
  58.             var minIndex = i
  59.             if sort.Data[j] < sort.Data[minIndex]{
  60.                 minIndex = j
  61.             }
  62.             if minIndex!=i{
  63.                 sort.swap(i,j)
  64.             }
  65.         }
  66.     }
  69. }
  71. // 交换data中 i j位置上的数据
  72. func (sort *SelectSort)swap(i int,j int)  {
  73.     sort.Data[i],sort.Data[j] = sort.Data[j],sort.Data[i]
  74.     return
  76. }
  77. func main()  {
  78.     var data []int
  79.     data = Data(20,100000,false)
  80.     selectSort:= new(SelectSort)
  81.     selectSort.Data = data
  82.     TimeTools(selectSort,"选择排序",20)
  83. }

时间复杂度分析

O(n^2)
通过实际测试可以看到，随着排序数据的增加，其算法执行时间是呈平方倍增加，即如果样本从100到1000再到1000，可以看到执行时间分别会增加100倍，10的平方。

  1. 算法:selectSort 数据量:100 执行时间为0.0009453296661376953
  2. 算法:selectSort 数据量:1000 执行时间为0.06486988067626953
  3. 算法:selectSort 数据量:10000 执行时间为5.670239448547363