1.1.2.1 选择 + 冒泡排序

选择排序

1. 原理

1. 0 ~ N-1 找min 放到 N-1位置  最小数
2. 0 ~ N-2 找min 放到 N-2位置  次小数
3. 0 ~ N-3 找min 放到 N-3位置  次次小数
4. ...
5. 0 ~ 1 找min 放到 1位置  次次小数
6. 时间复杂度： 多少次常数操作？？
8. 0 ~ N-1 找min 放到 N-1位置  最小数     N眼 + N比 1次swap
9. 0 ~ N-2 找min 放到 N-2位置  次小数     N-1眼 + N-1比 1次swap
10. 0 ~ N-3 找min 放到 N-3位置  次次小数   N-2眼 + N-2比 1次swap
11. ...
12. 0 ~ 1 找min 放到 1位置  次次小数
14. 看：N + N-1 + N-2 + N-3+... +1
15. 比: N + N-1 + N-2 + N-3+... +1
16. swap: N
17. = aN**2 + bN + C
19. 1. 拆分原则：常数操作级别，
20. 2. 时间复杂度优劣： 不要低阶项，常数项，高阶系数； 最后拆分到常数操作级别
21. 3. 当N很大时， 低阶、常数项影响很小
22. 4. 如果 a、b算法的时间复杂度同一个级别， 拼常数项（大样本验证）。
23. 5. 选择、冒泡、插入的时间复杂度为O(N^2)
25. 选择排序适用于少量数据的排序。每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。
26. 选择排序是一种不稳定的排序算法，但它具有 O(1) 的空间复杂度。
28. 选择排序的原理
29. 选择排序的基本思想是将数组分成两个部分：已排序部分和未排序部分。
30. 1. 初始状态：已排序部分为空，未排序部分包含整个数组。
31. 2. 从未排序部分选择最小（或最大）的元素，将其放到已排序部分的末尾。
32. 3. 重复步骤 2，直到未排序部分为空。
34. 选择排序的时间复杂度
35. 最坏情况时间复杂度：O(n^2)，因为每次选择最小元素都需要遍历未排序部分。
36. 最佳情况时间复杂度：O(n^2)，即使数组已经有序，仍然需要遍历未排序部分。
37. 平均情况时间复杂度：O(n^2)。
38. 选择排序的空间复杂度 O(1)。
40. 选择排序是不稳定的排序算法，因为相等元素的相对顺序可能会改变。例如，如果在选择过程中交换了两个相等元素的位置，那么它们的相对顺序就会改变。

复制代码

2. code

1. def selectionSort(arr):
2.     if len(arr) < 2:
3.         return
4.     lens = len(arr)
5.     for i in range(0, lens-1):  # 0~lens-2的index都要更新最小值
6.         minIndex = i            # 确定第 i个位置的值
7.         for j in range(i+1, lens):
8.             if arr[minIndex] > arr[j]:   # 不断更新第 i 个位置的最小值对应的索引
9.                 minIndex = j   # 如果当前值更小则更新最小值的索引
10.         swap(arr, i, minIndex)    # 交换
11.     return
13. def selection_sortxx(arr):
14.     n = len(arr)
15.     for i in range(n):
16.         # 假设当前元素是最小的
17.         min_idx = i
18.         for j in range(i + 1, n):
19.             if arr[j] < arr[min_idx]:
20.                 min_idx = j
21.         # 交换找到的最小元素和当前元素
22.         arr[i], arr[min_idx] = arr[min_idx], arr[i]
23.     return arr
26. # for test
27. def main():
28.     testTime = 500000
29.     maxSize = 100
30.     maxValue = 100
31.     succeed = True
32.     for i in range(testTime):
33.         arr1 = generateRandomArray(maxSize, maxValue)
34.         arr2 = copyArray(arr1)
35.         selectionSort(arr1)
36.         comparator(arr2)
37.         if (not isEqual(arr1, arr2)):
38.             succeed = False
39.             printArray(arr1)
40.             printArray(arr2)
41.             break
42.         print(i, succeed)
43.     if succeed:
44.         print("Nice!")
45.     else:
46.         print("Fucking fucked!")
48.     arr = generateRandomArray(maxSize, maxValue)
49.     printArray(arr)
50.     selectionSort(arr)
51.     printArray(arr)
53. if __name__ == '__main__':
54.     main()

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。