🟡前言
21天挑战赛第三天，本文主要讲述有关选择排序的内容
活动地址：CSDN21天学习挑战赛
🟡概述
选择排序是指每次从待排序的元素中选出最小（或最大）的元素，并存放在序列起始位置，直至从完成小到大（或从大到小）的排序
比如在第一次排序中，要将首位中的4依次与后面的每个位置中的元素进行比较，当碰到倒数第三个位置上的2时，将两个位置中的元素对换，这里注意是将a[0] 与 a[5]中的值互换，使得 a[0]=2，a[5]=4；由于比较是将数组中下标为0的值依次与数组中下标为1~n的值进行对比，所以下一步是将首位中的2接着与数组中下标值为6-n的元素对比
所以排序的关键在于：元素下标不改变，改变的是元素下标所对应的值
🟡调用API解决
1️⃣一个构造方法和三个成员方法
构造方法
Selection()
成员方法
- public static void sort(Comparable[]a)：对数组a中元素进行排序
- public static boolean greater(Comparable x, Cpmparable y)：判断x是否大于y；
一般使用时会这么写：x.compareTo(y) ，再判断值是否 >0 , >0则表示 x>y
- public static void sort(Comparable[]a)：对数组a中元素进行排序
2️⃣解题思路
1.想要对数组内元素进行排序，就要调用public static void sort(Comparable[]a)
2.假设最小值所对应的位置是数组中第一个，这样在经过比较以后就能将最小的元素放在首位
3.数组内除了最后一个元素外，每一个元素都要与其后面所有元素比较，所以要调用一个for循环语句来保证除最后一个外，每个元素都经过比较
此处我们用 元素下标 i 来表示每个元素（因为数组下标值不变，改变的是元数组中下标值所对应的元素，如：a[0] 代表的是排序中第一个位置上的元素值，不论元素值如何改变，其位置永不改变），终止条件是最后一位之前，即 i < a.length-1
4.每经过一次循环，排序中第一位的位置也要改变为后一个位置，以供存放比较后较小的数
5.对于每个元素，都要依次与其后面的每一个元素进行比较，同理，我们用元素下标 j 来表示所要与之比较的元素
6.如果某元素后面的元素的值比它小，就交换二者位置
7.转换成字符串类型后打印输出
3️⃣代码实现
public class SelectionSort { public static void sort(Comparable[] a){ for(int i = 0; i < a.length-1; i++){ int minIndex = i;//设最小值所对应位置 for(int j = i + 1; j < a.length; j++){ //如果该元素后的值更大，则改变此时最小值对应位置 if(greater(a[minIndex],a[j])){ minIndex = j; } } exch(a,i,minIndex);//交换首位元素和最小值 } } private static boolean greater(Comparable x, Comparable y){ return x.compareTo(y) > 0; } private static void exch(Comparable[] a, int i, int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } }
public class SelectionSortTest { public static void main(String[] args) { Integer[] arr = {4,6,8,7,9,2,10,1}; BubbleSort.sort(arr); System.out.println(Arrays.toString(arr)); } }
🟡普通解法
public class test { public static void main(String[] args) { int arr[] = {4,5,6,3,2,1}; int temp = 0; System.out.println("原数组是"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } for(int i = 0; i <arr.length; i++){ int index = i; for(int j = i+1; j < arr.length; j++){ if(arr[index] > arr[j]) { index = j; } } if(index != i){ temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } } System.out.println("\n排序后数组是"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }
🟡时间复杂度
比较元素：(n-1) + (n-2) + … + 2 + 1 = 1/2 * (n^2 - n)
交换次数：n-1
总计：1/2 * (n^2 + n) - 1
时间复杂度为：O(n^2)
🟡结语
选择排序的难点在于交换数组内下标值所对应的元素值，下一篇文章将介绍插入排序
