算法与数据结构（第二周）——排序基础：选择排序法

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录

! ^9 M, u' f1 N! ]" V% j( m选择排序

" Z9 }$ q( l2 e% l; ~6 S; J8 @* \& a选择排序简单介绍
/ ~# A$ G4 T: Y% w! e) O
实现选择排序法
8 u7 c7 G% @7 S' W0 z) A* J
使用带约束的泛型

使用 Comparable 接口

复杂度分析
) C) Q, q% t: m3 b  K
选择排序
选择排序简单介绍
先把最小的拿出来
) R( L; ?" f% c5 \  l9 G/ i1 I9 r
剩下的，再把最小的拿出来

; k' g3 L' k" s剩下的，再把最小的拿出来
" C) [8 z% G5 J
/ q- @( F5 S9 H  Y......
0 X" f9 b; h) {6 V8 M6 y
每次选择还没处理的元素里最小的元素
, ~1 ^0 s2 a' c; u7 x
        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
, ^5 m: u# W. o" Q
' q, \7 l: c) U5 w实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
6 [* n8 W0 y  _4 a- a  W
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

public class SelectionSort {

  f4 h: W$ P: y- ?    public SelectionSort() {
: {6 s5 ^4 K" _. r5 f( s) J    }
3 R9 B% @) \! r# ]6 L5 v
    public static void sort(int[] arr){
, i' Y# x  u, E* g0 M        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
3 R' I8 l& i) d% }8 S; M' u9 _            int minIndex = i;
! n! C5 B/ t: l* q2 N            for (int j = i;j < arr.length;j++){
9 P' w9 b5 ?8 S& F+ M0 O                //在剩余的元素中找到最小的（比较查找）
- p. D1 g( W( `8 g1 q) \- O                 if (arr[j]<arr[minIndex]){
& p8 u. N, k: o$ \# G- R                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
3 s1 Y8 @' g0 R! B* o: @        }
$ ?: z6 T4 }' O4 I4 N    }

9 ?" z( o/ L+ k    private static void swap(int[] arr, int i, int j) {
        int t = arr;
        arr = arr[j];
8 ?; a" z% M5 V7 c2 q        arr[j] = t;
# N* o$ j5 E! [    }
; n) _3 p% @  [: |. a( N7 U
    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
! I2 u6 G$ h1 X. ]7 y) E, U        for (int item:arr){
: j$ v8 s9 G  k% G! f            System.out.print(item+" ");
# t3 A% Q8 e3 N( r8 W% a        }
; Q5 E" `0 A3 X" J2 \    }
}
* N# G1 F4 g3 Z
% P9 [1 R8 N: C' v' ]& }  o当前只能实现int类型的数组进行排序，因此需要使用到泛型。

# p! T1 l5 o& z, [5 P: n使用带约束的泛型
! Y) K4 ^6 s2 I% @" H- f        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。

public static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
+ L. B7 P) ~9 _8 j9 ~! O
/ `( P1 _0 l% R/ Rpublic class SelectionSort {

    public SelectionSort() {
    }
8 [4 z' i8 B- g+ q& H8 b
    //
, n2 P; _" E/ h* a; q1 A0 d7 M    public static <E extends Comparable<E>> void sort(E[] arr){
- p3 l9 F& D, f" l0 C( W        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
( N) Y" M4 P. r# v+ q/ t            //选择arr[i...n)中的最小值的索引
! g7 G+ q' r: r$ c+ n, l            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
" ~3 f' c" d3 Z, D% e                 if (arr[j].compareTo(arr[minIndex]) < 0){
# \* m* }3 i* B9 V7 i                     minIndex = j;
) T( j# n5 e1 W/ ^% P3 p. j# K                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
" P$ ^9 y  F; C$ V6 `" W        }
    }
4 w3 b. A, `4 D1 |8 |2 L
    private static <E> void swap(E[] arr, int i, int j) {
2 i# E. H3 E; G6 t8 Z        E t = arr;
) a( K) H& ^" e/ I1 N        arr = arr[j];
* r! l5 ^) n) i9 \, o2 _        arr[j] = t;
    }

, m: r6 H; o+ t4 b8 X! g# G8 q    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
% i- X& u$ A) S7 o        SelectionSort.sort(arr);
        for (int item:arr){
% U: m% `+ j! S: J& D) ]& W* t5 O            System.out.print(item+" ");
        }
4 H& a' X8 n- W1 Y    }
}
  p0 Q& ~+ H/ Z
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
' |7 W. `$ w6 m: s3 i2 V4 ~
使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

