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

杨利霞

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

选择排序

) I  j: M- y* C7 l% J! b1 U% H1 u选择排序简单介绍
% A* J2 G. Y3 G$ v) j' }+ {) f* o! J
实现选择排序法

使用带约束的泛型

使用 Comparable 接口

复杂度分析

6 ~" b- u3 Q" K# K! q0 }' |选择排序
  U, Z" l% U# b& ^* w( q* j3 b选择排序简单介绍
" e' `/ d* J! P. j3 Q4 r先把最小的拿出来
5 [. @  k& x6 w4 d, U
剩下的，再把最小的拿出来

* l- H* O' D$ a剩下的，再把最小的拿出来

......
9 B' Z; B7 Y) P; X! v! G
  u  h4 k- C, n7 W每次选择还没处理的元素里最小的元素

        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
) V6 i% ^- ~8 q: X: x+ L; Q
6 q: x' z- x* s$ m* \2 d        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
5 ^0 w2 i9 h$ l
+ W: P' w" d: f5 E9 N8 Y/ b实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
3 I- Y$ d2 N7 s2 o. T2 O  q2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

1 S" {, T4 w/ n# x8 w7 ^        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

public class SelectionSort {

! a& o+ U' A" b8 v5 n    public SelectionSort() {
" b, k0 n$ M8 U; M# K    }

    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
$ @) o; ]) M  Q+ u, ]            int minIndex = i;
! |! w* v$ I; u4 \2 s. v2 B            for (int j = i;j < arr.length;j++){
* ~. k3 f* w* [+ q6 b7 c2 O                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
" i- c6 @. |. C: k7 ]2 `                     minIndex = j;
                 }
* ^* Z( ]9 A8 z1 U( @8 Y            }
. n8 u, L+ o( I- _! z            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
8 g7 z; [3 H3 d6 K    }
  @% q! c, M' Z4 i7 S( ?- p
    private static void swap(int[] arr, int i, int j) {
3 v' }- T0 e: A, e  m* o6 S6 E6 ^        int t = arr;
5 a& u5 q  p: W2 J5 h        arr = arr[j];
        arr[j] = t;
2 l7 M$ O! C; i. y; i1 k) O7 x    }

    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
4 S( l! ]& p  Y' p) A' s        SelectionSort.sort(arr);
        for (int item:arr){
- X& k- l  M* T# x/ L; t            System.out.print(item+" ");
, h0 V* Y  l8 L$ c4 l" G        }
- z$ w, Y9 l: f2 _    }
: a' D- p9 Q3 I}
4 f( B3 }/ g% j% Q
当前只能实现int类型的数组进行排序，因此需要使用到泛型。

8 c, f- X1 u3 G使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。

( Z' {: A$ x3 M$ }# T4 f3 cpublic static <E> void sort(E[] arr)
" |" [8 k( {' Q; D# Y        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
: v9 R- j. k, [( K0 G
. w9 @+ H1 u8 J7 ?# S, Epublic class SelectionSort {
6 `0 N# n- P9 z& K0 S
' R4 ?  W) r: F( k0 v/ a    public SelectionSort() {
8 [% ~5 C  c( D. p    }
5 Z! W) g( o' l0 Y
    //
' o% L$ j. t8 S  i( Z    public static <E extends Comparable<E>> void sort(E[] arr){
# T% l0 |. e+ g% Y$ w- K- }        //arr[0...i)是有序的; arr[i...n) 是无序的s
% O# f1 j7 z; f9 c  h- ~% b6 j$ N( n        for (int i = 0; i < arr.length; i++) {
( d" D. M4 P9 v. ]9 s8 q0 ~  e0 s9 T) d            //选择arr[i...n)中的最小值的索引
6 ~! q* }) B1 F4 E8 q            int minIndex = i;
2 ~* B3 y. L. j9 a' V/ s( a            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
8 P" E' `& c: H; l                     minIndex = j;
8 @& j' s8 Z" w) K: Q3 N% @+ K                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
7 R7 N/ }: J1 `$ ^( E# J0 U        }
    }

5 ~1 ]+ L( E! P1 J. A5 _    private static <E> void swap(E[] arr, int i, int j) {
' P) J# {% `( D( \$ Z6 \        E t = arr;
, f& x2 Q  S0 [- j        arr = arr[j];
1 W: b- q/ s, i$ y        arr[j] = t;
    }
" i! _( J) ^4 ~# I) z
    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
+ ?  W, y' ^: }0 r8 u        for (int item:arr){
: @4 M8 s% n9 T( _! O            System.out.print(item+" ");
4 p2 O' [8 T1 h        }
# f& Y7 ~' D$ L2 ?7 f    }
" N% q# e4 c6 h, q) a6 K}

        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
* m; k% i! Q1 y2 C  c! S
使用 Comparable 接口
! u: x" E6 }) S4 O% @        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
- }: ?8 b, G- J4 q2 I8 P: |- V3 G
import java.util.Objects;

public class Student implements Comparable<Student>{
    private String name;
    private int score;

% V0 S% h' o' k5 f: \( P
    public Student(String name, int score) {
        this.name = name;
5 P: V1 {: q. y        this.score = score;
! D6 m( y0 M( q4 Y3 U8 T, @    }
% J# S8 e  E. X
    @Override
    public int compareTo(Student another) {
        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
% t2 O. v$ @5 @2 }& s         */
! h4 O3 K+ t: j+ e' b) u        if (this.score<another.score)
            return -1;
        else if (this.score>another.score)
            return 1;
7 [5 y0 z# p7 u+ i9 o( E, Y# Y$ K. z        return 0;
        //return this.score - another.score
3 g# ~6 Y/ V7 S8 R; r5 L4 `4 F    }
& `. \( g- |5 B$ b4 a
    @Override
    public boolean equals(Object student) {
, i0 h+ V$ M* [# h. ]$ @" f! [        /*
) X! A) p* `+ D" @9 `# s        强制转换有可能出现异常，因此需要做出判断
        */
8 O- W6 x9 d& F& R; N        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
. _. X0 O9 S; V2 m! K            return true;
0 O4 \* ~2 Z0 C; E3 @* u. F/ \0 ^
        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;
7 o  v/ n4 }) U. g* W% @* K
        /*
! L0 e9 C7 W* E. v$ [. P        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
; J* a* f8 j; d4 F" {1 Z        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
        if (this.getClass() != student.getClass())
$ }8 G' ~1 t  ~" v            return false;
5 }1 d: e8 d0 J  k7 N
' V* X, v! ^& R& C5 d2 [8 B7 R        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }

' o7 R0 e) \8 {5 W* ?5 E  ^3 X% O    @Override
4 U1 `* d: m, y$ f- W    public String toString() {
        return "Student{" +
, g/ e8 G, ?' @9 h                "name='" + name + '\'' +
                ", score=" + score +
, _0 Y' T; Y8 s  D# I' x                '}';
    }
9 F2 }9 u5 t, P+ R! e) j+ `( y}
/ D% o7 U: J! G2 L+ E+ {3 H
主方法实现类：

" O* b2 Q' c4 Ppublic class SelectionSort {
% e' e8 M+ Q( a' p( Y; W0 F) F4 H
    public SelectionSort() {
- [3 j: M0 {! [3 [. p0 E4 k$ m( D% ~    }

0 e1 i: h9 U( o    //
    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++) {
            //选择arr[i...n)中的最小值的索引
$ g& ^7 e4 d5 L0 s            int minIndex = i;
- g, L% W( b0 G1 ^9 G            for (int j = i;j < arr.length;j++){
* y* Q- j( k$ t9 C/ @# c0 d) `                //在剩余的元素中找到最小的（比较查找）
& W1 ^- K3 u2 o- d6 e7 e- g# v; K" l                 if (arr[j].compareTo(arr[minIndex]) < 0){
; F+ c; ?, o/ k( h                     minIndex = j;
" _/ ?% I; _2 E* E* e( {                 }
            }
            //将arr与arr[minIndex]交换位置
; ~2 S& k/ C7 D- f            swap(arr,i,minIndex);
* k' g4 U2 W& [/ [' R* U        }
+ _- P  m+ v0 h: X. ~    }

5 m# V% Z( k( J% `7 L$ ^8 U+ Y. Z    private static <E> void swap(E[] arr, int i, int j) {
: U) k, W' j+ P: I* k        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }

: g0 z: z% V" x$ K% [' I    public static void main(String[] args) {
. O5 {5 x0 q* x9 q% m        Integer[] arr = {1,4,2,3,6,5};
- h7 a' g) B9 L8 K9 p4 u        SelectionSort.sort(arr);
        for (int item:arr){
$ p7 Q3 d- G: M$ F9 Z" C8 {( X- v            System.out.print(item+" ");
# v4 F) m7 d' M& I3 a" i" m, R- |        }
' ^/ Z3 g2 o) [1 K; e" S$ V        System.out.println();

& E4 c5 ~" m: q' k3 v, b8 f        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};

0 c0 c% N# H9 n, l0 N        SelectionSort.sort(students);
        for (Student student:students){
7 r8 m( ?1 k  {. S5 Q, _, S            System.out.println(student+" ");
% K% p9 R4 V( i! V  g5 y* r# _        }
5 ~) [6 ^% |; l+ Z1 s
    }
3 M& q5 Y: E4 D" X& b& t6 C}

复杂度分析
* j9 D" i4 h5 [- F& D7 b8 z2 _2 l        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
5 @5 n9 W& }3 z- ~

! h& r0 l0 A3 y. r0 H
首先在ArrayGenerator类当中生成随机数组

    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
6 X. x' K  G/ \- y    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
( R. T# N5 Q6 ?1 }( l% _        Random rnd = new Random( );
- t* }1 M" F8 t: U' G        for(int i = 0; i< n;i++)
0 S5 M; S5 ^$ X% s4 X+ }1 Z            arr = rnd.nextInt(bound);
$ ?# {& a% D! L3 b6 F: r$ K        return arr;
- V# Z4 ]! ^0 G: z    }
判断这么大数组是否真的排序成功：

public class SortingHelper {
  ]# d# ~; }4 P6 B' R    public SortingHelper() {
    }
( m  t/ _* a& R
) l) g/ W# n0 }" o    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
, ?0 }  k7 L2 d        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
                return false;
# @, t* g; e1 {8 f+ U' `- ^& l0 B$ `        }
        return true;
    }
}
, S) d& Y" |  c在SortingHelper封装一个test方法用来测试任意一个排序方法：
$ E) Z9 o9 L% m/ C
( P5 ^, |9 B- C1 _. ]    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
1 f9 E! F$ F* r4 E& I            long startTime = System.nanoTime();
* ^6 T, [2 o& x+ T8 N            if(sortname.equals("SelectionSort"))
3 i- w5 d* b5 a0 m: x4 E                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
5 {5 f* |2 U; ]% q  A& \            double time = (endTime - startTime) / 1000000000.0;
/ I- z% n$ K, B% ~9 e- y% n            if(!SortingHelper.isSorted(arr))
$ Y# ]7 v5 [, K+ T& X; V                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
/ u, G8 v  P* l' u$ ]+ p5 j测试时间：

+ S/ H+ n) T% J! h* Ipublic class SelectionSort {
5 g4 \* C4 q# i0 X' x2 R* L1 x5 M1 }
    public SelectionSort() {
+ J( O% ?% g9 k% q, V$ D    }

    //
0 v8 Q& Y: V' C# l    public static <E extends Comparable<E>> void sort(E[] arr){
4 Q9 d: k' x* M  |$ O, t        //arr[0...i)是有序的; arr[i...n) 是无序的s
+ c' M' t  Y& ^        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
* B+ J( X% n- T2 `+ j8 e            int minIndex = i;
            for (int j = i;j < arr.length;j++){
% m9 L$ v8 N  _$ ]5 k% z; O                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
1 D' D4 C( z! L. E; x: b                 }
0 f7 V5 T. w$ |            }
/ u* |3 I$ R# x! t            //将arr与arr[minIndex]交换位置
, t5 M- l; z: _5 G$ F, ^            swap(arr,i,minIndex);
        }
2 Y: V1 Q% j7 w  ~! e7 i/ |9 ]    }
' \: R. T7 D) q5 T8 N" z5 \
: _0 K% F" p4 A9 b+ P7 `+ S    private static <E> void swap(E[] arr, int i, int j) {
* s7 l( Y1 C/ {" X- {        E t = arr;
5 @* O% b% n$ c) O        arr = arr[j];
  U( H9 o% ~/ d        arr[j] = t;
: H0 D- k' S( E; y4 J8 t* u0 `, O    }

    public static void main(String[] args) {
        int n = 10000;
% L( F, X+ a- P  k3 o        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
}

, ^& t! M1 D4 U其中如果要测试两组数组：

" p) k6 |. {+ x+ c    public static void main(String[] args) {
- Q: Z/ U5 [0 x) w$ j, p        int[] dataSize = {10000,100000};
- N+ `4 H; ]3 a0 A) n* p        for (int n:dataSize){
' w0 Z: s# @5 k& H            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
& R6 ^& ]4 t& V            SortingHelper.sortTest("SelectionSort", arr);
        }
    }
5 \, m6 w5 e6 v
! ]5 j3 R, j7 T7 o
& O% N: w+ Y2 z' R- b4 }  P 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
" [; ?$ X, S) u) l, w————————————————
! }. A) _; k( E) ^版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122


# M9 O1 e; z/ M

1051373629

感谢楼主的资料
( k$ J6 U! ^$ b1 o' B