数据结构与算法之排序算法-选择排序
排序算法是数据结构与算法中最基本的算法之一，其作用就是将一些可以比较大小的数据进行有规律的排序，而想要实现这种排序就拥有很多种方法~
那么我将通过几篇文章，将排序算法中各种算法细化的，详尽的为大家呈现出来：
📚 非线性时间比较类：
📕 插入类排序：数据结构与算法之排序算法-插入排序-CSDN博客
📖 直接插入排序
📖 希尔排序
📕 交换类排序：数据结构与算法之排序算法-快速排序(分治)-CSDN博客
📖 冒泡排序
📖 冒泡排序-优化
📖 快速排序(Hoare，挖坑法，前后指针法)
📖 快速排序-优化
📕 选择类排序：[本篇]
📖 简单选择排序
📖 堆排序
📕 归并类排序：数据结构与算法之排序算法-归并排序-CSDN博客
📖 归并排序
📚 线性时间非比较类：
📕 非比较类排序：数据结构与算法之排序算法-(计数,桶,基数排序)-CSDN博客
📖 计数排序
📖 桶排序
📖 基数排序
一、选择排序
稳定性：不稳定
时间复杂度：O(n^2)
额外空间复杂度：O(1)
选择排序是排序算法中最简单直观的排序算法之一，还记得冒泡排序吗？在冒泡排序中，我们是通过多次遍历数组，然后将此次遍历中最大的元素放到遍历范围的最后，选择排序和冒泡排序有一些相似之处：
冒泡排序的核心思想：不断寻找最大的元素并放到最后。
选择排序的核心思想：不断寻找最小的元素并放到最前。
① 选择排序(循环嵌套)
📚 算法思想：
选择排序：通过两层循环，外层循环(int i = 0;i < len - 1;i++)代表从 i 开始，进行内层循环(int j = i + 1;j < len;j++)来寻找此次循环中的最小值，并将最小值放在 i 的位置~
⭐ 图示：
📖 代码示例：
public static void selectionSort(int[] arr){
int len = arr.length;
for(int i = 0;i < len - 1;i++){
int minIndex = i;
for(int j = i + 1;j < len;j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
swap(arr,i,minIndex);
}
}② 选择排序(双指针)
📚 算法思想：
通过每次迭代同时找到当前范围内的最大值和最小值，并且将它们分别放到数组的两端，这样可以减少直接插入排序算法的迭代次数，做到提高效率(但其实没卵用...)
使用两个指针left和right，分别指向数组的起始位置和结束位置
每次迭代中，找到当前范围内[left,right]的最小值和最大值
将最小值放到left位置，将最大值放到right位置
然后缩小范围，left++，right--，直到left和right相遇。
📖 代码示例：
public static void selectSort2(int[] array){
int left = 0;
int right = array.length - 1;
while(left < right){
int minIndex = left;
int maxIndex = left;
System.out.println(Arrays.toString(array));
for(int i = left + 1;i <= right;i++){
if(array[minIndex] > array[i]){
minIndex = i;
}
if(array[maxIndex] < array[i]){
maxIndex = i;
}
}
swap(array, left, minIndex);
if(left == maxIndex){
maxIndex = minIndex;
}
swap(array, right, maxIndex);
left++;
right--;
}
}(可以实现一下用来练习自己的代码能力，实际应用的话还是算了，时间复杂度为O(n^2)不说，还不具有稳定性，代码长度甚至可以和优化过的快速排序一拼了也是难绷...连冒泡排序都不如...)
二、堆排序
稳定性：不稳定
时间复杂度：O(n logn)
额外空间复杂度：O(1)
堆排序的时间复杂度和快速排序一样，也是O(n logn)，这是一种非常快速的排序了，并且它的额外空间复杂度为O(1)，这也使得它在实际应用中也比较广泛。
📚 算法思想：
堆排序的思想也是很简单的，在之前我们学习过"优先级队列"，也可以分为"大根堆"，"小根堆"。
不清楚什么是"优先级队列"，不认识"大根堆"，"小根堆"的可以去我之前的文章中进行学习：
Java-数据结构-优先级队列(堆)_java优先级队列获取大根堆-CSDN博客
Java-数据结构-优先级队列(堆的使用)-CSDN博客
而堆排序的实现，就是以堆中的各种方法组合起来实现的：
首先，我们需要先将数组创建成一个"大根堆"，这样我们就能够做到轻易地获取数组中的最大元素。
然后对这个"大根堆"的堆顶元素(最大元素)不断的放到最后，并进行删除操作(假意的删除，其实只是在后续操作中不再访问该元素)，这样直到最后，我们就能得到一个升序数组。
在这个过程中，我们需要实现"创建大根堆"，"向下调整"的方法，而这些方法在上面两篇博客链接中也有详细的讲解，可以移步到上述两篇博客中进行学习~
⭐ 图示：
📖 代码示例：
public void heapSort(int[] array){
//构造一个大根堆
createHeap(array);
int len = array.length;
for(int i = len - 1;i > 0;i--){
//将array[0]放到最后(最大的数放到最后)
swap(array,0,i);
//向下调整,再次变成大根堆(堆到后面的大数不再调整)
siftDown(array,0,i);
}
}
public void createHeap(int[] array){
int index = array.length;
//从最后一个父结点开始,依次将父结点向前进行向下调整
for(int parent = (index - 1 - 1) / 2;parent >= 0;parent--){
siftDown(array,parent,index);
}
}
public void siftDown(int[] array,int parent,int len){
int child = 2 * parent + 1;
while(child < len){
if(child + 1 < len && array[child + 1] > array[child]){
child = child + 1;
}
if(array[child] > array[parent]){
swap(array,child,parent);
parent = child;
child = parent * 2 + 1;
}else {
break;
}
}
}那么这篇关于选择排序的文章到这里就结束啦，作者能力有限，如果有哪里说的不够清楚或者不够准确，还请各位在评论区多多指出，我也会虚心学习的，我们下次再见啦