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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
- |4 _+ V' P6 d7 B/ k" Y$ R' `
选择排序
. x2 E2 p8 F3 ~3 d  Y% `8 U
1 x$ R# m  D  _选择排序简单介绍
( G3 e$ b0 @$ W3 S: x- U
& @: ?% W  i. A5 [/ `7 C实现选择排序法

使用带约束的泛型
! D! r5 h6 I5 |5 g5 h
使用 Comparable 接口
3 |  t3 c: ]# c3 O
复杂度分析

" r" D# a! E1 U2 N& u; Q' o. {3 c  P选择排序
选择排序简单介绍
先把最小的拿出来

) {  k( e) _9 @: [/ Y; l, Y2 w$ u剩下的，再把最小的拿出来
6 e2 u3 J/ Z% h: X; g& l: y: P' ^
3 [0 U  G5 _' |* k4 T剩下的，再把最小的拿出来

......
; B. E0 k1 c4 O* L9 g8 W
) @! V; m% m- t每次选择还没处理的元素里最小的元素
* \! ^; _9 u/ d- Z5 `1 L+ j
7 G5 }: g$ d# n7 i/ A, d4 \$ V3 E        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
5 L% H( c' `- P& B8 j
        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

9 D' C  s1 k% V5 f实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
+ j3 v' B8 b; |" u7 O3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
' b% J. {( d0 K- B$ K  w6 Q. k8 A
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
" c5 {2 X$ j8 b: b4 {! a
public class SelectionSort {
" k4 N0 h2 ^  t2 B- }% _) M
    public SelectionSort() {
/ o- C/ p) q! ]# J+ O    }

    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
1 f! t6 I% [% Q. u        for (int i = 0; i < arr.length; i++) {
9 j) t" F' o/ }/ b% D            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
5 E7 m0 e/ j$ l% \$ W; H0 G* ]            for (int j = i;j < arr.length;j++){
$ p; S6 N7 J+ w  ~3 m' N# }                //在剩余的元素中找到最小的（比较查找）
% Z  }) i, b" u! W: ?                 if (arr[j]<arr[minIndex]){
* _2 X- o* @* u$ ^( {8 W& h+ Y                     minIndex = j;
0 W7 K4 @$ t( I                 }
+ B6 \! `$ Q& k            }
4 V" {6 v, g2 ]+ k2 n            //将arr与arr[minIndex]交换位置
* B8 J! d3 H" r( C0 h# v            swap(arr,i,minIndex);
        }
" y: |% D$ Q7 Y- K    }
$ k& ]' g( m! g2 h* B
" G$ U7 i; M7 H1 \5 z2 f5 ~    private static void swap(int[] arr, int i, int j) {
        int t = arr;
        arr = arr[j];
1 y( e! J# Z9 F7 R  j' K* P% D        arr[j] = t;
    }
: e3 c# P8 D* w2 X
( M6 l/ H7 b6 `9 o/ S/ m4 D! `/ w8 f    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
$ `5 R, R! x% a( [, D! Y5 v        SelectionSort.sort(arr);
        for (int item:arr){
6 N9 C6 l+ B# P0 O+ T  s2 L2 k3 h5 k            System.out.print(item+" ");
        }
* @$ u6 p$ R" S1 h* Z0 |* B; n    }
}
6 P* U4 \$ B2 N5 l" ~, O8 C7 B9 B
当前只能实现int类型的数组进行排序，因此需要使用到泛型。
% c' K5 Q# I0 D+ }; r
使用带约束的泛型
( ~" d; v' g, O: Y5 x; h        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
/ t# Y4 |% S" r
- Q- F6 s( s% b/ y* Ppublic static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

* B' s; J8 O% f/ J! Y) x4 t1 {! ]public class SelectionSort {

& U" J6 _0 A" B1 v2 Y    public SelectionSort() {
    }

    //
; g$ ~9 T' y2 t" ]* M    public static <E extends Comparable<E>> void sort(E[] arr){
  u8 J1 h$ r$ T+ f$ J9 U* T        //arr[0...i)是有序的; arr[i...n) 是无序的s
$ {1 x7 Z* j2 g6 W& F        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
+ c. P0 c6 a; e1 |! g            int minIndex = i;
, @; J' h- @& J6 A0 S            for (int j = i;j < arr.length;j++){
' a! a8 ~# S5 r1 [! i8 @                //在剩余的元素中找到最小的（比较查找）
  m( t5 m; o4 |$ u. f                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
  z# q; h0 [. P0 J: [, |9 Y                 }
            }
, M( c5 \3 `1 u6 l            //将arr与arr[minIndex]交换位置
4 Z- L- Q9 h" K; s0 @) l; d7 T            swap(arr,i,minIndex);
        }
' H' n) h0 [  h2 o, q! {5 e$ U    }

' G* W, e2 E) Y0 u: \0 ^    private static <E> void swap(E[] arr, int i, int j) {
0 Z3 {; u! z8 U7 ~& N        E t = arr;
3 G3 w: K8 S" E$ d& m4 @3 j        arr = arr[j];
* V5 v# T/ c& _! Y# Y7 w$ j+ S        arr[j] = t;
    }
9 S1 v3 w4 M) W! l) D
    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
7 u4 ^2 F2 ~% U2 u        SelectionSort.sort(arr);
        for (int item:arr){
6 ?$ N: l3 a; h  {) J+ O* J; k            System.out.print(item+" ");
        }
: k( |3 L7 X+ a7 q3 Z" R! n0 n; Q    }
}

4 H! k4 d' ]  w0 J5 s) z$ t3 l2 M        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

使用 Comparable 接口
0 P6 g1 w) u' O% R  F: s& \        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
2 H: Z7 D$ G4 |/ w
. n( |' W2 P1 j) simport java.util.Objects;

public class Student implements Comparable<Student>{
    private String name;
    private int score;
# X' B6 L# k, e. F( ]+ ]+ Q% z
- u9 o0 z$ I$ w8 ?8 M
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
: ~8 ~8 Y+ y. u  Z; ^2 q! F, J  B    }
% h1 ]# H# ]( R' P6 i$ F% z$ v
    @Override
    public int compareTo(Student another) {
  w$ {( l4 j0 l" r" S        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
        if (this.score<another.score)
5 z0 W* }8 U6 y' m6 \1 J            return -1;
        else if (this.score>another.score)
            return 1;
        return 0;
        //return this.score - another.score
- H3 s5 ?& C# F+ t* L    }

" B0 D1 O' @7 `1 C+ T    @Override
    public boolean equals(Object student) {
+ @! y+ D( C/ `" Q. B) A' b        /*
7 I* S/ G) n5 e/ {8 L/ e0 k. i  G3 N4 S        强制转换有可能出现异常，因此需要做出判断
        */
7 l% v) v! M6 i) M9 N4 s        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;
* P2 O9 d' b  y! M5 i+ ~; G
        if (student == null)//如果传入的对象为空的话，则直接为false即可
: V! ~1 ^3 I4 D9 G+ _8 }5 ]            return false;
% X6 X  B% u  ]0 r* Z; K
        /*
1 U- p* I9 G0 ?) S* ~4 x. J# j9 z        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
7 O: K5 j  U/ j5 n8 [  j         */
' K4 m$ a) k; p+ ^; a        if (this.getClass() != student.getClass())
            return false;
/ e& g5 L: B* s0 u
        Student another = (Student) student;
/ d3 t$ Z, U" d3 S  M        return this.name.equals(another.name);//写比较逻辑
1 r. \( p2 @6 O) Q! ~* E    }
9 H0 C; L- ^4 ~! R; |3 z
    @Override
    public String toString() {
        return "Student{" +
9 \. r; o3 ]/ p& G                "name='" + name + '\'' +
                ", score=" + score +
                '}';
$ U6 Y; i3 d' x1 U5 \: C    }
}

主方法实现类：

public class SelectionSort {

$ Y" [4 A9 K" A/ p( Y. d7 X    public SelectionSort() {
    }
3 _4 C  @0 S2 v: d
    //
    public static <E extends Comparable<E>> void sort(E[] arr){
, s- _5 g& n# Y. j! s) B8 f( N        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
+ ^2 M1 T2 u2 _: W! G& {6 ?8 x            //选择arr[i...n)中的最小值的索引
7 n* j  ~: ~5 `2 B1 l% A            int minIndex = i;
4 e/ x# q& T, ]$ ?+ o0 r            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
: @/ t# ]& S1 @) [& F! c4 y                 if (arr[j].compareTo(arr[minIndex]) < 0){
8 P* j0 \6 L- j' m6 M  ^9 C+ {                     minIndex = j;
                 }
& Y) s3 O; d% s. e! G            }
* C0 O4 v. ]7 L9 E) D- S0 i            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }

& ]: X' W' h$ ]2 b( L    private static <E> void swap(E[] arr, int i, int j) {
' Y% w6 ]$ q7 T1 \% Y9 y4 D        E t = arr;
0 ]% v8 D$ c) N, ~) R4 t        arr = arr[j];
% i  m5 A& d" C3 [# `        arr[j] = t;
    }

    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
        }
  }8 W2 Z$ o7 P( P        System.out.println();

+ _9 W9 N# ]# Y, g8 R, `        Student[] students = {new Student("Alice",98),
5 g' ?+ ?; T* \, X. f9 L& d! f                              new Student("Bobo",100),
7 t5 s9 ]7 }1 ?& J% `                              new Student("xiaoming",66)};

2 B3 n' Y* P* X* R# P        SelectionSort.sort(students);
        for (Student student:students){
            System.out.println(student+" ");
        }
2 O* Y' @" Q' t9 L6 j
" ]$ @2 k- d% O. O    }
}
  t- }& m- G  k( i- n$ X0 ^
- l; \9 E+ K! u复杂度分析
9 ?1 k% \3 m8 k/ Z( N        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。


$ X( a; |) K2 h1 \0 L
* l, M5 y& p0 c/ `8 v6 ]7 b3 C首先在ArrayGenerator类当中生成随机数组
- k- G# M' M, e& o9 w, I* U
    /*
7 Z) s( b) u  N6 w: G' S$ V, b3 [    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
, Q5 R, |; d/ R" G( `# n6 n) l; J     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
, r3 X6 P6 L; Y, T+ ]/ ?# a5 A        Random rnd = new Random( );
4 {. p* {- f3 ]8 d6 Z2 _+ l, T        for(int i = 0; i< n;i++)
( j: T7 S$ |" J3 t6 V' v            arr = rnd.nextInt(bound);
        return arr;
/ V- o( E! _/ N1 z% x( @2 S    }
判断这么大数组是否真的排序成功：

9 e1 Q/ K# j/ `4 C6 G" a3 S( }. {public class SortingHelper {
( }8 T  `9 M" O+ g' p    public SortingHelper() {
- s- s; R. ?2 R    }

1 m0 \/ V5 a  z) d    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
( |2 F" A  h3 R/ K4 n        //判断数组前一个元素是否小于后一个元素
8 R0 H4 H6 ?: c) G3 T2 o! l0 E: |        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
" R7 H& [& k& y4 n8 O                return false;
/ t. w3 S5 L, r$ h" v8 S        }
        return true;
) i! Z: k" a1 w/ m    }
}
( I" T2 S: B" R4 ~2 x, ^+ S" H) R在SortingHelper封装一个test方法用来测试任意一个排序方法：

2 l% R3 n' X1 f# X! n    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
2 M8 Q4 \, n) d0 p& `5 L$ j0 ~7 Q# h5 P            long startTime = System.nanoTime();
/ [2 q* H. B6 Z5 y            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
0 r5 `6 X; v* d& e# s* E" A            long endTime = System.nanoTime();
3 t4 Z9 R: e7 E. X7 L            double time = (endTime - startTime) / 1000000000.0;
- }7 h5 c3 w0 R+ W            if(!SortingHelper.isSorted(arr))
' K$ }* ?: p! }                throw new RuntimeException(sortname + "failed");
: m: y% h  t; F8 t& h0 ~, z5 i0 B3 p            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
! q; g' E3 P; E7 x2 a测试时间：

6 _7 U& x6 ?0 m5 M9 b( qpublic class SelectionSort {
! Q3 g8 O  P) y  U. Z' F
" @  r  U& c, @/ Q! U  j( a* H& }    public SelectionSort() {
3 n/ b5 E* O. o( P* b* U    }
" M; w5 ]- u4 r1 w! O& {; _+ }" b3 O
# P5 l, C+ t4 @$ I/ D    //
4 K/ n6 L  D# K6 c    public static <E extends Comparable<E>> void sort(E[] arr){
5 w) V, V( F. }9 ~2 r$ _6 N        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
- v% `! @$ D1 ~$ D            int minIndex = i;
0 \! e! l& m, W            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
% G) K( q( g  H' f            }
+ g3 b8 r" d' D5 @- b# o9 J            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
( ]9 d' A, ?# w    }

* G% [- @7 Z0 x" z8 B    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
! F' d  I. v6 L        arr = arr[j];
2 t; G9 \& `$ O+ |% ^6 Q! x7 b/ a* U        arr[j] = t;
6 L4 ]2 w3 m" Q* V0 Z3 Y6 q    }
# l2 E9 K! w6 w) q) C8 N
# }3 M' M" {2 p& u" S    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
& u( @6 m' A- e        SortingHelper.sortTest("SelectionSort", arr);
3 f0 y) R% I% L+ H8 m
* H0 T1 P' f$ D9 y, u5 S. J% d    }
}

) T9 w8 ]5 U% j3 Y9 i. p其中如果要测试两组数组：
7 B* M  {9 g% u/ i! I  G0 e
    public static void main(String[] args) {
& N+ q5 c: d7 J8 `        int[] dataSize = {10000,100000};
8 T" n  P% W1 Y! `% t        for (int n:dataSize){
$ Z1 {3 u' x! P            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
        }
* y9 O. @# ?! w& p. D    }
! m+ B! N* M. Y# a

可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
1 c0 B4 P3 s. [& X2 Q$ r' _$ ~版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 t4 z0 G3 a( V原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
8 ^. t# p3 Y+ Y
" s5 I' P3 H4 O1 x
9 }5 C5 I( E1 O; ^* b/ K1 i

1051373629

感谢楼主的资料