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

杨利霞

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

# p, x. D* q  i6 V2 n选择排序

2 P: C& C) z6 q- u选择排序简单介绍

+ c' q) G& z/ @+ v! O+ ?实现选择排序法

: Z/ O4 @1 f7 k5 X3 H使用带约束的泛型
( x6 ^" g+ q7 |9 d
! J  I" k% _; y3 m使用 Comparable 接口
. l; G. I( m8 h9 y+ w& F  J! c
- a- Q4 S5 [& Q" j8 }复杂度分析
: f2 T, U8 l! Y$ [7 U; y
选择排序
& R: r6 a# t0 E* e- B选择排序简单介绍
先把最小的拿出来
0 B4 V6 d9 j* a" F5 c6 y
7 _- [# z5 h4 X8 @' Y+ c# |剩下的，再把最小的拿出来

, ~! S* L0 W! J# g剩下的，再把最小的拿出来

8 }  e& R3 O5 J+ n......
3 D. [! h* }* q" V
0 ~8 }0 M/ c; i每次选择还没处理的元素里最小的元素

; `) ~1 v. B/ g! u6 f, g; R. A9 D. Z        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

% s* @) j3 T* {1 r) |# ?        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
7 f( Y' Y; i, I. i: V& F3 T' J
- g9 b1 K- l2 u- R6 o) }实现选择排序法
* S7 D; e3 z4 ?3 z& X6 Y8 [1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
0 s  o) z$ B; a- N8 a# ^" N
2 O2 p5 M$ c( Q6 m# u        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

6 a1 b) P; w* g/ y' X: h8 apublic class SelectionSort {
- x: g7 e0 I5 h) m4 ]9 I7 [* w2 v
    public SelectionSort() {
    }

    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
9 `& k  O5 i) H7 I; s: t' ?        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
( M& u; e. K4 u0 W1 \+ D( {* D' k            int minIndex = i;
            for (int j = i;j < arr.length;j++){
* a5 s" a- b( k9 ]# e  M! S6 N                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
+ S! `4 @4 E- ?. w1 [) m* x1 ~                     minIndex = j;
5 \. B" g3 E  Q& S" N6 {7 r                 }
            }
  V; n7 D8 Q9 C            //将arr与arr[minIndex]交换位置
& S+ D5 A$ p2 M% o. i. A+ N8 m$ o            swap(arr,i,minIndex);
$ n5 z: _8 J! r5 f+ n" l4 S) u" ?        }
    }
; O. l9 |1 b0 Z4 h% D8 l: A1 p* Y' y
    private static void swap(int[] arr, int i, int j) {
0 g, T/ V# z* s        int t = arr;
        arr = arr[j];
        arr[j] = t;
. h- h2 s% ^7 r. P1 p    }
, ?8 N" l" c; a+ z+ C- K, D* C
    public static void main(String[] args) {
" F; \* B2 ?/ J( C5 [  @$ ^        int[] arr = {1,4,2,3,6,5};
" Q! y  Z3 c9 e& X( ]        SelectionSort.sort(arr);
        for (int item:arr){
' }. [9 u6 N$ Q2 }' q, a; s. N            System.out.print(item+" ");
- h  i% D, U2 ^4 P& A7 n        }
    }
}

当前只能实现int类型的数组进行排序，因此需要使用到泛型。
$ s9 Z4 u5 B2 L# z+ e; L3 `
使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
4 x3 C" N3 Z+ Z; N( |
public static <E> void sort(E[] arr)
4 \1 G! v& g# n) l& Z3 K        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

" q+ \7 b" T5 }# {public class SelectionSort {
5 e  @$ h; W9 W5 x% D9 q2 ]
    public SelectionSort() {
    }
) \& y+ C3 s4 w/ G8 x9 P$ u
    //
* c% _& Y# B; _/ c3 k    public static <E extends Comparable<E>> void sort(E[] arr){
! S2 R  f+ Z* a; n6 ~6 k        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
, N. r( Q9 K. E9 Z            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
: f. F  l* g: i! x' D                     minIndex = j;
                 }
            }
* d2 i2 n2 x  V% S            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
- `, y6 @$ z- L3 c  M    }
1 d$ a3 \  l0 A8 Z9 B
* c# S. D3 q: E9 Y    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
* o  ^. h3 B% v5 c. Y# f2 P& W        arr[j] = t;
    }
6 k  ]! @  P# l9 J8 k
    public static void main(String[] args) {
& a8 i9 r7 ]" x; K) d        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
5 O: E! g; d: Z& E        for (int item:arr){
3 \) ]: g! B" O6 b5 x- o. D            System.out.print(item+" ");
        }
4 I6 J# ?  k+ X0 H" ?' ~! O    }
5 g& c# B  W0 R* b6 s}
; d2 q+ s: g6 M6 @
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
" W1 W. ^4 Y4 s* H4 \) j8 ]$ X5 R  y( `! X
1 K6 w0 J& |, A% _0 T使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

import java.util.Objects;

# K1 i) C5 j& R$ c& Qpublic class Student implements Comparable<Student>{
) W  z/ T. l: {, P- l' y    private String name;
    private int score;


    public Student(String name, int score) {
- p  S7 B$ v" L7 J* I( y        this.name = name;
        this.score = score;
    }

    @Override
    public int compareTo(Student another) {
) k" c* Z% ]' L& S        /*
: T* @/ u9 _5 E3 K6 N        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
0 V1 P! }" v- f& K  p) g  z- D         */
$ _9 }4 X7 V/ |, W& h- R! i        if (this.score<another.score)
' [6 X+ h: x( c/ V+ D/ j* h            return -1;
. t5 `, R  o2 x1 X4 a, ]        else if (this.score>another.score)
" ~" W* H" n  }2 ~' M% d            return 1;
        return 0;
4 f' l; s$ b/ d3 W0 e        //return this.score - another.score
. K' D! O. A' @. e    }

" i8 J/ c7 }0 p$ _! `- L3 P    @Override
    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
