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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
( j) U! K: R2 I2 r
% m; G% T) o& M选择排序
( V1 ~3 R- X: [9 J# e) L
. }5 S5 ~/ q; c/ _选择排序简单介绍
5 w) n  }  p; k! }8 ]. J0 P7 G# @
实现选择排序法

使用带约束的泛型

使用 Comparable 接口

复杂度分析
# V9 f5 U/ @9 @, o1 X; j# e
选择排序
选择排序简单介绍
先把最小的拿出来

, ]3 K5 f& U. N) M- w剩下的，再把最小的拿出来
- |5 z6 k/ l( m6 p
' x+ \3 o; q9 f, T剩下的，再把最小的拿出来
- p6 d8 o+ j1 ]
/ d( f  U7 z7 _! D0 }* a8 p$ D......
( b- Z5 f) Z# T; \
每次选择还没处理的元素里最小的元素

        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

1 c) g" r8 y# u3 t5 v- y1 H9 F: v% [        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
# y2 `& d0 P7 d7 b
: ]% \' H5 {! `& l- M实现选择排序法
* @* S1 `$ n) K, t5 H" s1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
# S  K% W- C4 O$ q% ?; d  F4 A  B) G3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
2 A7 s! L1 `) r. G  {" r
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

  c" _5 j# g$ ipublic class SelectionSort {

: g1 @: }! X$ H' Q, _- E    public SelectionSort() {
* W: x+ _$ D- u: h    }
4 U: T8 Z7 w8 G- X* |  f
5 S* B. L! l5 O4 |    public static void sort(int[] arr){
$ _2 `: ^# ~; I8 `) O: q6 [        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
. f2 W$ w7 L3 V& ~            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
3 u1 p2 x& M; N7 E, O0 T                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
; R7 l3 [+ D0 G                     minIndex = j;
                 }
: G. P" b1 }7 ~0 f            }
            //将arr与arr[minIndex]交换位置
1 d9 ?: F1 E' ]3 D            swap(arr,i,minIndex);
, c* s- ]* r6 [/ G: E0 N        }
    }

2 \5 f  S" a( @1 J- `/ x    private static void swap(int[] arr, int i, int j) {
) Z$ w3 t2 r: T- G( f* v        int t = arr;
        arr = arr[j];
        arr[j] = t;
    }
0 `! N. o/ _" M6 I+ P
    public static void main(String[] args) {
. t, v" m1 y% E7 D, M        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
5 E7 O. j9 R: r: w2 [. @            System.out.print(item+" ");
        }
) |- _; O; x3 k% P    }
) L5 z; L) x" h}
7 B3 S0 `1 _  X. M; j
当前只能实现int类型的数组进行排序，因此需要使用到泛型。

9 ?3 n& P- L: {5 W/ d, D使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
6 G+ l  c$ u9 k2 `) E9 Q% [
: D" g" k4 k4 Xpublic static <E> void sort(E[] arr)
9 q% }! B+ D! V        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

public class SelectionSort {

    public SelectionSort() {
    }

: g1 k) T7 K3 V' g+ y& H    //
( ?0 L* Y+ M( I: [* c- j    public static <E extends Comparable<E>> void sort(E[] arr){
4 E( a* @0 E& f- {6 U$ V( E; e, D        //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++){
- J, Z( y) B2 o( D" Y: f/ P                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
2 ~; S9 H( l$ O6 f                 }
            }
' T4 v  R4 T3 W& c: p0 R1 V            //将arr与arr[minIndex]交换位置
5 @( n8 Q3 r6 y/ O0 O7 J) G            swap(arr,i,minIndex);
        }
. A+ Z" f/ }( k# `4 m2 _, U    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
3 R/ [, z; v' ?* ?" _        arr = arr[j];
# C7 }5 Q3 N6 {        arr[j] = t;
    }
) n5 b8 f5 x! G: C6 E4 E
, g  @- L1 s3 {! Q- \* k    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
0 K' ?" i+ x6 G* m        for (int item:arr){
& z! [- k2 I! D  S            System.out.print(item+" ");
        }
    }
}
. X$ N! E) X! E! v4 [* E* U5 `
( H- @: s9 H1 n* T        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
# j" r' I( A" p
使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
, ]4 t# A/ y  p. P# C6 T
1 n; m1 D. B! s& B# a; P5 `import java.util.Objects;
  k* @7 \: B& e% T3 ]
