Python算法札记2_选择排序

选择排序

算法思想

选择排序的思想是从待排序的数据中选出最小的值，与其最左边的数字进行交换，重复以上步骤。在序列中查找最小值使用的是线性查找。

菜鸟课程
选择排序-Python语言描述

image.png image.png

算法步骤

• 1、先用list[0]和list[1]~list[len(list)]比较，如果list[0]大，交换位置，将较小值放在list[0]即首位上。
• 2、再用list[1]和list[2]~list[len(list)]比较，如果list[1]大，交换位置，放在未排序的序列首位上。

• 3、重复1和2的过程。

  
  selectionSort.gif

# 首推看这段代码来理解选择排序
def select_sort(list1):
    n = len(list1)
    for i in range(n-1):    # i外层控制轮数，总长度为n，需要循环(n-1)轮，最后一个数无需比较；同时i也表示
        min_index = i   # 假定当前最小值的索引是i
        for j in range(i+1, n):   # 当第j轮开始比较的时候，其实是要和后面的(n-i-1)个元素进行比较
            if list1[min_index] > list1[j]:  # 如果本轮中我们假定的最小值，也就是索引为min_index处的值比后面未排序的元素要大，说明 min_index处的值不是最小的
                min_index = j  #   找到最小值元素的索引   
        list1[i], list1[min_index] = list1[min_index], list1[i]    # 退出整个循环，交换我们设定的最小值list1[i]和实际找到的最小值list1[min_index]的值，也就是上步中交换得到的list1[j]的值
    return list1
    
if __name__ == "__main__":
    list1 = [1,9,3,5,2,8,6]
    print("排序前",list1)
    select_sort(list1)
    print("排序后",list1)

image.png

def sort_list(list1):
    length = len(list1)
    for i in range(length - 1):   
        for j in range(i + 1, length):    
            if list1[i] > list1[j]:
                list1[i], list1[j] = list1[j], list1[i]
    return list1

# 参考菜鸟课程
def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

# 怎么从数组中找出最小值

def find_smallest(array):
    smallest = array[0]
    index = 0
    for i in range(1, len(array)):
        if smallest > array[i]:
            smallest = array[i]
            index = i
    return index

Python算法札记2_选择排序