Java基础 选择排序实例



一、选择排序

1、 核心思想

简单选择排序的基本思想是：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2、算法分析

Java基础 选择排序实例

初始状态：给定待排序的序列 arr，包含 n 个元素。
第一次遍历：从第一个元素开始，依次与后面的元素比较，找到最小的元素，将其与第一个元素交换位置。
第二次遍历：从第二个元素开始，依次与后面的元素比较，找到最小的元素，将其与第二个元素交换位置。
重复步骤2和步骤3，直到倒数第二个元素和最后一个元素比较完毕。
这样经过 n-1 次遍历后，整个序列就排好序了。

3、代码实现

对于选择排序可以进一步改进，即一次遍历找到最大和最小的元素

注意事项

• 对于两种实现方法，或一但没有写函数会陷入死循环
• 对于优化版本中的则是为了防止最大值位置在此时待排序元素的头部，由于先进行最小值的交换，假如最大值在头部，则此时最大值的位置应该在最小值开始的位置即。

二、堆排序

1、基础知识

堆的结构可以分为大根堆和小根堆，是一个完全二叉树，而堆排序是根据堆的这种数据结构设计的一种排序。

• 大根堆：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆
  
  

• 小根堆：每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆
  
  

1.父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）
2.左孩子索引：2i+1
3.右孩子索引：2i+2
所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质：
大根堆：arr(i)>arr(2i+1) && arr(i)>arr(2i+2)
小根堆：arr(i)<arr(2i+1) && arr(i)<arr(2i+2)

2、 核心思想

若在输出堆顶的最小值(最大值)后，使得剩余n-1个元素序列重新建成一个堆，则得到n个元素的次小值(次大值)…如此反复，便能得到一个有序序列，这个过程称之为堆排序。(每次从堆顶取一个元素)

• 升序：建大堆
• 降序：建小堆

3、算法分析

1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

构造堆
向下调整构造堆

从最后一个父节点开始，与子节点比较，小于子节点则交换，一直到根节点。最后一个节点为则其父节点为即

4、代码实现

• 构造大根堆，升序排列

• 构造小根堆，降序排列

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.bianchenghao6.com/h6javajc/25732.html