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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
$ g1 Q/ ~/ }1 ]- a目录

选择排序

选择排序简单介绍
9 ]' M" N" q! ^4 B" F
实现选择排序法
* _+ d2 ^9 S. R7 ?1 _4 ~
" [, u' v. Q0 o! s使用带约束的泛型
% }; |: F" o- L+ z/ c$ c9 U# k
使用 Comparable 接口
9 _2 F) `# L# j& h
复杂度分析

选择排序
  S9 }) F$ S: Z% L2 e* _# ^选择排序简单介绍
先把最小的拿出来

. y% ~% k* h7 W" Z9 Z* e. O剩下的，再把最小的拿出来
* f% G" G3 \$ w% v7 D4 X. U+ a
剩下的，再把最小的拿出来

6 q" t' [+ O6 y7 d......

5 i: M% c) V( ?" Z+ D每次选择还没处理的元素里最小的元素
+ Q( L4 S2 v4 S4 l; S: R$ l
        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
2 T0 w5 k, m7 o4 L' R  i
        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

) F& R; J2 k3 f: T; F) @7 o实现选择排序法
2 ?4 }# D6 K% d$ g- ~+ n4 P1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
" O& B9 e* H1 J% ~2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
& \+ r. ]: }) E- A6 e- S3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
& L( N8 p$ k/ Z+ v
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

public class SelectionSort {

3 }! N0 r8 M- ]- t0 [; T2 ~    public SelectionSort() {
9 Q0 H. ^1 V5 m* a2 U+ t+ g    }

    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
4 s* n1 S( p. T8 g$ Q! H. [  r& @            int minIndex = i;
            for (int j = i;j < arr.length;j++){
9 ~9 M) E3 O% q9 w( F+ {                //在剩余的元素中找到最小的（比较查找）
7 t2 I( L0 i8 U, M                 if (arr[j]<arr[minIndex]){
0 d" U8 {; ?! j7 w# V& |6 W5 g                     minIndex = j;
                 }
            }
5 q& y, D' ]2 b4 j: N4 q            //将arr与arr[minIndex]交换位置
% o! f* Q+ i% `4 d. C" D            swap(arr,i,minIndex);
6 }7 r6 N7 l! E        }
    }
: k' _6 N, O6 _0 g4 |. j, ]2 f
    private static void swap(int[] arr, int i, int j) {
        int t = arr;
4 n* K' [/ P6 k# ]+ Q        arr = arr[j];
        arr[j] = t;
    }

/ w. v7 e. ~$ B& E8 |6 S( _( N    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
# x: k$ {1 V! j7 o) A9 h        }
    }
}

0 Q4 ~% X; @; Z7 l) L  A当前只能实现int类型的数组进行排序，因此需要使用到泛型。
) X8 m7 S5 `( A+ O7 z+ n! J
使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
, b0 y/ N- {% F/ ?- x4 `
public static <E> void sort(E[] arr)
5 K+ \7 L  V9 ^- u        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

2 C& b  G; R, Y1 e+ t* q' F% apublic class SelectionSort {

$ r7 {' p$ O4 }4 }, x    public SelectionSort() {
    }
# W! H# T& v  X
    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
, p1 I% {' ?1 w- S$ \& d' u        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
$ Y+ M. W$ S, l            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
% c! \1 ?' g! O" y; T; D) v# |0 x5 Z/ x                 if (arr[j].compareTo(arr[minIndex]) < 0){
" I% D' t+ H6 t; c; j                     minIndex = j;
8 \& L! u1 b, N6 W1 c9 O/ ?9 \                 }
% F, w$ X$ }- x5 k: x3 P1 ~            }
            //将arr与arr[minIndex]交换位置
