选择排序

1. 原理

0 ~ N-1 找min 放到 N-1位置  最小数
0 ~ N-2 找min 放到 N-2位置  次小数
0 ~ N-3 找min 放到 N-3位置  次次小数
...
0 ~ 1 找min 放到 1位置  次次小数
时间复杂度： 多少次常数操作？？

0 ~ N-1 找min 放到 N-1位置  最小数     N眼 + N比 1次swap
0 ~ N-2 找min 放到 N-2位置  次小数     N-1眼 + N-1比 1次swap
0 ~ N-3 找min 放到 N-3位置  次次小数   N-2眼 + N-2比 1次swap
...
0 ~ 1 找min 放到 1位置  次次小数

看：N + N-1 + N-2 + N-3+... +1
比: N + N-1 + N-2 + N-3+... +1
swap: N
= aN**2 + bN + C

1. 拆分原则：常数操作级别，
2. 时间复杂度优劣： 不要低阶项，常数项，高阶系数； 最后拆分到常数操作级别
3. 当N很大时， 低阶、常数项影响很小
4. 如果 a、b算法的时间复杂度同一个级别， 拼常数项（大样本验证）。
5. 选择、冒泡、插入的时间复杂度为O(N^2)

选择排序适用于少量数据的排序。每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。
选择排序是一种不稳定的排序算法，但它具有 O(1) 的空间复杂度。

选择排序的原理
选择排序的基本思想是将数组分成两个部分：已排序部分和未排序部分。
1. 初始状态：已排序部分为空，未排序部分包含整个数组。
2. 从未排序部分选择最小（或最大）的元素，将其放到已排序部分的末尾。
3. 重复步骤 2，直到未排序部分为空。

选择排序的时间复杂度
最坏情况时间复杂度：O(n^2)，因为每次选择最小元素都需要遍历未排序部分。
最佳情况时间复杂度：O(n^2)，即使数组已经有序，仍然需要遍历未排序部分。
平均情况时间复杂度：O(n^2)。
选择排序的空间复杂度 O(1)。

选择排序是不稳定的排序算法，因为相等元素的相对顺序可能会改变。例如，如果在选择过程中交换了两个相等元素的位置，那么它们的相对顺序就会改变。

2. code

def selectionSort(arr):
    if len(arr) < 2:
        return
    lens = len(arr)
    for i in range(0, lens-1):  # 0~lens-2的index都要更新最小值
        minIndex = i            # 确定第 i个位置的值
        for j in range(i+1, lens):
            if arr[minIndex] > arr[j]:   # 不断更新第 i 个位置的最小值对应的索引
                minIndex = j   # 如果当前值更小则更新最小值的索引
        swap(arr, i, minIndex)    # 交换
    return

def selection_sortxx(arr):
    n = len(arr)
    for i in range(n):
        # 假设当前元素是最小的
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 交换找到的最小元素和当前元素
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr


# for test
def main():
    testTime = 500000
    maxSize = 100
    maxValue = 100
    succeed = True
    for i in range(testTime):
        arr1 = generateRandomArray(maxSize, maxValue)
        arr2 = copyArray(arr1)
        selectionSort(arr1)
        comparator(arr2)
        if (not isEqual(arr1, arr2)):
            succeed = False
            printArray(arr1)
            printArray(arr2)
            break
        print(i, succeed)
    if succeed:
        print("Nice!")
    else:
        print("Fucking fucked!")

    arr = generateRandomArray(maxSize, maxValue)
    printArray(arr)
    selectionSort(arr)
    printArray(arr)

if __name__ == '__main__':
    main()