...
 Algorithms

『Selection Sort』详解「选择排序」的Python实现

...
hokyo
发布于 4 年, 8 ヶ月 之前
2103
0

选择排序

选择排序就是从一堆数组里面挑选一个最大（最小）的，放在最前后面。大O(n2)。

本质上就2个步骤

  • 找最大的value
  • 放在最前面或者最后面

The first two items in [1, 2, 7, 8, 4, 3, 6] are sorted. 3 is the smallest item in the unsorted portion ([7, 8, 4, 3, 6]). Swapping 3 with 7, we have [1, 2, 3, 7, 4, 7, 6] and the first three items are sorted.

思路1

"""  
1. find_smallest_index()辅助方法实现找到最小的值  
2. select_sort()才是排序本体  
"""  
# 找最小  
def find_smallest_index(number):  
    # 把索引第1个当最小  
    # 记录下索引  
    small_number = number[0]   
    small_index = 0  
    # 开始遍历找到最小的那个  
    for i in range(len(number)):  
        # 你竟然ß比我假想的最小的还小，好吧。我称你为最小。  
        # 记录下最小的value和index  
        # 然后接着循环循环，一直找到最小的那个的index！  
        if number[i] < small_number:  
            small_number = number[i]  
            small_index = i  
    return small_index           

def select_sort(arr):  
    new_list = []  
    for i in range(len(arr)):  
        small_index = find_smallest_index(arr)  
        new_list.append(arr.pop(small_index))  
    return new_list  

print(select_sort([5,6,90,2,89]))  

# result  
# [2, 5, 6, 89, 90]

思路2

比思路1简洁很多，也是网上貌似比较多的。
参考链接：选择排序 Selection Sort

俩loop是最最最重要的
第1个loop是为了验证是数组里所有的数
第2个loop是通过交换为了找出来最小的数的index，index，index！

也就是说里面那一层遍历最后得到的是最小的数 

def select_sort(arr):  
    for i in range(len(arr)):  
        # 默认第1个为最小value，记录下index  
        min_idx = i  
        # 因为要对比，所以从第2个开始loop  
        for j in range(i+1,len(arr)):  
            if arr[j] < arr[min_idx]:  
                # 找出最小value的index  
                min_idx = j  
        arr[i],arr[min_idx] = arr[min_idx],arr[i]         
    return arr  

print(select_sort([5,6,90,2,89]))  

# result  
# [2, 5, 6, 89, 90]
#Python #算法 #选择排序

共有评论(0)

登陆即可评论哦