<<<<<<<<<<<<--------->>>>>>>>>>>>>>>>
选择排序是一种简单直观的排序算法, 而且它不会占用额外的内存空间.
原理: 遍历元素找到一个最小或最大的元素, 把它放在第一个位置, 然后再从剩余的元素中找到最小或最大的元素, 把它放在第二个位置, 依次下去, 直到完成排序.
时间复杂度为 O(n2)
思路:
给定一个数组 s[]
第一趟排序, 在待排序的 n 个元素中选出最小的一个, 将它与 s[1] 交换;
第二趟排序, 在剩下的待排序元素 s[2]~s[n] 中选出最小的一个数据, 将它与 s[2] 交换;
...
以此类推
第 n-1 趟排序, 在待排序的 s[n-1]~s[n] 中选出最小的数据, 将它与 s[n-1] 交换
排序完成.
动图演示效果:
Java 代码实现:
- public class SelectionSort {
- public static void main(String[] args) {
- int[] arr = new int[] { 5, 3, 6, 2, 10, 2, 1 };
- selectSort(arr);
- for (int i = 0; i < arr.length; i++) {
- System.out.print(arr[i] + " ");
- }
- }
- public static void selectSort(int[] arr) {
- for (int i = 0; i < arr.length - 1; i++) {
- int minIndex = i; // 用来记录最小值的索引位置, 默认值为 i
- for (int j = i ; j < arr.length; j++) {
- if (arr[j] < arr[minIndex]) {
- minIndex = j; // 遍历 i~length 的值, 找到其中最小值的位置
- }
- }
- if (i != minIndex) { // 交换当前索引 i 和最小值索引 minIndex 两处的值
- int temp = arr[i];
- arr[i] = arr[minIndex];
- arr[minIndex] = temp;
- } // 执行完一次循环, 当前索引 i 处的值为最小值, 直到循环结束即可完成排序
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3237689.html