选择排序思路、分析过程

ajiao111 0

1、思路:

将数组分为左右两部分,左边放置的是有序的元素,右边放置的是无序的元素,每次从无序的部分找出最小的元素放到左边有序的部分。始终从右边未排序部分选择一个最小的放到左边已排序部分的末尾

第一次遍历

  • 第一次遍历,假设0号索引位置的元素是最小值【min_index = 0】
  • 其他每个元素都与0号索引位置元素对比,如果值比0号索引位置元素小,则将min_index赋值为当前最小元素的索引【如上图min_index从0变为6】,因此游标 i需要从0索引位置走到n-1索引位置。用for循环表示为for i in range(1,n)
  • 遍历完成后,交换0号元素和最小值元素的位置。经过第一次遍历后,便可以将数组中最小的元素排在数组0号索引位置

多次遍历

  • 第二次遍历,因为0号索引已经排好,所以假设1号索引位置是最小值【min_index = 1】
  • 重复上述交换min_value步骤,就可以把第二小的元素放到1号索引的位置
  • 遍历完成后,左边排序好的元素便会增加一个次小的元素
  • 经过上面的分析可以发现,每遍历一次,起始元素的索引都加1。另一方面,我们只需要确定n-1个数的位置,便可以确定所有元素的位置。【n-1个元素位置确定后,剩下一个位置的元素就可以确定】因此,我们假设起使游标的位置是 j,j只需要走到n-2索引的位置,便可以确定所有元素的位置。range()函数左闭右开,所以可以确定for j in range(0,n-1)
  • 对应的,只需要将上面第一次遍历的代码部分的0索引改为j索引即可

发表评论