vlambda博客
学习文章列表

Scratch十大经典排序算法之选择排序

选择排序算法有两种:直接选择排序和堆排序

直接选择排序算法思想:第一趟从n个元素的数据序列中选出关键字最小/大的元素并放在最前/后位置,下一趟从n-1个元素中选出最小/大的元素并放在最前/后位置类推,经过n-1趟完成排序(堆排序这里不做详解)

题目:使用Scratch编写程序,对列表中的10个数利用选择排序法排序。

简单选择排序的基本思想:第1趟,在待排序记录r[1]~r[n]中选出最小的记录,将它与r[1]交换;第2趟,在待排序记录r[2]~r[n]中选出最小的记录,将它与r[2]交换;以此类推,第i趟在待排序记录r[i]~r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。

以下为简单选择排序的存储状态,其中大括号内为无序区,大括号外为有序序列:

初始序列:{49 27 65 97 76 12 38}

  第1趟:12与49交换:12{27 65 97 76 49 38}

  第2趟:27不动 :12 27{65 97 76 49 38}

  第3趟:65与38交换:12 27 38{97 76 49 65}

  第4趟:97与49交换:12 27 38 49{76 97 65}

  第5趟:76与65交换:12 27 38 49 65{97 76}

  第6趟:97与76交换:12 27 38 49 65 76 97 完成

数据交换位置的一般方法:假设我们要交换A\B两个瓶子中的水,首先要把A瓶子里的水倒出来放入其它容器里C里,然后再把B瓶子里的水倒入到A瓶里,最后把其它容器C里的水倒回B瓶子里,这样就完成了交换,程序也是如此。例如:替换第1项与第3项,将第1项存入临时变量,然后把第1项替换为第3项,再将第3项替换为临时变量。

scratch程序如图: