排序算法--选择排序(Java实现) : [4 O% N2 m/ ~) x6 p1 D . t2 {" B2 j' e5 L! Y7 }1 [- `" h9 s选择排序概念 , {& p X, Z% u, x4 j 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。 --form baike 8 K9 K3 I& h2 y, O# z * ~, J+ B7 w: E8 d: t& R思想 ' P4 v5 _% _% V* 每次从待排序的数据元素中选出最小或最大的一个元素,存放在序列的起始或末尾位置 , ] g$ C/ c7 p& o5 v) |* 长度为n的数组一共需要进行n-1趟排序,每趟排序会进行一次值的交换;+ d- g% j. B& N5 W; D' H
* 当进行下一次排序时,范围缩小1( i* V& }4 [% T3 D1 f" E) r3 M
6 ~7 y j! q- V. F代码实现 + p$ p/ _: ]3 c' Opackage com.lll.datastructure.sort;) |: ]; T+ g6 p0 `4 V' d) h) R/ \
$ |5 k E$ u8 N$ d( y/ K# timport java.util.Arrays; $ O# ]8 e+ S; k& ]# w& v* }2 C. m. t4 [* G: h; A% [* h+ m
/**/ Z5 o1 _+ F( k l6 C7 i
* " r* J! e* l" a9 f1 O* @ClassName: SelectionSort + B: r$ R' l& M* @Description: 选择排序 " p4 q# D9 d3 M$ T Z3 t0 U9 ^* @Author: liulianglin + v" e' O/ R$ m S) s* @DateTime 2022年9月7日 上午9:12:13 _+ [" i8 _ h5 S8 Y
* # M( r7 R6 ?2 z/ Z* 选择排序思想: + x4 j# H! f/ }* 每次从待排序的数据元素中选出最小或最大的一个元素,存放在序列的起始或末尾位置 * Q$ H' R) E% y n2 ?* 长度为n的数组一共需要进行n-1趟排序,每趟排序会进行一次值的交换; ) U8 ~& @: Q6 ~; d# v 当进行下一次排序时,范围缩小1. ?" K: e7 ?' t2 h- N p! W+ r
*/ " O- c6 z1 b8 c4 ~3 n5 E* `4 D. [public class SelectionSort {9 Q f1 F% Z: \; j
public static void main(String[] args) { / n" \+ J a' h" Z) ^/ Y4 V // 待排序数据 , m; l# z+ S3 w. v* p, Q int[] arr = {1,3,2,4,7,54,11,34,9}; 1 E6 E- x2 l! B- M+ g9 q 7 x, J& f" N! }4 I" G+ ^% M1 m // 记录当前趟数查找到的最大值的数组下标 8 C/ R0 g* K. q4 Z+ m9 I' @$ ]0 p
int max; . j { g4 ?* y % d5 M1 V. G; \( F, b! t4 c // 交换变量 3 d) z1 M* W P+ R2 G0 t; ^- L int temp;7 l& w) o) L6 g, D
$ H1 i( b3 T. l* c
System.out.println("排序前:" + Arrays.toString(arr));$ ]7 l: \# o0 S2 B' J8 i% F
' U. b3 s. e% p" k9 Y" b; w4 K$ e // 外层控制循环需要排序的趟数 6 V n8 }. r) e& c' r& C for(int i = 0; i < arr.length - 1; i++) { ) F( o1 w. m. R // 每一趟都默认数组第一个元素为最大值 ! `! f: K. r; b! ^ max = 0;; o; U3 l+ X% W# I9 E. M
/ Q) s' l! s. P+ W4 m/ w // 内循环控制遍历数组的个数(每趟减1),并得到最大数的下标3 F, g$ G8 _ _. [' x [% V
for (int j = 0; j < arr.length - i; j++) { 3 W- N4 q- S5 S f& a: v. A if (arr[j] > arr[max]) { : X' S f$ d* J/ \ u3 a: v max = j;! m/ k B1 K: B6 s- ^" F# T
}* V* k1 L7 r* Q$ b& B
} / e9 g ?1 N6 }9 {; F8 U( M, m 2 M ?7 n/ x: |8 m; A% J' J // 将交换变量设置为最大值, 将最大值暂存一下; C8 m+ u! A( ?# b) C1 R
temp = arr[max]; 2 t7 s' \% E+ k( K // 将当前最大值设置为当前未排序序列的最后一个元素值* K O& q$ I1 r$ K3 H$ o
arr[max] = arr[arr.length - 1 - i]; 0 h: r* K7 U" V; d8 v8 H/ l$ G // 将刚才缓存的最大值,设置为当前未排序队列的最后一个元素,完成交换6 D% l3 V. P7 R, i3 R! u. v2 m8 ]
arr[arr.length - 1 - i] = temp;9 k1 K# Q$ p2 _( f/ W9 R: V1 Z2 m
}' {( Z4 J$ S; D# X+ C X: g( |
O, j8 I% `" h4 N" ]$ d; j1 t
System.out.println("排序后:" + Arrays.toString(arr)); . r6 a7 ?. J9 n, W }: |6 z1 ^. r& m$ A
} " g% ^, G& ~* X( {1 s1 s4 x/ q; T0 b0 q" `
关键步骤: 0 P" H8 j: Q% e. `: X2 ]" L* `: v- Y4 k; `) k
1. 首先定义两个变量:分别表示最大值标 和 交换变量;; I8 U; _$ i, L4 q9 @2 U- \2 p8 C
5 s% e# r+ v" O6 `3 W$ C2. 通过外层for循环,控制排序的趟数; / W* v" [$ I. v* ?7 v1 ^6 A3 P* N+ p4 ~7 q7 }) x, o! S
3. 通过内循环控制每趟需要遍历数组的次数,每趟会较上一趟减1,每次会得到最大值的下标。再下一趟外循环会将这个下标重新置为0;: u- M2 x; x' L0 F- r
% Q9 O6 c. B* Y
4. 每趟找到最大值后,将交换变量设置为最大值,目的是将最大值进行一个暂存; 9 E( d" F* c w# ~$ v d$ ]& R( U8 d5 u/ S6 N+ R4 w" B5.然后将最大值设置为当前未排序序列的最后一个元素; : C/ n/ R" b; @- w r / u Z* j: e" d6 a" D6.最后将第4步缓存的最大值,设置为的当前未排序序列的最后一个元素 ?- r k8 {$ \& F7 F y/ Q, b0 N; b) k5 N: Z: w$ m& Z
7.至此完成数据交换,继续进行步骤2,直到数据数据有序。/ F$ J7 \) S3 U1 z: H
' _! Y; ~" r+ r% Y. B! W [" m
执行结果- \* z% o4 j5 G5 A& v g