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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
6 B* g6 [7 N$ b" Z
& \1 V# |: S! J% B2 M选择排序

$ m& \6 y; u9 p. k1 l5 u4 q/ R/ \选择排序简单介绍

实现选择排序法
8 p/ I5 c3 I( O/ p
# H* @' Z$ d0 ^! v2 G+ F2 L6 F使用带约束的泛型

/ L' g7 C/ M& M7 Y+ }, A* G. [, n使用 Comparable 接口

3 _8 Z% C* o5 ^( g复杂度分析

+ _% ?" a& D  I选择排序
* b8 E; x. j( A选择排序简单介绍
先把最小的拿出来
5 r; u1 H3 K7 b
! \# f& g) B0 O/ A0 T$ X剩下的，再把最小的拿出来
( x- y' D5 _0 q0 C$ m
" \7 G. e) s+ R2 Q* O8 t! T剩下的，再把最小的拿出来
% f3 a( R" L+ v' ]9 b/ h7 s
......
# q6 p: r2 c' w) p8 L
) X1 N; r0 s' R每次选择还没处理的元素里最小的元素
9 ~) U0 G4 Q9 W3 f  [
        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
8 k1 l1 Z2 r/ a$ N" A
, \5 B" z( E, B- ?        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
1 U- [4 b- _* u. W8 B/ J7 _
. y. F% ^! P9 Y8 _& F实现选择排序法
  ?% Y8 d9 E! W0 e7 i& K1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

: m/ L( a3 N& q( o* ]        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
8 E. v& v' V4 d
public class SelectionSort {
- ^+ V- Y1 b2 L8 j
/ C5 F/ g0 ^$ d; |    public SelectionSort() {
    }

! g3 X2 p0 `" I  c/ x    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
% U; s( T1 F6 ^! _5 n        for (int i = 0; i < arr.length; i++) {
" j, V% \% ^# x  G            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
% t! A- Y, [, K$ d4 s# x, w            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
! v3 J* d' `' m" x1 j+ Z; E& x                 if (arr[j]<arr[minIndex]){
5 W7 Q6 ^) I" n' f+ _  K7 ^                     minIndex = j;
                 }
/ }' {: L0 e6 n& Y& z            }
1 I" R$ l+ d; x  T' F            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }

    private static void swap(int[] arr, int i, int j) {
: T8 p+ l4 _$ C3 h, ^; Z        int t = arr;
        arr = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
8 ^( o% ]3 p7 a& ~        SelectionSort.sort(arr);
+ N" k; D5 T+ E        for (int item:arr){
! k1 a6 x6 a! S  E& A/ j/ P1 b            System.out.print(item+" ");
        }
    }
}

当前只能实现int类型的数组进行排序，因此需要使用到泛型。
( i3 h2 T0 t' k# x6 r
" t. V% ^" d+ e( ]使用带约束的泛型
* I# U# @  T5 h+ p, x  _        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
1 A  y- X" e5 \1 T
/ }$ W( c- R  u* epublic static <E> void sort(E[] arr)
7 N/ H/ Z  @$ y' L* G* o        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
) E0 N/ q* ]( V2 u9 U
public class SelectionSort {
! s2 ^7 y2 \, Z4 O. e
    public SelectionSort() {
    }

    //
    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++) {
& J9 ~9 }5 e  a( [# s/ E8 O            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
# A# D" J/ H. }; f                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
6 d1 O5 r6 q/ }% \( m0 M' ~            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
4 ]( E0 {9 y7 A2 u( A3 b! c        }
    }

* s6 J2 o1 [' E5 }( a& |    private static <E> void swap(E[] arr, int i, int j) {
' ?. t5 k7 z5 ]* n" z        E t = arr;
        arr = arr[j];
1 p$ R4 a/ v3 `+ S! x9 b) u        arr[j] = t;
5 m" L2 b4 O. W; Z- l  }( Y    }
0 `! ]* U% W* P% k* e
    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
, g& G( X8 r' V        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
+ Z) V* O3 ~* S5 `- O        }
    }
}

. Y, N' G' {2 e+ |3 w        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

使用 Comparable 接口
2 }) R" k1 _5 U; ?8 _, Y        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

6 z3 z2 `$ k: h( b+ O; @+ {import java.util.Objects;
4 S4 ]" }( o+ M1 U$ _- S
" @5 o) j1 P9 x& b, F; ]- |& d6 a1 `public class Student implements Comparable<Student>{
" L! J& c" z$ z/ m! c1 m% i    private String name;
6 @4 s: e. A4 o" G/ ?$ u! O- |    private int score;

$ n9 O% E7 m5 L$ v
7 `4 z& s3 R$ `: ?* K    public Student(String name, int score) {
        this.name = name;
7 R! y+ {, S2 D, e        this.score = score;
$ V) p- t, b  ]2 `    }

    @Override
    public int compareTo(Student another) {
        /*
9 B4 k( y1 j4 _1 {* G        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
$ a# O! _2 @6 s0 m, r; n7 q% W         */
        if (this.score<another.score)
& C6 f1 T3 O/ r! {9 [            return -1;
9 D! B- {7 r3 r4 `        else if (this.score>another.score)
            return 1;
        return 0;
) }5 z' x$ C% x' g, a        //return this.score - another.score
    }
$ M' m1 D$ ], J8 D: k( {
    @Override
    public boolean equals(Object student) {
, d0 o$ U6 `! R+ C' T! `6 K% R        /*
7 k4 ^  N- [" q        强制转换有可能出现异常，因此需要做出判断
* }; u3 T: i& z( n) _" i! S        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
. N' d/ \# [2 P, h; k! \' f3 J            return true;

        if (student == null)//如果传入的对象为空的话，则直接为false即可
  ]! K' E2 O) y# E4 a; C* _6 j! `& B' S            return false;

: y- u% h( t% m' D, L6 o+ o, g, D        /*
0 ~% I3 F, S9 j( t2 n        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
1 I5 M+ v2 v% l+ r3 Z+ \8 b% L        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
9 V: K5 L( G' M% K2 V$ V0 u         */
        if (this.getClass() != student.getClass())
  s9 q7 R6 P, ]0 X! b            return false;
# C1 f, I# d  i. O* z5 o
        Student another = (Student) student;
' ]6 y3 }( U1 ^6 h* |6 Y        return this.name.equals(another.name);//写比较逻辑
5 O$ F4 A- F9 W; P$ G( O2 {    }

    @Override
* Z: l. D# k1 [( l2 U6 x7 ]    public String toString() {
        return "Student{" +
7 M. Q  Y* B! d+ O/ n) e! V                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }
}
1 ]5 `' N9 _: f4 Q2 m) R
# M6 a) |( [8 `主方法实现类：

