1.1.2.1 选择 + 冒泡排序 - qidao123.com技术社区-IT企服评测·应用市场

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

复制代码

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()

复制代码