思想:
每次从未排序的部分找出最小的元素,将其放到已排序部分的末尾
从数据结构中找到最小值,放到第一位,放到最前面,之后再从剩下的元素中找出第二小的值放到第二位,以此类推。
实现思路:
- 遍历数据结构,找到最小值,放到第一位
- 从剩下的部分找到第二小的值,放到第二位
- 重复上述过程,直到整个排序完成
视频实现:
文字描述如上,以下是选择排序的视频全过程
选择排序全过程
代码实现:
接下来是选择排序的代码实现:
java"> //传入一个数组,用来进行排序
public static void SelectionSort(int[] arr){ //外层循环是用来控制排序的层次的 for(int i = 0 ; i< arr.length-1; i++){ int minIndex = i; //内层循环是为了在没有进行排序的元素中找到最小的元素 for(int j = i+1 ; j< arr.length;j++){ if(arr[j] < arr[minIndex]){ minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; }
}
外层循环是用来控制排序的层次的 ,所以如下:
for(int i = 0; i < arr.length-1; i++)
内层循环的目的是为了在没有进行排序的元素中找到最小的元素
for(int j = i-1; j < arr.length; j++)
时间复杂度分析:
啊~ 选择排序的时间复杂度嘛,哼哼,这个问题可是很有意思的哦!让我给你详细分析一下,保证你完全明白!(。•̀ᴗ•́。)
选择排序时间复杂度分析:
选择排序的基本思想就是 每次从未排序的部分找出最小的元素,将其放到已排序部分的末尾。它的核心是通过两层循环来完成排序:外层循环控制排序轮次,内层循环负责找最小值。
1. 外层循环的复杂度
外层循环从数组的第一个元素开始,到倒数第二个元素为止。假设数组的长度为 n
,那么外层循环的次数就是 n - 1
。所以外层循环的复杂度是 O(n)。
2. 内层循环的复杂度
对于每次外层循环,内层循环会从外层循环当前位置之后的元素开始,遍历剩下的所有元素。具体来说:
- 第一次外层循环:内层循环会从第 1 个元素开始遍历到最后一个元素,总共遍历
n-1
次。 - 第二次外层循环:内层循环会从第 2 个元素开始遍历到最后一个元素,总共遍历
n-2
次。 - 第三次外层循环:内层循环会从第 3 个元素开始遍历到最后一个元素,总共遍历
n-3
次。 - 以此类推……直到最后一次外层循环只遍历一个元素。
所以内层循环的总遍历次数就是:
[
(n-1) + (n-2) + (n-3) + \dots + 1
]
这个和是一个等差数列,我们可以使用等差数列求和公式:
[
S = \frac{n(n-1)}{2}
]
所以内层循环的复杂度是 O(n²)。
3. 总时间复杂度
选择排序的总时间复杂度是外层循环和内层循环的复杂度之和。
- 外层循环:O(n)
- 内层循环:O(n²)
因此,选择排序的总时间复杂度是 O(n²)。
4. 空间复杂度
选择排序是一个 原地算法>排序算法,意味着它只需要常数级别的额外空间。只用了一个变量 minIndex
来记录最小值的位置,空间复杂度就是 O(1)。
总结:
- 时间复杂度:选择排序的时间复杂度是 O(n²),因为它有两层嵌套循环。
- 空间复杂度:空间复杂度是 O(1),因为它是一个原地排序,不需要额外的空间。
为什么时间复杂度是 O(n²)?
- 选择排序每一次外层循环都会执行一次内层循环,内层循环的次数逐步递减,但总体来说,它的时间复杂度是平方级的(O(n²))。