建筑平面设计图用什么软件_北京网站制作公司建站_如何做营销策划方案_软文平台发布

选择排序

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):  # 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)    # 交换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 = j# 交换找到的最小元素和当前元素arr[i], arr[min_idx] = arr[min_idx], arr[i]return arr# for test
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()