import java.util.Objects;
7 D4 V  p8 s$ B' k/ }
public class Student implements Comparable<Student>{
    private String name;
; y! H+ a" e/ |) s2 x    private int score;
( A, f' N! x$ L3 u! N3 w* F+ \
% ~/ e1 N: c, r$ V# S8 }/ n% S' Z
) }% T: g) P  U/ J6 q) P; s" ~/ z    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
0 M5 T( f+ j' f) ]/ H) D9 R! ~% I$ y
! D+ l/ m# Q' J) y# h    @Override
    public int compareTo(Student another) {
        /*
( y; a) d+ a# H! ]- U# r/ G( {        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
" N$ y$ u& I) {/ O6 Z/ Z9 t        if (this.score<another.score)
            return -1;
        else if (this.score>another.score)
' N$ _* F! ?; B9 }1 N) f4 Y2 c            return 1;
        return 0;
        //return this.score - another.score
% W1 q) p) p0 {: I    }
8 h) U6 g8 Z( ?0 D
    @Override
5 E% E% m1 l& a8 u2 O    public boolean equals(Object student) {
        /*
9 I( l( _$ p) D2 g- Z' O) B2 s/ \8 a        强制转换有可能出现异常，因此需要做出判断
. R6 v1 O6 i9 m7 F. I2 F9 l4 c        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
' H5 `1 d: V/ f( b/ W            return true;
! K2 o! O8 I9 E) Y" x3 k- K$ U7 {5 k
        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;

; g' M8 O, Y5 h% N        /*
4 o; ~9 X/ ^7 f3 M9 L" ]! }        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
/ u+ c$ R9 k% |/ V        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
- r9 H- o8 W+ l' \         */
1 _7 C5 l% x5 g* S( d7 G8 J        if (this.getClass() != student.getClass())
; j. t$ k+ g5 h            return false;
7 @7 _7 s: e( u$ I5 |  j
        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }

    @Override
4 X# U! h0 j4 [  ?! H6 Z- Y* F    public String toString() {
        return "Student{" +
, M, A1 }, |! F* i; a                "name='" + name + '\'' +
                ", score=" + score +
$ Z; n' O3 O2 q, n- K                '}';
    }
