选择排序
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 + C1. 拆分原则：常数操作级别，
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:returnlens = len(arr)for i in range(0, lens-1): minIndex = i for j in range(i+1, lens):if arr[minIndex] > arr[j]: minIndex = j swap(arr, i, minIndex) returndef selection_sortxx(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i + 1, n):if arr[j] < arr[min_idx]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arr
def main():testTime = 500000maxSize = 100maxValue = 100succeed = Truefor i in range(testTime):arr1 = generateRandomArray(maxSize, maxValue)arr2 = copyArray(arr1)selectionSort(arr1)comparator(arr2)if (not isEqual(arr1, arr2)):succeed = FalseprintArray(arr1)printArray(arr2)breakprint(i, succeed)if succeed:print("Nice!")else:print("Fucking fucked!")arr = generateRandomArray(maxSize, maxValue)printArray(arr)selectionSort(arr)printArray(arr)if __name__ == '__main__':main()
