选择排序

选择排序：

搜索整个列表，找到最小项的位置。如果该位置不是列表的第一个位置，则交换这两个位置。然后算法回到第二个位置并且重复这个过程。如果必要的话，将最小项和第二个位置的项交换。当达到整个过程额最有一个位置。列表就是排序好的了。

Python实现：

import random


def selection_sort(lyst):
    """
    :param lyst: 需要排序的列表
    :return:
    """
    def swap(lyst, i, j):
        """交换项目中 i 和 j的位置"""
        #  可以理解为 lyst[i], lyst[j] = lyst[j], lyst[i]
        temp = lyst[i]
        lyst[i] = lyst[j]
        lyst[j] = temp

    i = 0
    while i < len(lyst) - 1:
        min_index = i
        j = i + 1
        while j < len(lyst):
            if lyst[j] < lyst[min_index]:
                min_index = j
            j += 1
        if min_index != i:
            swap(lyst, min_index, i)
        i += 1
    else:
        return lyst


if __name__ == '__main__':
    size = 10
    lyst = []
    for count in range(size):
        lyst.append(random.randint(1, size + 1))
    print(lyst)
    print(selection_sort(lyst))

Go实现:

package main

import "fmt"

func swap(lyst []int, i int, j int) {

    temp := lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp
}

func main()  {
    // 申明一个空slice
    lyst := []int{100, 900, 111, 99, 56, 103, 78, 95, 1000, 789, 134, 110}
    fmt.Println(lyst)

    i := 0

    for i < len(lyst) -1 {
        min_index := i
        j := i + 1
        for j < len(lyst) {
            if lyst[j] < lyst[min_index] {
                min_index = j
            }
            j += 1
        }
        if min_index != i {
            swap(lyst, min_index, i)
        }
        i += 1
    }
    fmt.Println(lyst)
}

时间复杂度：

在各种情况下复杂度为O($n^2$); 由于数据交互只在外围循环中进行，所以在最坏的情况下和平均情况下，开销是线性的。