选择排序--自学笔记

选择排序

学习目标：

1.选择排序的基本思想

2.二元选择排序

3.冒泡排序和选择排序的异同

4.复杂度分析

1.选择排序的基本思想

1.1基本思想

双重循环遍历数组，每经过一轮比较，找到最小或最大元素的下标，将其换至首位!

经过六轮选择，完成排序

1.2代码实现

publicstaticvoidselectSort(int[]arr){intminIndex;intlen=arr.length;for(inti=0;i<len-1;i++){minIndex=i;for(intj=i+1;j<len;j++){if(arr[j]<arr[minIndex]){minIndex=j;}}swap(arr,i,minIndex);}}

2.二元选择排序

2.1 二元选择排序的思想

既然一次选择中要找出最小值，何不把最大值也找出来

2.2 代码实现

publicstaticvoidselectSort(int[]arr){intminIndex,maxIndex;intlen=arr.length;for(inti=0;i<len-1;i++){minIndex=i;maxIndex=i;//每轮最末尾 i 位 已有序for(intj=i+1;j<len-i;j++){if(arr[j]<arr[minIndex]){minIndex=j;}if(arr[j]>arr[maxIndex]){maxIndex=j;}}//min == max 说明所有元素相等 提前退出if(minIndex==maxIndex)break;swap(arr,i,minIndex);//当前数组的末尾下标 len - 1 - i//特殊情况：此时maxIndex == i//而 i 刚刚与 minIndex 互换//更新为 maxIndex = minIndexif(maxIndex==i)maxIndex=minIndex;swap(arr,len-1-i,maxIndex);}}

3.冒泡排序和选择排序的异同

3.1 相同点

1.都是两层循环，时间复杂度为O(n²)

2.都只使用有限个变量，空间复杂度为O(1)

3.2 不同点

1.冒泡排序在比较过程中不断交换

2.选择排序增加一个变量保存最小值/最大值的下标，遍历完成后才交换，

减少了交换的次数

*3.冒泡排序是稳定的，而选择排序是不稳定的

3.3 排序算法的稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，

若经过排序，这些记录的相对次序保持不变，即

在原序列中，r[i] = r[j] ，且r[i] 在 r[j] 之前，而在排序后的序列中，

r[i] 仍在 r[j] 之前，相对顺序依然不变，

则称这种排序算法是稳定的；

否则称为不稳定的

3.4 什么情况下要用的排序算法的稳定性？

将要排序的内容是一个对象的多个属性，

且其原本的顺序存在意义，

如果要在二次排序后保持原有排序的意义，

则需要用到稳定性

4.复杂度分析

1.时间复杂度：O(n²)

2.空间复杂度：O(1)

215. 数组中的第K个最大元素 - 力扣（LeetCode）

2.空间复杂度：O(1)

215. 数组中的第K个最大元素 - 力扣（LeetCode）