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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
; X! B, |1 [) w! t  M- w目录

选择排序
/ K2 d3 m% S9 y, [# D! n& j% W, s6 n
+ I; @7 k; w7 s% |! ?4 C% x0 k选择排序简单介绍
, y' Q& e, D  m8 Q% h! a
实现选择排序法

使用带约束的泛型
1 P" E9 m2 T* Z  H
% Q+ q: R, J$ d使用 Comparable 接口

2 ?# {! @) ]8 ~1 p' E复杂度分析
" S2 ^$ F0 m, u( k, x0 V
选择排序
2 _7 O' Y) I; \" T0 t9 X选择排序简单介绍
/ x0 M4 g3 }  D: g先把最小的拿出来
& Q# H1 J4 x4 ]$ Y5 l$ b, y9 [
6 X+ J6 Q2 b# ]6 l& M% E2 M8 f! b剩下的，再把最小的拿出来

- S+ [, X, ~4 ~* Z- B7 q1 v7 S剩下的，再把最小的拿出来

- m& n& y5 C$ ~! T# l: {9 g......
# I7 `. q. Y, A% ~. k! D
每次选择还没处理的元素里最小的元素
6 C6 H, W% }; f
        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
; a1 D9 D2 I9 o' F" N2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
( k4 |' @* I% F$ @" X  W- d/ }3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
: U7 O5 E+ t# z) [2 G
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
4 L% r! z5 n7 b6 e7 w* z% Q
public class SelectionSort {
9 X- z2 Y& w+ u) r! q
* r3 N# n! p0 S7 R' J' B, k    public SelectionSort() {
. h, I% z% U* z' O! s' G    }

4 P" G7 b. I7 u4 I" w0 N    public static void sort(int[] arr){
, W4 E; ?$ D3 ]! ]( C3 o        //arr[0...i)是有序的; arr[i...n) 是无序的s
6 W$ [0 n. m" ~* v+ E8 Q- s& e) y        for (int i = 0; i < arr.length; i++) {
% O" H. q9 {2 K7 H. ^0 ], Y            //选择arr[i...n)中的最小值的索引
8 U2 |& s" C! q# F/ I+ Y$ M            int minIndex = i;
; S2 u- {' v# L9 n            for (int j = i;j < arr.length;j++){
9 m" e; R* P5 ^4 e                //在剩余的元素中找到最小的（比较查找）
, s/ w6 `0 |$ Z* i; c8 N. Z, A                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
                 }
4 T5 a: z4 L( D, b            }
; j6 ?2 e* n3 E# c            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
+ R8 t- \1 _( N% Y    }

) d+ p6 _" H! K' h    private static void swap(int[] arr, int i, int j) {
! ~: L) N7 ]/ f4 K3 N        int t = arr;
# U; x7 @2 f/ T# C, |. I$ I        arr = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
9 c8 K% S. m7 q' q- i: P" b' r        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
+ C5 Y0 i4 [- X' W, t) @4 p        for (int item:arr){
' \( r' ?6 A2 R. _9 {) w            System.out.print(item+" ");
        }
6 [4 h% P) _0 \, ?8 c0 D% Z" Q    }
}
  x3 c  P( \/ D- Z2 S' A. P
当前只能实现int类型的数组进行排序，因此需要使用到泛型。
; l( G, G( q- e& L
5 y1 x5 [) F2 c( B0 U! g使用带约束的泛型
$ B" K7 ]) s6 Z+ K% y/ d        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
1 _+ y/ d: Q) q9 `0 A, g$ Q- z
9 D9 f5 F6 A2 a) }) E& l0 K- u' [public static <E> void sort(E[] arr)
  K6 X+ ?; G9 }        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

public class SelectionSort {
; i6 M) d( h, o2 n3 X. E' b8 o
    public SelectionSort() {
) v" Q. ?& o* l6 h1 z" c    }

