算法札记3_选择排序

选择排序

算法思想

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

菜鸟课程
选择排序-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