数据结构与算法之排序算法-选择排序

排序算法是数据结构与算法中最基本的算法之一，其作用就是将一些可以比较大小的数据进行有规律的排序，而想要实现这种排序就拥有很多种方法~

那么我将通过几篇文章，将排序算法中各种算法细化的，详尽的为大家呈现出来：

📚 非线性时间比较类：

📕 插入类排序：数据结构与算法之排序算法-插入排序-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; } } }

那么这篇关于选择排序的文章到这里就结束啦，作者能力有限，如果有哪里说的不够清楚或者不够准确，还请各位在评论区多多指出，我也会虚心学习的，我们下次再见啦