, ~3 o( t3 |- a, }; ?9 D    //
9 n2 [% {) K. D  N1 `( |3 r8 Z    public static <E extends Comparable<E>> void sort(E[] arr){
  \0 O# F5 b7 y) _& o! Z4 b, h        //arr[0...i)是有序的; arr[i...n) 是无序的s
- {8 f3 j0 a+ b        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
0 l3 [) n( D; p) a) M9 ]                 }
; ^8 k4 n1 u" E+ j/ V% f$ m            }
            //将arr与arr[minIndex]交换位置
4 @1 V% G# X, W( M; C            swap(arr,i,minIndex);
        }
/ o8 x4 x3 B4 p* K; s    }
6 w" H5 P8 r! G9 `( g5 l
8 J3 v1 E0 W) [" t" K! O0 J$ E    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
- o( W" C/ E, Q        arr[j] = t;
3 ^, l% S0 h7 i5 p% J    }
7 V, V6 O- f& j1 E  K3 P: j  J
    public static void main(String[] args) {
6 h! g1 j7 W4 X3 a" T        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
        }
    }
}
: T7 |: s0 P2 O0 d1 Z
8 {8 k7 [8 @2 E# }4 h: _7 S        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

* L  u& D) y& g4 Qimport java.util.Objects;
" r# w* {/ h% j4 d  B% |; w' A
$ B' T; F: |' w: {) O' {% Opublic class Student implements Comparable<Student>{
    private String name;
    private int score;
( T; H- |' D2 f2 T$ F7 |- N0 s

    public Student(String name, int score) {
# w  R  F0 O2 A: O3 z        this.name = name;
2 k8 A, [% N6 e$ R8 Q        this.score = score;
9 P7 [+ x/ a7 G3 {- `$ `% ?% ]    }
3 S6 k- s/ ]. `, ~6 l8 k; P. E
    @Override
) ]& ~+ S! }0 S% e% `    public int compareTo(Student another) {
" \" }2 K+ U! o2 w- {" |        /*
9 \9 ~" D- J7 t/ {9 J2 M        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
1 G3 b) t- u8 e# U        if (this.score<another.score)
' ~* E& h; R8 t6 b. }9 t            return -1;
4 r; f! h/ f/ O        else if (this.score>another.score)
            return 1;
# M4 Q- W  D: b3 Q6 P3 F; ~( ?) C; D        return 0;
        //return this.score - another.score
3 R$ x' ~6 l4 D$ j4 u9 R    }
+ \7 k/ K5 s& c# R( ]
    @Override
    public boolean equals(Object student) {
        /*
" |8 a5 r9 b/ B' M( B* {        强制转换有可能出现异常，因此需要做出判断
2 l8 _; [2 D5 P8 e4 @1 B2 t, l; S7 a        */
, c2 |+ \2 k4 v        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
; z& U) Z' w: ]6 U            return true;
. I: c$ U7 E9 X! j7 M) }, D8 T1 t
        if (student == null)//如果传入的对象为空的话，则直接为false即可
6 d% H, k2 F) @% e0 v            return false;
3 D; I) }, \' H, J" o- B
        /*
        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
+ E- A! x; t9 [* J6 E        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
+ c) y; \0 \2 C/ o6 B        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
        if (this.getClass() != student.getClass())
5 J# y7 S8 {8 J( e            return false;
& }# [* y) P6 ~0 A" g$ t
        Student another = (Student) student;
! i5 F5 s/ X2 J1 V! \3 D8 N        return this.name.equals(another.name);//写比较逻辑
    }

1 H9 t+ J/ x1 a# ]/ Y    @Override
    public String toString() {
        return "Student{" +
- \: ^" }  o& s! N: \1 B                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }
! G5 f! W/ G' x1 q}

主方法实现类：
5 E9 }. M& O6 o4 h; ~% R
, X8 P) W1 P, Z% y  N& {public class SelectionSort {

    public SelectionSort() {
; h0 L: L; z6 }& a5 q, B    }
# n1 y) p3 c" D* _6 v  E
3 T( k2 A' g# {4 i; N* J    //
4 `4 S$ ?+ c& N4 N  M2 z: O5 }    public static <E extends Comparable<E>> void sort(E[] arr){
- D+ _/ K8 @. S6 z' C4 B        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
. m3 S9 Z. d( s0 X" m! |+ K: H                     minIndex = j;
# e1 c, i+ F# Q                 }
            }
8 o3 {9 s5 K- q. i; ~            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
) C$ a. h, b4 i7 N2 B7 A        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
2 W$ [8 ^: Z- |0 s: g: Y& {        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }
# n4 t' o3 i% ^7 s5 I
- T0 \/ R% K6 u, [* |4 l    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
; V! E( F* h) x! T: Y        for (int item:arr){
            System.out.print(item+" ");
        }
! [+ X, R, \, S$ O; }        System.out.println();

        Student[] students = {new Student("Alice",98),
/ M2 X: o4 g. l                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
% ]0 y! d* k. A; Y
        SelectionSort.sort(students);
        for (Student student:students){
3 b" |1 g# X  |( q% T            System.out.println(student+" ");
0 k; E$ m" m, v5 ^7 x* ^  Q$ D        }

3 e0 ?$ b# u; z% [1 E6 U: D- R    }
}

复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。



" Q) K7 U0 A% a5 E) m* `4 q. X, m首先在ArrayGenerator类当中生成随机数组
2 b5 K- E7 f9 M) \" m8 T# ^
7 c/ N( E. v; P4 ]# |4 Z- K    /*
5 N* m& C* r9 @/ z1 {    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
1 K: V3 n9 Z3 m3 Q5 l/ `     */
, d1 w, R) ?" P7 ~3 \    public static Integer[] generateRandomArray(int n,int bound){
9 Y/ I6 F* T/ u) P' P' F2 C        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
$ Q4 }9 B2 g& V- m! a        for(int i = 0; i< n;i++)
3 q4 X+ ~1 J% S% s' p, f7 ?5 p6 W            arr = rnd.nextInt(bound);
4 ~  b2 g% c# \% [' U8 v3 N- i        return arr;
    }
