经典算法---选择排序
【摘要】 选择排序的核心思想是:每一趟从无序区中选出关键字最小的元素,按顺序放在有序区的最后,新生成的有序区元素个数加1,无序区元素个数减1,知道全部排完为止
选择排序介绍
选择排序的核心思想是:每一趟从无序区中选出关键字最小的元素,按顺序放在有序区的最后,新生成的有序区元素个数加1,无序区元素个数减1,知道全部排完为止。
-
直接选择排序
也称简单选择排序,整个过程就是每一趟都将无序区中的元素进行逐一比较,找到最小的元素,与无序区中的首个元素进行交换,有序区长度加1,无序区长度减1。重复以上步骤,直到所有元素均已排好。 -
树形选择排序
也称锦标赛排序,是为了优化每次在无序区中确定最小元素时比较次数过多的问题。核心思想是借助树形结构对整个序列进行两两比较,将数值较小的元素作为优胜者上升到父节点。最后能够在树形结构中记录每一次优胜者之间的关系,按规则取出即可。 -
堆排序
堆排序是对树形选择排序的优化,由于树形选择排序需要花费较多的存储空间,堆排序的主要思想是构建一个小顶堆(升序排列中),整个过程就是不断的弹出堆顶元素,归入有序区,然后继续将堆中剩余元素调整为小顶堆,重复这个过程,直到排好所有元素。
直接选择排序
-
输入
n个数的序列,通常直接存放在数组中,可能是任何顺序。 -
输出
输入序列的一个新排列,满足从小到大的顺序(默认讨论升序,简单的修改就可以实现降序) -
算法说明
直接选择排序的主要步骤是:在第1趟中,从n个记录中找出关键字最小的记录与第一个记录交换;在第2趟中,从n-1个记录中找出关键字最小的记录与第二个记录交换;可以归纳为:从第i趟中,从n-i+1个记录中找出关键字最小的记录与第i个记录交换;直到完成i=n-1时的操作,此时整个序列有序。
伪代码
for i= 1 to n-1
k=i
for j=i+1 to n
if A[j]<A[k]
k = j
if k!=i
exchange A[i] with A[k]
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)