# M7 ~2 P4 H; E! w) t* \: |            swap(arr,i,minIndex);
! S* ^( y  q1 h% \  r# @7 {        }
- {8 V8 N/ l8 ~( d9 w    }

/ z, L! C. \8 {    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }
5 X# q8 t! F- P/ j+ `- G
+ _/ v$ n" b- H    public static void main(String[] args) {
! p  |3 z7 b' g2 ^6 {7 @        Integer[] arr = {1,4,2,3,6,5};
" N9 `/ C1 o# g3 l6 b% {0 j7 @0 q        SelectionSort.sort(arr);
        for (int item:arr){
- a7 y; x# U& i! D, L, e' S. |            System.out.print(item+" ");
$ W8 x$ g' v8 n) e        }
    }
}

2 }7 g6 C( F9 _. }% u- |# Q        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
% R. V( L  X2 S
使用 Comparable 接口
7 B. h7 \, B# N% j9 R& x+ Y" e; g        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

0 t( [$ `, j5 zimport java.util.Objects;

6 H3 n9 ?: L6 P  `public class Student implements Comparable<Student>{
    private String name;
/ {2 ?$ n& z2 N  Y0 R- K    private int score;
; y# z7 Z# }9 u5 M* ]
; B2 s8 K/ t, ~0 u* d2 ?$ l# n
( @. H; o  a2 H9 K- ]' Y    public Student(String name, int score) {
, M. g$ E& n' |0 f% n# R        this.name = name;
        this.score = score;
3 m3 @+ M; e- a/ {# X; S0 D    }
2 d% f6 A* c2 ~) o4 R. J
) a7 |" e: Q  J2 t    @Override
" k5 R4 L$ N- q" R    public int compareTo(Student another) {
1 `* U! L* [, a/ s9 ]        /*
% y; Y7 _. G: w+ g        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
/ r0 b% ?) z0 p$ ]# V8 m/ H         */
        if (this.score<another.score)
. u4 k, s3 p4 p& p0 G, B1 X) j$ F7 \            return -1;
. k. t6 D! Q2 x7 q# y1 P        else if (this.score>another.score)
            return 1;
, A* o% \# I. f% q' u% p. q        return 0;
/ u) L  [( w2 o9 j        //return this.score - another.score
    }

: |3 y5 t- a  g6 f    @Override
    public boolean equals(Object student) {
! P, U4 e. i. l        /*
2 U2 Q; c' K3 z! h1 K! v        强制转换有可能出现异常，因此需要做出判断
        */
  x" h' @, Z" Z& J; @7 n3 c5 v        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;

        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;
; Y; w, Y# }+ F& Z% Y+ T( g
        /*
5 X7 O2 J) q/ W* j7 P        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
6 b" o  o! T% W; _" e        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
        if (this.getClass() != student.getClass())
  |& M+ M3 h2 v4 c            return false;

        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }

    @Override
2 ~0 M& B' X8 g7 Q! r6 Y    public String toString() {
3 ]5 r: n% M# J: q3 V, z3 D        return "Student{" +
                "name='" + name + '\'' +
: _. I. j. c% C% T                ", score=" + score +
                '}';
- h0 b7 a2 _; T) V* s, S  J1 {! ]8 W    }
' R+ z, Z. H0 z& B8 u' y}

$ A4 G8 i) o! Q# r. h8 C0 |9 F主方法实现类：

2 a& G; o0 Q7 S( a" W2 y! V2 upublic class SelectionSort {
" r' C" w. E' o9 [4 V2 E
( L  d3 |2 u  t  o$ j' V8 x    public SelectionSort() {
    }

    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
0 v7 X- V. R' c1 V" x7 E9 I        for (int i = 0; i < arr.length; i++) {
! ]6 a! E  x3 R7 L1 t            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
0 L  t3 S; J7 T& `8 c2 F9 ]                //在剩余的元素中找到最小的（比较查找）
3 V# h+ I5 h5 Y" k4 x7 \3 ?2 z                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
/ [/ _2 Z7 o3 A" s% z                 }
            }
5 S5 B9 F9 }# |: w$ `            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
2 c) U' n0 ?1 j, `& m! Y9 s        }
7 k" n: Z5 O, z* r    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
% B7 c" U: h( d) I! e9 ^# m6 F        arr[j] = t;
1 O# ]! k* O* w# d" \% z$ X, S6 c8 n    }

    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
. a8 A! @8 b2 K$ ?+ \8 G        SelectionSort.sort(arr);
& U8 F/ `, x( c& G, J9 T, O        for (int item:arr){
            System.out.print(item+" ");
        }
        System.out.println();

! A- y/ n2 U) @3 Y        Student[] students = {new Student("Alice",98),
9 O4 Y% U; H) T) u6 V& r                              new Student("Bobo",100),
. v/ B3 }$ I: A2 i. N1 H                              new Student("xiaoming",66)};

        SelectionSort.sort(students);
$ @6 d" d9 f+ C% _7 S- f6 I        for (Student student:students){
+ j: n/ z. }: `            System.out.println(student+" ");
        }

; U% N) T2 t! ]% G' P* U' u9 g$ q* b    }
  _* K! u$ c- m+ \2 f# {1 {}
