数据结构与算法之选择排序（含改进版）

（四）数据结构与算法之希尔排序

（五）数据结构与算法之归并排序

（六）数据结构与算法之快速排序

（七）数据结构与算法之堆排序

（八）数据结构与算法之计数排序

（九）数据结构与算法之桶排序

（十）数据结构与算法之基数排序

选择排序概念

========================================================================

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种

动图展示：

代码实现

======================================================================

import java.util.Arrays;

public class seletsort {

public static void main(String[] args) {

int[] arr = {4, 5, 6, 3, 2, 1};

selectSort(arr);

// [1, 5, 6, 3, 2, 4]

// [1, 2, 6, 3, 5, 4]

// [1, 2, 3, 6, 5, 4]

// [1, 2, 3, 4, 5, 6]

// [1, 2, 3, 4, 5, 6]

// [1, 2, 3, 4, 5, 6]

}

//选择排序

public static void selectSort(int[] arr) {

//遍历所有的数

for (int i = 0; i < arr.length; i++) {

int minIndex = i;

//把当前遍历的数和后面所有的数依次进行比较，并记录最小的数的下标

for (int j = i + 1; j < arr.length; j++) {

//如果后面比较的数比记录的最小的数小

if (arr[minIndex] > arr[j]) {

//记录最小的那个数的下标

minIndex = j;

}

}

//如果发现了更小的元素，与第一个元素交换位置（第一个不是最小的元素）

if (i != minIndex) {

int temp = arr[i];

arr[i] = arr[minIndex];

arr[minIndex] = temp;

}

//打印每次排序后的结果

System.out.println(Arrays.toString(arr));

}

}

}

时间复杂度

=======================================================================

• 最优时间复杂度：O(n^2)

• 最坏时间复杂度：O(n^2)

• 稳定性：不稳定（考虑升序每次选择最大的情况）

选择排序与冒泡排序一样，需要进行N*(N-1)/2次比较，但是只需要N次交换，当N很大时，交换次数的时间影响力更大，所以选择排序的时间复杂度为O(N^2)。

虽然选择排序与冒泡排序在时间复杂度属于同一量级，但是毫无疑问选择排序的效率更高，因为它的交换操作次数更少，而且在交换操作比比较操作的时间级大得多时，选择排序的速度是相当快的。

代码改进

======================================================================

传统的选择排序每次只确定最小值，根据改进冒泡算法的经验，我们可以对排序算法进行如下改进：每趟排序确定两个最值——最大值与最小值，这样就可以将排序趟数缩减一半

改进后代码如下：

import java.util.Arrays;

public class seletsort {

public static void main(String[] args) {

int[] arr = {4, 5, 6, 3, 2, 1};

selectSort(arr);

// [1, 5, 4, 3, 2, 6]

// [1, 2, 4, 3, 5, 6]

// [1, 2, 3, 4, 5, 6]

}

//选择排序改进

public static void selectSort(int[] arr) {

int minIndex; // 存储最小元素的小标

int maxIndex; // 存储最大元素的小标

for (int i = 0; i < arr.length / 2; i++) {

minIndex = i;

maxIndex = i;

//每完成一轮排序，就确定了两个最值，下一轮排序时比较范围减少两个元素

for (int j = i + 1; j <= arr.length - 1 - i; j++) {

//如果待排数组中的某个元素比当前元素小，minIndex指向该元素的下标

if (arr[j] < arr[minIndex]) {
自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Python工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Python开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上前端开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以扫码获取！！！（备注：Python）

onvert/9f49b566129f47b8a67243c1008edf79.png)

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上前端开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以扫码获取！！！（备注：Python）