算法系列1—排序算法之选择排序(SelectionSort)

本文主要是介绍算法系列1—排序算法之选择排序(SelectionSort)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原理简介

遍历元素找到其中最小（或最大）的那个元素，把它放在第一位；
然后再在剩余元素中遍历元素找到最小（或最大）的那个元素，把它放在第二位；
依次下去，完成排序。

代码实现

public class SelectionSort {public static void selectSort(int[] arr) {for (int index = 0; index < arr.length; index++) {for (int compareIndex = index + 1; compareIndex < arr.length; compareIndex++) {if (arr[index] > arr[compareIndex]) {swap(arr, index, compareIndex);}}}}private static void swap(int[] arr, int index, int compareIndex) {int temp = arr[index];arr[index] = arr[compareIndex];arr[compareIndex] = temp;}public static void main(String[] args) {int[] arr = {3, 5, 12, 9, 43, 7, 32};selectSort(arr);for (int i : arr) {System.out.print(i+"  ");}}
}

时间复杂度

选择排序的时间复杂度为O(n^2)
从代码中可以看出一共遍历了
n + n-1 + n-2 + … + 2 + 1 = n * (n+1) / 2 = 0.5 * n ^ 2 + 0.5 * n
那么时间复杂度是O(n^2)。

这篇关于算法系列1—排序算法之选择排序(SelectionSort)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---