🟡前言
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)
🟡结语
选择排序的难点在于交换数组内下标值所对应的元素值,下一篇文章将介绍插入排序