public class SelectionSort {

! @; a0 @, m+ p% @- i4 [0 P4 A    public SelectionSort() {
! ]% w% ^5 Q% y& h" ~* h    }
9 I$ \  Q3 a, [) J& r# m+ r
; p0 [* ]9 D( h4 Z- s& C$ `# _    //
" ~* W- F- w  ?- I. ?    public static <E extends Comparable<E>> void sort(E[] arr){
3 t$ @3 i- }! S- c7 i( S) L        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
0 z8 r/ w; r8 \/ o            //选择arr[i...n)中的最小值的索引
5 g! J9 m* @" d            int minIndex = i;
            for (int j = i;j < arr.length;j++){
3 Z, a9 Y1 u8 M# F# @8 n4 C: P3 c                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
4 k3 H/ W) Y% f9 A2 O4 }0 \* Y/ o                     minIndex = j;
                 }
7 O* ?; L5 a/ ^) |5 @) q            }
            //将arr与arr[minIndex]交换位置
4 H/ G* ~, i1 h* x8 M/ P            swap(arr,i,minIndex);
6 e% V8 U3 R* `% h' Y        }
    }

1 U$ I/ |' r( M6 R* P1 e# _    private static <E> void swap(E[] arr, int i, int j) {
+ H6 j& g! N; W2 v) U: |        E t = arr;
! w1 g. K, r" k, ~* y        arr = arr[j];
, w* J* z; t% S+ P7 m7 L! j. m& r        arr[j] = t;
" N/ J8 j- v8 H& `    }

( G/ J9 ~' C5 |% t+ v# J; B- J2 K    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
2 M6 z: ~, w* q( h% {, ?/ [        SelectionSort.sort(arr);
- e0 v! y) e9 k        for (int item:arr){
; m/ T- P: ?1 m8 ]0 V0 |4 j            System.out.print(item+" ");
6 S0 Y" e5 Z4 j8 n) p! Q! Y( I' a        }
4 N: }; y* d3 a1 [' |5 U2 ?  T        System.out.println();

7 O, P$ V0 Y# ^, q/ B        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};

        SelectionSort.sort(students);
4 D4 e# ^9 l$ y' ?        for (Student student:students){
            System.out.println(student+" ");
4 `8 g, {3 K3 _" c, ?        }
6 T) h$ w) e" N- S; Z* v
    }
% l6 _: A; ?. i$ j, s; F8 N}
' W  T. ?- q- [" @& v- f8 ^% t
. V/ d' k- r9 @0 R/ u复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。


2 d) W* o/ {- f
首先在ArrayGenerator类当中生成随机数组

0 {' U1 O( l5 E0 ]3 m* C7 ~    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
, U5 [" b3 w( G; P9 Z! j( o: [     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
" J: L1 a" b2 }  E. y5 h        Random rnd = new Random( );
& P- C2 G+ S2 z3 v        for(int i = 0; i< n;i++)
# S. Q/ j+ K# v            arr = rnd.nextInt(bound);
4 ?  y& N: m+ S7 j3 Y1 x        return arr;
    }
判断这么大数组是否真的排序成功：

public class SortingHelper {
9 I: B8 r! E6 F# S/ u6 [+ J; O  \( k% N    public SortingHelper() {
    }
# S) ~+ X5 f+ K/ K
    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
; }+ y8 D4 T+ N" h) [            if (arr[i-1].compareTo(arr)>0)
5 @. v$ J7 ^, F                return false;
2 o  r3 m) e& _, ?' i, h+ M        }
        return true;
9 D, r# v8 ]+ ]% s3 ]    }
$ A( ~5 `& n4 ~4 @3 s1 L}
" p5 L8 B7 i& a( G& ], D: c在SortingHelper封装一个test方法用来测试任意一个排序方法：

/ `* g* i+ H0 L4 k4 u- I% z1 q    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
/ G* \! W0 o( P/ P            long startTime = System.nanoTime();
  A& G9 a7 `* x: t/ q1 X( q            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
6 o% C2 E: X5 D2 P            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
" L0 Y* v: P( q! ?            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
6 j. p: U1 W$ n8 Y! Z    }
/ m; s3 c! N/ ]/ V* e+ G7 C  A测试时间：

* i% Z# f3 _) O6 w/ {public class SelectionSort {
6 B" q9 p6 U7 W# G; n
, _9 A3 U# y  }; n    public SelectionSort() {
0 @3 w4 ?: Y+ o8 n1 Y8 h% s    }
" B. z+ W$ O7 E7 _: _
    //
    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++) {
9 H- J3 `( _" d' G            //选择arr[i...n)中的最小值的索引
" {/ x' L% g, T# i% e4 F            int minIndex = i;
            for (int j = i;j < arr.length;j++){
2 l; A0 |# {4 d2 {5 P: S% L# n& b0 Q                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
4 p8 ]# L# q2 ^' G                     minIndex = j;
6 s. C( j- |. \# q                 }
            }
6 K% \: [' [( M9 C5 u) E# `            //将arr与arr[minIndex]交换位置
. ?! y) z* m# {            swap(arr,i,minIndex);
# D! o; `' o! [5 [( @' D; V/ _        }
    }

" ?3 n( g4 z6 Y. X' m1 {4 w5 z0 s7 C    private static <E> void swap(E[] arr, int i, int j) {
. T" F& s! H3 z9 a/ a$ O        E t = arr;
0 k+ c, ]0 a' ?4 t        arr = arr[j];
        arr[j] = t;
6 R/ H4 X. A; I+ j    }
1 |) k+ s8 k( [( F* j$ \
, K- J7 O/ I2 ^1 S, U    public static void main(String[] args) {
$ O9 `9 W, A' ]' s        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
}

其中如果要测试两组数组：
% N2 `8 R( |7 _
7 r& v$ Y* r; l; {+ j4 K    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
' N" b/ y  h6 s& g% `, K        for (int n:dataSize){
5 I+ P* x' o' J! F8 [3 Y            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
8 m4 m! w5 F& r7 U3 o        }
    }
$ z. D* c9 v! o, W6 Z" p" X

& L' q4 T& q% l3 f5 \ 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
$ k& B# J" k% }2 g: ]- L4 D原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122


* k9 m4 `% b0 m2 A$ g

1051373629

感谢楼主的资料
1 o. n( r9 u  _6 a8 F3 a