排序算法-选择排序
1. 简单选择排序Select Sort
1.1 Select Sort介绍
简单选择排序（select Sort）的基本思想是：每一轮排序都从待排序的序列（无序区）中选取一个最小值，并将其与无序区的第一个元素进行交换，此时有序区长度 + 1，无序区长度 - 1。重复上述过程直至整个序列完成排序。
1.2 图解说明Select Sort步骤
举一个例子来具体说明Select Sort的过程。给出一个无序数列：5，3，6，4，7，1，8，2使用简单选择排序将其排列成一个从小到大的有序数列。
- 初始无序序列长度为nums.length = 8，首先选择nums[0]作为当前无序区的最小值min，并逐一将min与无序区的所有元素进行比较，找出无序区中的实际最小值，即min = nums[5]，然后将min与nums[0]交换，即构成有序区
1，无序区3，6，4，7，5，8，2； - 第二轮再次从无序区中选择nums[1]作为最小值min，并逐一与无序区中所有元素进行比较，找出实际最小值min = nums[7]，将min与nums[1]交换，构成有序区
1，2，无序区6，4，7，5，8，3； - 重复执行上述过程，完成后面几轮排序。每一轮排序都使得有序区长度 + 1，无序区长度 - 1。需要注意的是，每一趟排序过后，最前面的一个数（即最小的数）即被确认不再参与后续选择排序过程。
1.3 简单选择排序规则
- 一共需要进行nums.length - 1轮排序；
- 需要创建两个临时变量min和minIndex，分别用于记录最小值和最小值所在的位置（数组下标）；
- 每一轮排序中都会确认该轮的无序区的最小数，并经过交换放入有序区，因此每一轮排序过后，有序区长度 + 1， 无序区长度 - 1；
- 每一轮排序中至多仅进行一次交换，即将无序区中的实际最小值min与无序区的第一个元素进行交换；
- 至多仅交换一次的意思是，如果当前轮的比较过程中，min的值和minIndex索引值没有发生改变，即一直是该轮排序开始时指定的minIndex = i，那么就不需要交换；仅当minIndex != i时才执行交换；
- 时间复杂度：最坏情况O(\(n^2\))，平均时间复杂度O(\(n^2\))。
1.4 代码实现
package com.algorithm;
import java.util.Arrays;
/**
* @author SnkrGao
* @create 2023-04-13 16:55
*/
public class SelectSort {
public static void main(String[] args) {
int[] nums = {5,3,6,4,7,1,8,2};
System.out.println("排序前的数组为：");
System.out.println(Arrays.toString(nums));
System.out.println("---------------------------------");
selectSort(nums);
System.out.println("---------------------------------");
System.out.println("排序后的数组为：");
System.out.println(Arrays.toString(nums));
}
public static void selectSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) { // 一共进行nums.length - 1轮排序
int min = nums[i]; // 排序开始前，首先令每轮排序中的无序区的第一个元素为min
int minIndex = i; // 并记录该min值的下标
// 每轮排序都是将min与其后的每一个元素进行比较，因此内层循环从i + 1开始
for (int j = i + 1; j < nums.length; j++) {
if (min > nums[j]) { // 发现新的最小值，重置min和minIndex
min = nums[j];
minIndex = j;
}
}
// 仅当minIndex发生了变化时，即比较过程中重置了min和minIndex，才进行交换
if (minIndex != i) {
nums[minIndex] = nums[i];
nums[i] = min;
}
System.out.println("第" + (i + 1) + "轮排序结果为：");
System.out.println(Arrays.toString(nums));
}
}
}
2. 堆排序 Heap Sort
2.1 Heap Sort介绍
-
Heap Sort是利用堆（heap）这种数据结构而设计的一种排序算法，堆排序是一种选择排序，同时也是一种不稳定的排序算法；
-
堆是一种具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆；而每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆；大顶堆和小顶堆都不要求左孩子节点的值与右孩子节点的值的大小关系；
注：完全二叉树是指一颗深度为 k 有 n 个节点的二叉树，对其树中节点按从上至下、从左至右的顺序编号，若编号为 i 的节点与满二叉树中编号为 i 的节点在树中的位置相同，则称为完全二叉树。
-
可以用一个一维数组来表示堆，其中节点 i 的父节点和左右孩子节点的index分别为：
- parent(i) = (i - 1) / 2 （取整）；
- leftChild(i) = i × 2 + 1；
- rightChild(i) = i ×2 + 2；
-
一般要求升序排列时采用大顶堆，降序排列时采用小顶堆。
2.2 Heap Sort基本思想
- 首先将待排序序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的根节点；
- 将堆顶根节点与末尾元素进行交换，此时末尾就成了最大值；
- 将剩余n - 1个元素再次构造大顶堆，得到剩余n - 1个元素中的最大值，反复执行上述步骤即可得到一个有序序列。
2.3 图解说明Heap Sort步骤
举一个例子来具体说明Heap Sort的过程。给出一个无序数列：4，6，8，5，9使用堆排序将其排列成一个从小到大的有序数列。
- 初始待排序序列结构如图：
-
从最后一个非叶子节点（其索引为 arr.length / 2 - 1）开始调整堆结构，每次调整时遵循从右往左，从下往上的规则去找非叶子节点。找到非叶子节点后，先根据 leftChild = i × 2 + 1 找其左孩子节点，并判断其是否有右孩子节点，若有则比较两个孩子节点，得到两个孩子节点中的较大值；之后将孩子节点中的较大值与该非叶子进行比较，若大则交换位置；
eg.上图结构中，最后一个非叶子节点为arr[1] == 6，其左右孩子的较大值arr[2 × 1 + 2] == arr[4] == 9 > arr[1]，交换其位置
为什么最后一个非叶子节点为 n / 2 - 1 ？可以分以下两种情况考虑：
- 最后一个非叶子节点只有左孩子：那么左孩子的序号为n - 1，而根据leftCild(i) = i × 2 + 1，即n - 1 = i × 2 + 1，推出 i = n / 2 - 1；
- 最后一个非叶子节点有左右两个孩子：那么其左孩子序号为n - 2 = i × 2 + 1，推出 i = (n - 1) / 2 - 1，而右孩子序号n - 1 = i × 2 + 2，推出 i = (n - 1) / 2 - 1。
- 当完全二叉树的最后一个节点是左孩子节点时，整个树的节点数n为偶数；当是右孩子节点时，整个树的节点数n为奇数。由于整数除不尽时要向下取整，因此当n为奇数时，(n - 1) / 2 - 1 = n / 2 - 1。
- 继续按照前述的规则找到下一个非叶子节点arr[0] == 4，并继续按照上面的步骤得到其左右孩子的较大值arr[1] == 9 > arr[0]，交换其位置。
-
此时发现上一步的交换导致了以被交换位置arr[1]为非叶子节点的局部树结构的结构混乱，不符合大顶堆的性质，因此需要继续向下调整。（也即这一部分也需要写入调整堆结构adjustHeap的代码中，将前一步调整中被交换的较大值（孩子节点）的位置认为是新的非叶子节点，并继续按上述步骤比较其孩子节点与该节点的大小并交换）
eg.上图中交换导致了arr[1]为非叶子节点的结构不符合大顶堆的性质，因此继续调整，比较发现其右孩子节点arr[4] == 6 > arr[1]，交换其位置
-
此时已经将无序序列构造成了一个大顶堆，接下来将堆顶元素与末尾元素进行交换，使末尾元素最大。然后排除掉已经确定的最大元素，将剩余的序列重新调整堆结构；
eg.上图中将堆顶元素9与末尾元素4进行交换，得到新的序列
4，6，8，5，9，将元素9用虚线隔开，对剩余的元素重新构造大顶堆
- 反复进行上述的交换和调整过程，最终使得整个序列有序。但需要注意的是，将堆顶元素与末尾元素交换的过程只需要进行nums.length - 1次，因为每次都会确定一个最大元素，当确定了nums.length - 1个元素之后，最后一个元素已经在其应在的位置。另外，每次交换完后再次调整堆结构时，仅需要以arr[0]为非叶子节点调整剩余的无序序列长度的堆结构，这是因为每一次交换都已经确定了剩余元素中最大元素的位置。
2.4 代码实现
package com.algorithm;
import java.util.Arrays;
/**
* @author SnkrGao
* @create 2023-04-13 22:23
*/
public class HeapSort {
public static void main(String[] args) {
int[] nums = {6,4,2,8,3,1,9,7,5,0};
System.out.println("排序前的数组：");
System.out.println(Arrays.toString(nums));
heapSort(nums, nums.length);
System.out.println("排序后的数组：");
System.out.println(Arrays.toString(nums));
}
/**
* 每一次调用都是对传入的非叶子节点的局部树结构调整为堆
* @param nums 待排序序列
* @param parent 传入的非叶子节点index
* @param length 待排序序列的长度
*/
public static void adjustHeap(int[] nums, int parent, int length) {
int temp = nums[parent]; // 临时变量先保存该非叶子节点的值，用于后面的交换
/**
* child = parent * 2 + 1 是在找该非叶子节点的左孩子节点
* child = child * 2 + 1 是对当前非叶子节点的局部树结构调整完成后，继续以被交换的孩子节点
* 继续以被交换的孩子节点为新的非叶子节点向下调整，即令parent = child
*/
for (int child = parent * 2 + 1; child < length; child = child * 2 + 1) {
// 判断是否有右孩子节点，且令child为左右孩子节点的较大值index
if (child + 1 < length && nums[child] < nums[child + 1]) {
child++;
}
/**
* 若上述较大值大于该非叶子节点的值，就进行"交换"，并将parent赋值为被交换的child
* 以这个child为新的非叶子节点向下调整，继续找其左孩子节点
* ！！！注意此处比较的是temp的值，为了降低复杂度，该处并没有进行实际交换，
* ！！！而是将temp赋值给最后向下调整完的位置完成交换的步骤，
* ！！！但在逻辑上认为已经将temp的值放到了被交换的child也即新的parent处
*/
if (nums[child] > temp) {
nums[parent] = nums[child];
parent = child;
} else {
break; // 若不发生交换说明局部已经符合大顶堆的性质，直接跳出循环
}
}
nums[parent] = temp;
}
public static void heapSort(int[] nums, int length) {
int temp = 0; // 临时变量用于后续交换
// 从最后一个非叶子节点开始，从右向左从下向上找非叶子节点，并调用adjustHeap调整堆结构
// ！！！注意 i 一定要 >= 0，因为根节点也是非叶子节点
for (int i = length / 2 - 1; i >= 0; i--) {
adjustHeap(nums, i, length);
}
// 只需进行nums.length - 1次堆顶元素与末尾元素的交换，因此 i > 0
// 为了方便直接将 j 初始定义为 length - 1，表示末尾元素
for (int j = length - 1; j > 0; j--) {
temp = nums[0];
nums[0] = nums[j];
nums[j] = temp;
// 堆顶与末尾交换后，只有新的堆顶的树结构需要调整，而新的末尾已经确定不再参与
// 因此需要调整的序列长度length应减去已经确定的元素的长度，即为j
adjustHeap(nums, 0, j);
}
}
}
2.5 Heap Sort时间复杂度分析
最坏情况时间复杂度：O(\(nlogn\))
平均时间复杂度：O(\(nlogn\))
标签：nums,交换,length,选择,算法,child,排序,节点 From： https://www.cnblogs.com/SnkrGao/p/17318578.html