/ j$ D6 W+ O. Z; K6 U% s        */
' _% q  l+ h, a; Z        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
0 B$ P! n3 X: ~1 r8 B/ Z1 F; D            return true;
$ K  u  \+ i) q3 D9 `2 S
; ^9 I9 _( r! s3 G  z* v        if (student == null)//如果传入的对象为空的话，则直接为false即可
. @1 H: v! \: n4 o1 r/ {' N            return false;
) e$ c3 z- ^$ V# \6 f  X+ v
        /*
3 S& V3 q7 Z: p) n  C8 G        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
" d) z3 }. u' p5 y        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
  m8 a$ e& H7 `9 c$ U$ O: b' p9 H        if (this.getClass() != student.getClass())
! k& x* I2 M* c% V% ^$ ]+ v9 P8 n/ y. [            return false;

        Student another = (Student) student;
1 }$ z2 h' H2 @# j  B        return this.name.equals(another.name);//写比较逻辑
; b! C0 v- G0 d$ G/ U9 |    }
; v$ I  P7 u- N9 K6 a
    @Override
    public String toString() {
8 w) t" i3 Z7 p5 W9 u        return "Student{" +
) z% ]# R1 U  N" ~3 Y4 h- {, N                "name='" + name + '\'' +
                ", score=" + score +
                '}';
4 }4 \5 g+ M( x2 T    }
8 w0 z7 Y/ k% q4 x& e}
6 L( o& j, D% P/ q' S
* Z8 n7 b1 |& Z1 c* ?# O主方法实现类：

$ |1 ^! c9 v& }4 K0 ~public class SelectionSort {
3 [% a4 a( G# W4 K# ~* z# J0 u
" v: B. R7 D+ }. {, Q9 h: H    public SelectionSort() {
! }% k# M$ U* b    }

4 E3 r* W$ ]. o9 I3 ^3 g! a    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
2 {; o0 C9 \. b+ F/ J        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){
/ W, @3 f, I, ?) o5 u                     minIndex = j;
+ U1 x" Z  }' `. Y2 Q% x                 }
            }
2 ?' K, H$ g& j$ c            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }
& c  E* X& q6 h
* j# n0 {) x; w0 W) H6 Y    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
2 v$ l& B3 a+ O( {  e0 }        arr[j] = t;
% J2 W; f. X4 R$ [    }
& ]5 G( K+ Y- v
    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
; J3 i3 k3 M' x- j7 N9 F$ {$ [9 |        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
        }