public class Student implements Comparable<Student>{
    private String name;
3 }3 o! ]( @/ E% `3 [    private int score;


3 d% `1 l; R' P) Y. A. [' P/ B    public Student(String name, int score) {
        this.name = name;
        this.score = score;
/ L( |1 ?$ D; w8 |/ v! t% }4 P    }

: h" a5 e& R/ X    @Override
    public int compareTo(Student another) {
# U, l5 ^1 \' _) H# w        /*
9 [' A! C9 w+ }        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
) m( g" L+ ^9 `6 i3 g2 d5 ^- ~        if (this.score<another.score)
            return -1;
        else if (this.score>another.score)
8 `- ?  L0 h7 D: V' \            return 1;
! Q% k" [4 ^! o8 o        return 0;
        //return this.score - another.score
# ]3 ~- w9 |& _+ H. D8 w9 O  B2 g    }
5 U3 K. M) J9 q. }0 k0 T
    @Override
    public boolean equals(Object student) {
        /*
7 Q4 [  t/ Q# W* x! b        强制转换有可能出现异常，因此需要做出判断
% D( e! I8 e% l6 l; e' N' ]' S5 l        */
/ O% C/ V* ~% b        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;
, Z& y$ \: z! |% g8 P
        if (student == null)//如果传入的对象为空的话，则直接为false即可
' f9 I4 O! _3 p" o+ p& @& U# T            return false;

2 @6 g7 x0 X: s        /*
/ U) p0 n% O! q, `. [7 z0 b        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
4 I9 J. u3 G2 D" t! b; t         */
& M) E4 R, w7 Q& N- N        if (this.getClass() != student.getClass())
7 N! S* y) k2 G) m1 T% `7 U- ?9 H            return false;
3 `& g9 P" @: `. a
6 c+ f) D; q7 L* W# {        Student another = (Student) student;
/ N: W7 u% G9 o; @( a8 F        return this.name.equals(another.name);//写比较逻辑
- k/ @( m; R, ^. i6 h3 ^    }

- V1 s1 o7 m$ O/ K    @Override
' E+ s0 m% E' _/ @    public String toString() {
5 ?2 }2 R( q6 o  ^. m        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
                '}';
( [; i/ v+ `" ?7 W4 d" }  H/ V    }
}

5 s' S9 C) K' S  _6 D6 j主方法实现类：

public class SelectionSort {
* H- [9 b: ~3 a, l
0 q% y. W$ u6 E& H( G6 m+ k    public SelectionSort() {
1 ~1 ^$ O# f! }3 i$ z6 P, V# P    }

    //
    public static <E extends Comparable<E>> void sort(E[] arr){
, f4 H- F0 L# M, m+ h+ t4 |        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
3 P. a& E9 z  V- l: N            int minIndex = i;
) J9 U6 y3 I% s/ L1 P            for (int j = i;j < arr.length;j++){
" [* h" m! u. l  Y9 D                //在剩余的元素中找到最小的（比较查找）
6 X6 V0 R- |* P. b/ G                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
, m) _7 O0 N% f& d! P                 }
            }
1 F* j0 s: F, O8 `5 |/ [3 Q            //将arr与arr[minIndex]交换位置
1 I; n+ P% `. e+ a5 L; L7 J            swap(arr,i,minIndex);
        }
& \/ y4 ^, y" }; s  Y    }

    private static <E> void swap(E[] arr, int i, int j) {
" u: H9 Z( O6 q, |& ^5 f        E t = arr;
. S" Z7 ]; _# l& v        arr = arr[j];
* [! [3 f0 [5 F- v        arr[j] = t;
' M/ S2 I2 }* t4 v' Z* ]8 k    }

% t4 b. S+ e( f; }, u; Q    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
4 D3 N( Q6 Y% @5 U$ n6 ]        SelectionSort.sort(arr);
9 \" H4 Y8 t0 t        for (int item:arr){
            System.out.print(item+" ");
3 D+ \1 z3 y; [' t$ \: `3 V        }
# Y" Z$ e+ {. A1 @; T: v9 e, W        System.out.println();
* ?7 N% V  ?+ n. Z2 h' _0 d
* X1 S- S- a: `: K" D! E4 ^& l: q8 i        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};

        SelectionSort.sort(students);
8 \: C+ I" q4 ^0 E5 R/ u        for (Student student:students){
! r( N' o' E( x: B( n$ g) D            System.out.println(student+" ");
! U' J/ A* f' e" O  M  F* i        }
+ a" v6 I4 S2 i6 M3 \
" M( V6 F9 p' Q- `: l3 H! B# V    }
# n5 `* [- K; D' w- {  x}

8 q) |$ a8 W1 T复杂度分析
, a' F4 r! n/ ?3 b0 g4 A3 q/ y# j        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。

. Q, E6 d! l0 \, p3 l. l: g

% @( e- `: |6 T2 J! f8 e5 k# w首先在ArrayGenerator类当中生成随机数组
6 b1 e# d2 ?% z- L7 d2 @  @3 {
    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
! b4 K. `8 f+ S8 v* N; @     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
3 v' j8 c5 {5 H' f4 B& C: A- _        Random rnd = new Random( );
& N0 V4 F- L/ U9 H$ D7 [1 a        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
% E2 }8 L2 O0 k: F" G    }
+ @5 `( E% ]6 T7 I! ~: ?判断这么大数组是否真的排序成功：
( @5 k7 d# @6 S) w# Y, a  |  `
7 f- W' r0 u1 t1 F% x* ^public class SortingHelper {
    public SortingHelper() {
    }
0 \2 ^3 A) P" b3 W" Y' l3 v1 _5 ~; ]
    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
9 l: r' W$ b: l2 e        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
- {3 J5 G  U2 A& ^$ P- k- x0 b0 o            if (arr[i-1].compareTo(arr)>0)
$ I, O$ E( A$ b7 ?                return false;
4 t; D: E! D7 y- v' C        }
        return true;
+ F5 U3 Z% F4 G8 w( @    }
, E9 l% \3 x' m' g# M}
在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
, O0 W  U0 K( w. _% |' e6 Y& |    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
  N/ F/ M9 C1 n1 C0 I" F% `            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
( S9 c6 p: a/ m! ?, S  |/ e                SelectionSort.sort(arr);
2 \, {* |3 s2 J. c: a' _: D) ~& E5 t            long endTime = System.nanoTime();
# q8 u8 [, r2 I  o2 H            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
/ I- g3 A+ s/ l9 H' d; ?测试时间：

public class SelectionSort {
7 n( }  F0 {& U4 r. |1 H
2 i: R2 w; D# L1 E. R& d    public SelectionSort() {
9 L! z4 ]3 C) y/ u    }
3 t( e+ ?; D& @) e9 O, k" g# O4 U
) A2 M2 V/ w0 K: z  O    //
    public static <E extends Comparable<E>> void sort(E[] arr){
! u7 k2 d! [' D5 t& s3 r        //arr[0...i)是有序的; arr[i...n) 是无序的s
, N+ l% X4 d0 N/ r' g        for (int i = 0; i < arr.length; i++) {
3 g' E- ~* v9 Z            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
. f$ M) u* |1 g9 U% s( w/ C            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
% J4 Q; r! G* ]4 |# n                     minIndex = j;
8 }+ j3 W9 f4 Q' {2 I/ ^3 X1 }                 }
! l9 g5 n* W" r6 l            }
            //将arr与arr[minIndex]交换位置
" p3 v; }4 Y: J8 j            swap(arr,i,minIndex);
9 ^: a% H1 J! s. k        }
    }
- }; z7 T! ?0 V$ I5 v3 o
    private static <E> void swap(E[] arr, int i, int j) {
1 D2 j) r6 Z- D0 i  n/ j" E( D        E t = arr;
! _9 \/ v. t+ v8 x        arr = arr[j];
! A. X3 D" x2 @' m0 P- B        arr[j] = t;
& ^; `! @/ `. A2 [4 O    }
  {. j3 v: `" u6 W! q* f) x4 v, s
    public static void main(String[] args) {
& w/ A9 z. F; |9 G' A% i; `. S        int n = 10000;
5 h) U$ G$ }# |7 |) p$ q        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
" _1 r2 q8 f6 U1 r% G: i$ X! }        SortingHelper.sortTest("SelectionSort", arr);
1 j! n0 P7 r5 c( {3 n# ?
: S1 X; k7 p' w7 B    }
}

其中如果要测试两组数组：
6 |5 I/ D& m- F* B
    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
7 ~: v, x0 p, i/ g; Y0 U6 P            SortingHelper.sortTest("SelectionSort", arr);
. H0 |/ N# T) B0 y1 A        }
8 n0 h6 l: m$ I2 p& p    }
( Z7 F9 F+ K2 H! T7 m
; C: T9 h+ v% X5 B8 w( W2 n
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
* V2 H( a3 _: \( J% H. B, u9 c————————————————
7 P# ]: V, j  N" h% X版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" e, i: z) h# k% B4 J: e, }原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

- q. p' d! B( _( t

1051373629

感谢楼主的资料