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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
- b4 a  Z- n( T# M3 {$ e6 B
4 O$ D. a2 K5 T. @选择排序
' z, S9 Q2 D! H8 m
选择排序简单介绍
+ ?% F& M) M$ F, [
实现选择排序法

* m' z: t7 T( `* Q使用带约束的泛型

6 p8 l9 K+ h! c, v( ?. I- H% g6 u2 O使用 Comparable 接口

5 v% @& w/ l  u' W6 I复杂度分析
" O& P1 k2 V0 t! |
选择排序
8 o  E( l( Z3 {% z# \  s$ n选择排序简单介绍
7 ^2 d3 V( P9 m先把最小的拿出来

剩下的，再把最小的拿出来
& H. i4 J. L4 N0 i/ q+ G+ b
剩下的，再把最小的拿出来
7 h1 A, a! s& F2 A* ]3 [$ K
1 G" |" q0 \4 u$ B4 v......
) t' n0 Q2 N: b* H7 B+ s6 D# k  [
每次选择还没处理的元素里最小的元素

) u0 Z3 ]2 E0 V9 B/ b+ o4 V        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

) g7 b# L+ l% @! b        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
) }# n7 n& L: f1 @) n8 E
实现选择排序法
4 p4 b- b. |- f0 s1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

# v9 ~$ c2 @; }! @$ h8 r+ Z% ]& c        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

public class SelectionSort {

    public SelectionSort() {
    }
+ _( \+ _, B& R1 m4 n
    public static void sort(int[] arr){
        //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]<arr[minIndex]){
; _9 P6 z/ ~! F0 j1 E& _                     minIndex = j;
                 }
            }
6 j: q. k9 y* X' j            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
$ u5 V+ j/ n8 L6 ^  Y    }
5 |: B$ s  [3 S4 z
    private static void swap(int[] arr, int i, int j) {
        int t = arr;
* a+ s6 A6 s* h+ X        arr = arr[j];
        arr[j] = t;
0 O8 f  _4 @  g    }
" o% H8 \( R+ d! J7 Q. t% e7 b0 @
    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
# m& y9 X3 X  Z$ T4 \' s        SelectionSort.sort(arr);
. i5 z! c6 }$ W! ^4 h; S  ~        for (int item:arr){
            System.out.print(item+" ");
        }
3 \) N6 s$ O$ n2 R    }
9 t9 {. N5 i- |$ e}

当前只能实现int类型的数组进行排序，因此需要使用到泛型。