判断这么大数组是否真的排序成功：
) ?) b9 @. G4 V6 D: w2 r
8 N0 W3 w' A  q: k; R' M1 K* Npublic class SortingHelper {
    public SortingHelper() {
+ ]8 C8 A6 O8 A. l2 r    }
0 D' }8 \5 u3 V% }4 _
1 f" h+ f/ T4 l( t0 `# p' ?    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
$ P' v) B8 f0 L. E: U# I* x                return false;
        }
, S1 X5 w; Y8 L: c# Y( f% q1 n        return true;
    }
}
在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
1 I% {/ N) X+ J7 l    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
, D1 p3 @6 X( ?5 L! m            if(sortname.equals("SelectionSort"))
1 F) Y8 F4 _$ {; y- f  u                SelectionSort.sort(arr);
( j  Y) U4 z: e# g0 G1 I: w            long endTime = System.nanoTime();
( t/ o) k8 n. P            double time = (endTime - startTime) / 1000000000.0;
- h$ l5 M$ `  D            if(!SortingHelper.isSorted(arr))
; Q# S' E$ q/ B3 v. j0 z                throw new RuntimeException(sortname + "failed");
6 h  q6 }8 _* f' X" M$ k            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
  F+ t( H0 H6 B* |9 v- x% o' B    }
* L( L: X' J$ m5 |' \. v4 t% G测试时间：
/ C& |  ~% |5 ~4 s8 G7 `
public class SelectionSort {
) Y1 p& H4 e( t8 |1 k$ B
( X, `8 R# u# R    public SelectionSort() {
    }
4 B+ q1 \8 E  |4 r' \" {
0 M+ b) D4 q( p  e    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
* @9 ~$ N9 ]- T4 O        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
; o( c7 \1 _+ l            int minIndex = i;
2 S! w% w9 t- z            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
1 J( t; i4 h8 E* H0 `% B, x) W                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
3 {& o8 c: B! p& Z                 }
& j6 P" v+ R4 Z) r; O8 Q. T8 v; ^            }
! E. R! t2 J( S            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }

$ S# J2 D! O$ h& A    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
1 T+ ]5 l* f3 _  B        arr = arr[j];
3 L6 }* s. `1 `: C/ y9 Q+ r, E. I        arr[j] = t;
    }
2 D2 {: L1 d' B  P( P3 N4 _
( W$ ^( [; h- A/ k- l    public static void main(String[] args) {
# o! t6 F; ?: F$ T        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
  `, ?4 x3 q3 v9 a& ^1 Q( K0 ?        SortingHelper.sortTest("SelectionSort", arr);
$ `  R( Y, z2 ^! h
    }
5 t: f( m+ ?4 x. C/ l% w2 }}
0 d: v* \. H; S
! Y7 h# a6 H4 y1 w其中如果要测试两组数组：

    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
* N8 |0 V7 \; @, N. k6 A5 a: [            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
; N& t: Y' E. z% A; w7 p. @$ d        }
/ e, b9 ]2 t/ |3 R3 n4 p6 r" \    }
4 a' R4 \  A) l
. H9 E* n+ j: X1 P- j
9 O" _; P4 m/ ]: o* T/ t 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
0 S) U2 y2 I! I' o' t* J( h9 v原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

# F" v$ I9 T: N) f7 p6 M% m8 ~
4 W3 x! c  z/ h) x

1051373629

感谢楼主的资料