数据结构和算法(十四)选择排序算法
1. 数据结构和算法(十四)选择排序算法
1.1 什么是选择排序
-
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
1.2 算法基本思想
选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
-
分为三步： -
从待排序序列中，找到关键字最小的元素 -
如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换 -
从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束
1.3 选择排序复杂度分析
选择排序的时间复杂度是 ：选择排序的时间复杂度并不低，可以看到是由两个for循环构成，所以他的时间复杂度肯定是 。但是它比冒泡好在的是交换次数少，不过选择排序并不是一个稳定排序。
1.3 选择排序代码实现
package com.yuanxw.datastructure.chapter11;import java.util.Arrays;/*** 选择排序* 选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。* - 分为三步：* 1. 从待排序序列中，找到关键字最小的元素* 2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换* 3. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束*/public class SelectionSort {public static void main(String[] args) {int[] array = new int[]{10, -7, 8, -2, 5, -4};System.out.println("【选择排序】前的结果：" + Arrays.toString(array));selectionSort(array);System.out.println("【选择排序】后的结果：" + Arrays.toString(array));}public static void selectionSort(int[] array) {// 第一个位置开始比较，找最小的元素。假设最小值为：0，在比较之后如果存在还有比array[0]更小的值，则进对min进行重新复制for (int i = 0; i < array.length - 1; i++) {int min = array[i];int minIndex = i;// 查找最小for (int j = 1 + i; j < array.length; j++) {if (min > array[j]) {min = array[j];minIndex = j;}}// 判断如果不存在最小的，则不需要进行重新赋值if (minIndex != i) {array[minIndex] = array[i];array[i] = min;}}}}
执行结果：
【选择排序】前的结果：[10, -7, 8, -2, 5, -4]【选择排序】后的结果：[-7, -4, -2, 5, 8, 10]
-- 以上为《数据结构和算法(十四)选择排序算法》，如有不当之处请指出，我后续逐步完善更正，大家共同提高。谢谢大家对我的关注。
——厚积薄发(yuanxw)