* O: @3 f9 l1 A/ U        System.out.println();

        Student[] students = {new Student("Alice",98),
) D4 J. r5 `7 @- U; x. T                              new Student("Bobo",100),
                              new Student("xiaoming",66)};

        SelectionSort.sort(students);
7 Z3 N, N& i2 N$ x" L& B9 s$ f. X& \        for (Student student:students){
9 n" u$ {8 u9 }% V; Q            System.out.println(student+" ");
% p# s* N* n1 g  N2 V3 W        }
/ x0 T% M2 y7 T  x+ s/ E
! o1 @6 D# O8 [' I9 D& r    }
}
5 T1 _' k5 a6 l) M
& o5 j! n+ a0 r) d3 Q2 K9 [) Z复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
+ z, E4 g8 c8 i. L
5 t! n' s, r( a  n
# C1 i. x6 o# a1 p* t8 M# V
首先在ArrayGenerator类当中生成随机数组
8 j5 N- N; U8 B: H7 H( k3 L2 G
    /*
8 d/ m( }4 [4 A; ~) C    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
    public static Integer[] generateRandomArray(int n,int bound){
$ A- R  t' o0 v+ B- U        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
- N; Y1 k6 E" F7 n5 D, I& l        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
    }
, v, T/ d2 b  G. @  \判断这么大数组是否真的排序成功：

public class SortingHelper {
. m8 m) N0 h2 |" b4 Z3 F    public SortingHelper() {
    }
5 L) D; J  G8 O2 q
    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
$ s: h, ?3 q2 w: |' ?- t        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
  e% y+ G) }( W% B+ J            if (arr[i-1].compareTo(arr)>0)
                return false;
        }
        return true;
    }
* X' S  J% M, M0 @7 M}
1 R% G% X1 A# e' \在SortingHelper封装一个test方法用来测试任意一个排序方法：

  {+ \/ Z' z+ H$ b    //封装一个test方法用来测试任意一个排序方法
8 N# J6 T* i9 F) W    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
, R3 x8 s( B0 O. c4 E5 m1 F+ L3 D            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
% t- J3 t; C1 }9 e4 z            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
. v% w* Y" l/ y) Q% v1 [- g# r            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
测试时间：
! {- g* J0 g  o9 }) q& A' u& g
public class SelectionSort {
/ V8 [: F# H# L* i/ N
9 J* L, b; t# Q# W8 J# C    public SelectionSort() {
    }

    //
9 |9 G0 O$ q7 y) G' J; W    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 Q8 o) P% `$ T; O2 Z8 F7 N            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
" y: s7 s; m; k* b* r            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
9 q$ o! v) C6 s, e: z3 F                 }
) Q, c, j! Q% b6 R6 R$ ~- M9 i/ S. x            }
            //将arr与arr[minIndex]交换位置
8 G) j- T5 Q- C2 Q! g  [            swap(arr,i,minIndex);
        }
    }

# F- ]! T/ W! S) ^. F    private static <E> void swap(E[] arr, int i, int j) {
  Q0 C# F( U" C0 A. F) e0 i0 \        E t = arr;
9 k+ t0 W* W* ^8 ?, Z' ^$ |        arr = arr[j];
" r/ Q# t! S' r4 @" O- S        arr[j] = t;
  g# A. t4 K$ Q8 z6 d    }

- T" m5 F3 K# E3 v. [    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);
6 t9 {" S1 j* v$ S- [8 `
    }
}
* w  z7 z- S9 m
( w& D$ P( v. M  m, X其中如果要测试两组数组：
8 g3 U  a- k  |9 w) ~
    public static void main(String[] args) {
; Q/ E- \( H% M; K+ k& a/ Y        int[] dataSize = {10000,100000};
1 B- m% W1 S, t# c        for (int n:dataSize){
, K, l% v6 R( R. t/ N2 Q* @8 b            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
) `  q9 o/ p* G! V( o( r            SortingHelper.sortTest("SelectionSort", arr);
        }
) |; F  ]" ~/ y* ]3 I    }
. |( v' c  l/ K
& M9 z. E5 Z  V) B
, j/ n+ q3 R3 @# P3 n3 o 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
' H* b3 S' L& t8 f$ L& \————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
! H3 H$ j3 Y. s  u- ~  X

1051373629

感谢楼主的资料