排序算法(二)选择排序

xiaoxiao2021-03-01  36

一、算法的基本思路 1.进行选择排序排序就是把所有的元素扫描一遍,从中选择最小的一个元素,最小的元素和最左边的元素交换位置,即到0号位置。 2.现在最左边的元素是有序的,不需要再交换位置了,再次扫描元素时,就从1号位置开始,还是寻找最小的,然后和1号位置的元素交换。 3.每进行完一趟排序,就多一个元素有序,并被安排在左边,下次再找新的最小值就可以少考虑一个元素,持续进行这个过程直到所有元素都排定


二、示例说明 初始元素:8 2 16 9 7 4 6 第一趟排序: 2 8 16 9 7 4 6(第一趟排序,比较6次,未排序最小值2放在0号位置) 第二趟排序: 2 4 16 9 7 8 6(第二趟排序,比较5次,未排序最小值4放在1号位置) 第三趟排序: 2 4 6 9 7 8 16(第三趟排序,比较4次,未排序最小值6放在2号位置) 第四趟排序: 2 4 6 7 9 8 16(第四趟排序,比较3次,未排序最小值7放在3号位置) 第五趟排序: 2 4 6 7 8 9 16(第五趟排序,比较2次,未排序最小值8放在4号位置) 第六趟排序:2 4 6 7 8 9 16(第六趟排序,比较1次,未排序最小值9放在5号位置) 三、算法实现

public class SelectionSort { public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap(arr, i, minIndex); } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }

四、时间复杂度、空间复杂度和稳定性 1、时间复杂度

单选择排序的比较次数与序列的初始排序无关。假设待排序的序列有 N 个元素,则比较次数永远都是N (N - 1) /2 而移动次数与序列的初始排序有关。 当序列正序时,移动次数最少,为 0。 当序列反序时,移动次数最多,为3N (N - 1) / 2。 所以,综上,简单排序的时间复杂度为 O(N^2)。

2、空间复杂度

选择排序过程中元素进行交换,所需要的额外空间为1,因此空间复杂度为O(1)。

3、稳定性

选择排序在排序过程中,元素交换时,相同元素的前后顺序可能改变,所以选择排序是一种不稳定排序算法。 比如:一组元素为4 4 4 1,第一趟排序1和第一个4交换,第一个4到了第二,三个4的后面。

转载请注明原文地址: https://www.6miu.com/read-3450266.html

最新回复(0)