选择排序是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。以下是一个不使用Python内置sort()方
选择排序是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。以下是一个不使用Python内置sort()方法的手写选择排序算法实现:
def selection_sort(arr):
# 遍历整个数组
for i in range(len(arr)):
# 假设当前位置的元素是最小值
min_index = i
# 与当前位置之后的元素进行比较
for j in range(i+1, len(arr)):
# 如果发现更小的元素,更新最小值的索引
if arr[j] < arr[min_index]:
min_index = j
# 将找到的最小元素与当前位置的元素交换
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# 测试选择排序算法
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:")
print(arr)
sorted_arr = selection_sort(arr)
print("排序后的数组:")
print(sorted_arr)
在这个实现中,我们首先遍历数组的每个元素,然后在每次迭代中,我们会查找从当前位置到数组末尾的最小值,并将其与当前位置的元素交换。这个过程会一直重复,直到数组完全排序。
选择排序的时间复杂度为O(n^2),其中n是数组的长度。这是因为算法需要遍历数组n次,并且在每次遍历中,它还需要查找从当前位置到数组末尾的最小元素,这个过程本身也需要O(n)的时间。
虽然选择排序在实际应用中效率不高,特别是对于大数据集来说,但它的原理简单,易于理解,并且对于小数据集或者教学目的来说是非常有用的。
暂无管理员
粉丝
0
关注
0
收藏
0