使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
; X$ M4 H! z% x6 C5 q
6 s: S) Z3 K5 P/ tpublic static <E> void sort(E[] arr)
* O7 f9 a0 U' V0 D        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
+ ~  l- ]5 F/ r+ Q# m0 O
$ X# j1 _2 l) g( R& k" n% v  Lpublic class SelectionSort {
. J% t3 k- `: q, E0 H2 p, e
    public SelectionSort() {
    }

9 i4 w1 f4 f" ~. T    //
  o5 T; d9 C8 H" M7 ^0 y: L    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
! ?2 {* j/ n% Z" f. Q$ u" @: g0 u        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
( u: q! g; W0 r; U& i- H            int minIndex = i;
7 x! k# x0 b% o            for (int j = i;j < arr.length;j++){
$ [1 a& n0 H& s                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
, |8 c) l! i1 I0 g$ Q                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
; b  k1 @" `2 G, [. J: f( q1 [/ [7 c    }
1 L7 N2 e$ d( j! x
( Z4 g, N1 V% N* K    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
$ b7 m& A& A. E5 R% n$ O& v% ]        arr = arr[j];
' T" W! p; S1 t8 s& B/ n. `2 i        arr[j] = t;
    }

, T7 [+ b% R- C# N( L$ k4 B  D# W    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
% P$ I1 O0 X- e$ w! L        SelectionSort.sort(arr);
& \: n7 d4 q+ z        for (int item:arr){
* A; l" Z) V3 e/ W" L- U9 s            System.out.print(item+" ");
- z. B* ^2 j9 I& Y8 ?: I, F- \        }
    }
* ]( O+ }- R* J- v0 w}

& y6 E4 ~% l7 y% V. k" P* b        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

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

0 Y. R: z# P' F' ?+ a3 [8 oimport java.util.Objects;

5 e! A2 ^' w& Y4 k6 @4 Qpublic class Student implements Comparable<Student>{
- o2 A  t6 F2 z    private String name;
2 x0 e8 I3 n# ^9 y& l7 [, `; x    private int score;


    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

2 T2 \6 b  f$ U9 W5 [    @Override
, _  l6 e, U+ S# U    public int compareTo(Student another) {
) w: S! A# ^) Y. A0 P# q& R$ d        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
$ E( `' i. J3 ^" p: B; C0 E        if (this.score<another.score)
' M: ?* V' q3 W: f% i# l            return -1;
        else if (this.score>another.score)
            return 1;
% W' K: |; ~6 \0 ^5 f, s        return 0;
0 G8 \2 \( @. C! d7 W' j        //return this.score - another.score
    }

    @Override
    public boolean equals(Object student) {
9 n) r: s9 H% R, e; D        /*
0 V- C% p4 A1 b        强制转换有可能出现异常，因此需要做出判断
/ n& C4 {( L& \* D        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
4 s  y( ]9 m7 ^  K2 l            return true;
  ?  |6 n& ~5 `4 p, C
        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;
! P: V* O8 p$ k0 Q
6 F4 c5 j6 ]9 h        /*
$ H5 f2 v& A. w6 V        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
: b  k& P8 n7 s& m) ?/ P         */
7 Q3 t( Z6 l# n3 M        if (this.getClass() != student.getClass())
' U: p& l; \' o  P' y            return false;
0 [: V3 y" v! X$ _" T) J2 @6 s$ n
        Student another = (Student) student;
4 m3 t4 r' F5 p        return this.name.equals(another.name);//写比较逻辑
" q3 o. H0 w8 w6 l  G# g- u6 F/ x    }

    @Override
    public String toString() {
+ ]' R, j! U" k' V% m        return "Student{" +
* S7 J8 y( K6 A. z8 g+ V                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }
; E7 x. Y; ]+ Z}
$ p% ?( C  R6 T2 c
主方法实现类：
6 c2 G3 Y7 K/ W. c  ^
public class SelectionSort {

- Y# y( x% k4 t1 l' E1 f& W# v! |    public SelectionSort() {
    }
$ O! f( U/ M  F  P$ s7 N
    //
    public static <E extends Comparable<E>> void sort(E[] arr){
9 z) ?! H, y4 [' B7 M: V: U        //arr[0...i)是有序的; arr[i...n) 是无序的s
+ O# [1 ]( N8 {' K0 |        for (int i = 0; i < arr.length; i++) {
$ u* z8 `0 e; ~' @            //选择arr[i...n)中的最小值的索引
7 u- O' N! y4 m* V2 Z2 L7 h            int minIndex = i;
1 ^) R- ^. X4 S2 n5 a, a/ x            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
            }
$ @$ h& ^: u; E! x+ K5 l            //将arr与arr[minIndex]交换位置
2 ?9 W7 F! p+ w. i' }$ a# M3 g            swap(arr,i,minIndex);
        }
8 z, {* W+ S. U" ]5 |2 g7 ]' Y    }

* a. \8 O/ X. v' o9 n# c8 y    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
) A6 G) ]9 a' u1 h) P    }
$ [. B. n* F. A7 y4 l! q& l" @
( f* |# q  ^( S    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
5 {1 a0 T! K& Y) V6 a( z        for (int item:arr){
            System.out.print(item+" ");
        }
        System.out.println();

1 F( B" l7 ^! F/ q        Student[] students = {new Student("Alice",98),
, T; H! t7 G5 T                              new Student("Bobo",100),
                              new Student("xiaoming",66)};

        SelectionSort.sort(students);
; I7 I4 C& N( `        for (Student student:students){
            System.out.println(student+" ");
        }

9 ]0 J; I; y% u. N: @( h' w    }
}
5 P/ e, c0 S/ m( n( e& e
% A$ B5 x/ T4 [& T0 y, v复杂度分析
' c* v6 C  e3 c/ N, T+ g! g* y; n        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。

2 f) x5 v0 q% l) n7 O1 I

首先在ArrayGenerator类当中生成随机数组

    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
* l  [, Y/ c+ ?. b& x' ^  Q7 m     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
" D) v7 K/ x! D2 \0 G        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
& g! G0 Y2 y6 s  D5 M        return arr;
    }
, m% b" n) Q. n( K, [判断这么大数组是否真的排序成功：
' ?4 ]2 o' r& X2 N8 C( v
public class SortingHelper {
$ L! z; G8 {9 u+ Q% ]    public SortingHelper() {
    }
* Z: k% e: R4 T4 G4 ?
+ {. j# X/ S+ ~, Y    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
. I& f/ l% V" h# \6 u* U, N        //判断数组前一个元素是否小于后一个元素
, k/ r1 J$ M7 O. z' p' I        for (int i = 1;i<arr.length;i++){
5 y' F1 ?3 J2 [: K" B+ Y) w            if (arr[i-1].compareTo(arr)>0)
1 P8 |! f" O- F6 j                return false;
        }
! f" \8 c* y6 u2 ]. ]# }  {6 r        return true;
% e  b% O9 f& Z8 o    }
4 m; z2 m. w# i/ t' A# T}
, C1 ~  C% s0 `  Z" P在SortingHelper封装一个test方法用来测试任意一个排序方法：
7 \* R# P# U( z
    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
- E# n: y3 s0 y9 P. V            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
) G8 g  K7 h& _& P" w' Q            long endTime = System.nanoTime();
; ]# [  @: _5 a/ n) X" J8 J& w6 f            double time = (endTime - startTime) / 1000000000.0;
7 p9 O: i, j) i. \* ^/ W            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
0 |9 g+ s2 p& M" r% T# J0 D3 b5 a            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
( m  s+ \  ^6 |& h; a测试时间：
9 K( A  n  w  [1 _/ `& R
public class SelectionSort {

    public SelectionSort() {
% b$ r0 L9 I4 D$ Z7 H    }

    //
) C4 ^2 k7 z7 i1 h& Y+ J/ q" |    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
/ f2 f3 U0 F3 ?0 ?        for (int i = 0; i < arr.length; i++) {
% I2 g. `% n6 q# M' n6 g            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
" ?; d% V+ `/ A            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
. |  Z( F2 m! k2 k, [7 O                     minIndex = j;
                 }
. K. P$ Y  ]; U            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
$ i) _$ ^* w0 A( Y& W6 ^5 t        }
" U6 T0 a) G  V/ h! x$ N    }

    private static <E> void swap(E[] arr, int i, int j) {
, ]% j% w6 L2 H/ }) `        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }
8 R( x4 |7 `; i+ C: Y4 O
9 f& o  o8 C& N    public static void main(String[] args) {
. l& y, U$ Q* C2 `; c. O" V        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
& S- i1 E: {, ~0 q' x}
: F4 |0 t5 P+ `
& v' x/ N3 P# U4 |$ l其中如果要测试两组数组：
: P; L1 `' p8 d
    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
2 @& x; \! i7 T+ ]! P        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
/ ^6 n' X% ]# F" v" n        }
0 f9 f7 K: @( M8 A* f3 p( |    }
! ?4 Q9 Y6 \/ s7 h
# t* |( w% c' g" p+ N- \+ `
- ~, R' t6 t3 l% U* k# n: F 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
2 A3 j' t' t& d: x6 D————————————————
. Y( o8 r4 n' n4 D- |版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
; I+ E0 w1 L& F7 O7 O原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

& r9 K0 T1 K7 V- r2 O2 @& y5 w* C

1051373629

感谢楼主的资料