阅读《算法实例精讲》第28页简单选择排序法,并用程序设计语言进行描述
时间: 2024-09-13 20:05:24 浏览: 35
51单片机C语言应用程序设计实例精讲
简单选择排序法是一种基础的排序算法,其核心思想是在每一轮选择中找到剩余未排序部分的最小(或最大)元素,然后将其放到已排序序列的末尾。具体步骤如下:
1. 初始化:设数组arr的长度为n,将未排序部分看作整个数组,即起始索引为0,结束索引为n-1。
2. 在未排序部分找到最小元素的索引minIndex。
3. 若minIndex不为当前未排序部分的最后一个元素的索引(即不在位置n-1),则将最小元素与未排序部分最后一个元素交换。
4. 将未排序部分的最后一个元素(此时为当前找到的最小元素)纳入已排序部分,将未排序部分的结束索引减1。
5. 重复步骤2至4,直到未排序部分只有一个元素(即n-1个元素已排序),此时数组已完全排序。
下面是一个简单选择排序的Python示例代码:
```python
def simple_selection_sort(arr):
n = len(arr)
for i in range(n):
# 假设最小元素的索引为当前位置i
min_index = i
# 遍历未排序的元素
for j in range(i+1, n):
# 如果发现更小的元素,则更新最小元素的索引
if arr[j] < arr[min_index]:
min_index = j
# 将找到的最小元素交换到当前位置i
arr[i], arr[min_index] = arr[min_index], arr[i]
# 示例使用
arr = [64, 25, 12, 22, 11]
simple_selection_sort(arr)
print("排序后的数组:", arr)
```
阅读全文