" F/ O& r7 [! ]- H' F9 r}
2 a7 T0 ]. j% F) E9 l
, |5 `" F4 s6 V+ z主方法实现类：
5 B6 s' i6 m1 ]- U) P9 P
3 q4 J/ X& g; p3 s# fpublic class SelectionSort {

    public SelectionSort() {
    }

( m4 Y1 D2 T3 P" c# w% o% h    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
3 i+ q! b5 a: x8 \+ ^0 o            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
8 g; O3 B" d% L                //在剩余的元素中找到最小的（比较查找）
% G) y! ~' d# k. A7 c9 C) q                 if (arr[j].compareTo(arr[minIndex]) < 0){
1 L2 r# L4 B' g' v0 B1 g  p                     minIndex = j;
                 }
            }
/ E3 g& D% {8 W. k3 k3 T            //将arr与arr[minIndex]交换位置
( g$ N- y0 N3 K2 o) i            swap(arr,i,minIndex);
! y3 _1 |0 c5 g) R1 e        }
) @" T: \# Q- S1 W5 F: s' }    }
: h* V4 f( J& _$ \3 f+ R5 B
$ s6 v3 s. m5 f/ V% W    private static <E> void swap(E[] arr, int i, int j) {
8 S1 K; V, v, B" N; N" Z        E t = arr;
        arr = arr[j];
        arr[j] = t;
$ L0 _3 ]& B8 r' f" D* ?  H    }
6 ~7 v  v  P9 `7 O, {0 S% Q
! v# e5 q, V" H  c. Z" S    public static void main(String[] args) {
9 f$ ~. w6 i1 `4 O+ M* d- q" b        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
& ^( n3 k' }! j* I) C' r        for (int item:arr){
, z& p/ P  N3 ^; A6 z            System.out.print(item+" ");
$ J" o, i1 G/ J: f' [7 q        }
        System.out.println();

        Student[] students = {new Student("Alice",98),
4 Q5 J3 v% w0 F                              new Student("Bobo",100),
                              new Student("xiaoming",66)};

; t2 ?- V' P5 @- K        SelectionSort.sort(students);
        for (Student student:students){
+ A/ i2 L5 B' C- U            System.out.println(student+" ");
        }
8 m/ P) z( r+ ~4 f  d& C
    }
}
, E& \( B) \* j7 {5 Z( u; b/ C1 n
( X5 h- d$ Z0 {# K4 g3 w复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
6 f2 {( N, k+ A. [


首先在ArrayGenerator类当中生成随机数组
+ s7 H: h, v6 q+ |) u' E
8 }+ t  c  ]" P0 R3 H6 |    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
    public static Integer[] generateRandomArray(int n,int bound){
- F! X+ a3 i3 h        Integer[] arr = new Integer[n];
: c  ?4 `* Q: p( U3 O3 l, E1 T1 q6 l        Random rnd = new Random( );
' p. u9 f. O* z0 K+ ?3 ]        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
; q7 W4 e7 g+ z1 O& q) j        return arr;
5 v% G2 L2 s8 l0 w. F2 M    }
判断这么大数组是否真的排序成功：
; b: u" b- v% P4 u% z' k
public class SortingHelper {
    public SortingHelper() {
& f5 b: J/ c# K1 j    }

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
& d  K2 z: M2 [: C9 _0 h        //判断数组前一个元素是否小于后一个元素
! s, U$ n3 {6 I, B        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
+ Y# |) U/ O& e                return false;
        }
        return true;
    }
1 i8 i% i' L. O, j% s9 h7 \9 G/ O# m}
/ L  U- T8 B( r3 O9 N$ s/ P在SortingHelper封装一个test方法用来测试任意一个排序方法：
  b1 \" m2 i( Q5 v! r
2 R& M, g4 y9 r' \* y    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
, c9 O6 N" r' C4 u            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
$ O* A- `( t9 r' t3 w1 Q. g                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
# B' \9 K+ T' @1 r0 s                throw new RuntimeException(sortname + "failed");
* H/ C$ J" o$ g) [( D            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
测试时间：

public class SelectionSort {

    public SelectionSort() {
8 E$ e% E  ~. r' t8 N' ^# q    }

5 B/ v# {# C7 q3 |2 f1 N% N9 |! B    //
    public static <E extends Comparable<E>> void sort(E[] arr){
8 T$ i( A- j, Y8 D/ ^        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
6 |) I# a/ n' y' u8 i8 `3 ~( v) R            int minIndex = i;
$ p  F" o# ?# c5 L            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
& V" }1 A  d9 x  z, [$ Y$ J                 }
            }
  n9 y5 B9 p* x0 Z0 B# U: {: g& f) I            //将arr与arr[minIndex]交换位置
' e) ~5 w  D1 Q. O! n* ~: l            swap(arr,i,minIndex);
0 w+ B# e6 k" k, e7 f: k. |% n        }
    }
3 t8 E7 {( [/ w, Y
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
0 h7 [- D* A. ~6 }. _3 q        arr = arr[j];
; T. J0 H  s- F        arr[j] = t;
    }
: a  o" ?! t  M7 c# b8 v
6 r$ R6 R2 k7 b) E$ S9 J" y: d    public static void main(String[] args) {
        int n = 10000;
- V/ e) C: Q+ A' o2 Z+ i* \. j        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);
2 B1 Z; I! I1 Z- D2 @
' g0 X" m! }# n8 z0 a    }
}
5 P' z# o7 X1 r4 H5 ]9 ^
其中如果要测试两组数组：

* t/ {: l( J" A5 |. n3 P& O    public static void main(String[] args) {
. P- m' ~& H( D0 i' B0 G# k6 v        int[] dataSize = {10000,100000};
        for (int n:dataSize){
; Q, O# ]# t0 R. I$ u, f  G' C& o            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
2 C8 j* p3 m- B3 P            SortingHelper.sortTest("SelectionSort", arr);
        }
    }

. V+ V, ?8 I* a
+ i# W0 W, W2 {( D: k 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
! u0 k5 ]% N& z' _————————————————
+ H' Q( g/ i3 E- t; `版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. D+ J* f4 _# b1 E; R! D# g, K* E9 t原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
$ y  o) {3 c. r* }% l" g/ V
3 P$ ?  m3 b8 [; J
. c0 D" w6 Z8 u: `7 a

1051373629

感谢楼主的资料
9 j4 J$ N' c0 ]