; k! ]: O8 Z' i! U
复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。

) V( r3 ]$ G2 d! \1 ]" f
! z, j3 P( U) `+ ~4 o, f
6 ~/ S& s* e8 }4 [首先在ArrayGenerator类当中生成随机数组

    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
' o7 Y4 A1 U! \& w$ m            arr = rnd.nextInt(bound);
1 |5 f/ R3 l! Q% `1 G( j$ {        return arr;
9 Z3 H% I! S4 W7 y' _7 q    }
判断这么大数组是否真的排序成功：
2 P* M9 H# P( `3 h
9 }# ], j) w! `8 \0 i6 J. ^public class SortingHelper {
- @4 L. [$ O: \3 R! E    public SortingHelper() {
    }
) M, O3 I+ {5 `: O6 k# A
+ ?4 ~! t8 s) N+ Z' s  f    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
! R! ^0 @* q+ P* V! N        for (int i = 1;i<arr.length;i++){
: {) r* e* f; g4 c/ C3 G+ C  f            if (arr[i-1].compareTo(arr)>0)
6 E0 D  A8 q' M4 c& y  k( q, |. u2 h                return false;
4 F1 J: b% d$ V& `* M* V        }
7 p  A/ `$ k% c        return true;
# H3 W1 E1 ~; l* d/ Y    }
}
! e' f+ \1 E1 z: A& `' L5 B在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
7 f: d! J) s$ z5 \            long startTime = System.nanoTime();
9 ?# x- G! k- n            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
  P4 ^+ {: V2 P6 {: Z; d% [* `' _$ \            if(!SortingHelper.isSorted(arr))
. ~6 K% K7 \7 ]                throw new RuntimeException(sortname + "failed");
* o- d8 u) w) H7 ~& J# A8 i0 q            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
, H$ a3 S1 o$ |* u测试时间：

' s# J, T7 j/ [  V  S' dpublic class SelectionSort {
4 \- \& ^/ q/ q) n8 R+ L
- h* Z6 j; K. R    public SelectionSort() {
    }

, W0 N1 ]- |# F0 j/ L, X% y    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
( ]0 @. F  d- X; f- G) b) l        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
8 l' x) m  i7 c2 w5 w            int minIndex = i;
            for (int j = i;j < arr.length;j++){
1 v( I0 Q& n* `# }& T6 D6 Z# Z# v                //在剩余的元素中找到最小的（比较查找）
  P* @' d6 r( R# t# j                 if (arr[j].compareTo(arr[minIndex]) < 0){
. b& r; s- U6 o6 W                     minIndex = j;
# Y# Z1 ~' D  F. B" T# c  q  Z6 l6 ~                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
) v# Q5 W# Q% L4 Z    }

! T, s% H. T+ S, V! S9 i  a    private static <E> void swap(E[] arr, int i, int j) {
4 }9 K+ V# |9 }3 o; m5 ?        E t = arr;
! R! H2 K/ q% S$ \/ L7 ^7 D, c        arr = arr[j];
        arr[j] = t;
3 X; F: A+ l; c6 [& G    }

* n$ W; a6 ^( ~5 A# r, q/ q    public static void main(String[] args) {
$ g. a4 H; z" A( R& h; O- {        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);
- A" g& _7 q2 z6 @5 q
    }
}

5 w; t( M% ]3 L; f( U% H其中如果要测试两组数组：
; O6 @) H+ ]" d- K' s# p
    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
% |4 w6 C3 F- I# r9 Q$ k. n. A$ L            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
8 h- i0 X6 u6 w6 ~8 O- H        }
    }
, E' V0 A, c/ p/ g/ D4 i. f

可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

! t# L6 z% ]* d) H2 W+ J7 z

1051373629

感谢楼主的资料