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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
" }  N! k+ n  `7 X: _目录
9 ]" y. z- [! d  M
7 W8 b2 s3 J$ L0 M选择排序
, _; G0 E, t* ]0 H; ~
9 h: D4 j. z' _+ @5 p3 `选择排序简单介绍

7 v* G6 r( G: D# C9 }( ?实现选择排序法

使用带约束的泛型

使用 Comparable 接口
% a6 e* L( X4 c  C/ V4 d
复杂度分析
5 b: e' F' Q, P' F) g7 z" N" p
* t# u4 N4 g, B* X选择排序
选择排序简单介绍
先把最小的拿出来
% r2 ~1 i2 W0 ?4 H3 y
剩下的，再把最小的拿出来

剩下的，再把最小的拿出来

" f' }; |* X% T9 O8 d% C* ]......

每次选择还没处理的元素里最小的元素

# J) |* [) {$ n  k- U        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
% H5 b" \# U7 {# i  u3 K
        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
) v6 {# M* p- \+ \2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
3 ~, n; ?4 r& A, M
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

# V2 O0 C6 K. e4 E) I7 T+ c! Hpublic class SelectionSort {

    public SelectionSort() {
& A3 x6 r1 b4 P$ H7 z4 J1 @& q' o8 p5 N    }

    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
, v% I: W, R) k- ?9 @/ {, E0 F        for (int i = 0; i < arr.length; i++) {
, s6 T! `. M! ~# L* a3 w            //选择arr[i...n)中的最小值的索引
: w2 p; |4 y9 _) e  V            int minIndex = i;
- V( [0 K* T' _9 q+ k* d+ D% b9 u2 O            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
, q* r( g! L9 z: L            swap(arr,i,minIndex);
/ `7 U3 a% \' p- Z9 ~: k        }
    }
  x0 g1 a8 e& K
    private static void swap(int[] arr, int i, int j) {
        int t = arr;
7 M7 S" S8 M+ X1 n  C        arr = arr[j];
+ d; d# b: e9 N' J0 G$ a        arr[j] = t;
    }

    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
* ^. o& Z4 ^) g  f% j5 E8 a+ r9 }        SelectionSort.sort(arr);
% s  E  J4 a6 t% s        for (int item:arr){
4 \6 n) a. M5 H3 n: @            System.out.print(item+" ");
3 M; `0 A- m8 Z8 K! @/ B        }
    }
}
/ `# E5 L1 ^# g1 A+ o9 w
当前只能实现int类型的数组进行排序，因此需要使用到泛型。
5 \8 W. f, ?% ^" I; ~- f
& t4 l, X- T5 ^8 ]使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。

/ n4 G/ ?, W) bpublic static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
% R) B3 g- v# ~, S( ], ]. F
: v6 ]# `! Y" q4 D: t; j( @! Cpublic class SelectionSort {
# C6 ^9 |$ R1 I
    public SelectionSort() {
    }

& \, P- J  |: x: ~    //
    public static <E extends Comparable<E>> void sort(E[] arr){
6 C) y( z6 r1 |0 H, z) T, s2 ~        //arr[0...i)是有序的; arr[i...n) 是无序的s
2 f0 m0 F0 J$ e1 Z        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
$ ^) N2 O! K- C) L; a: y            int minIndex = i;
* n# p, ~& j' W' o6 p5 i            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
6 B0 e# }9 {1 R+ o1 y) u                 if (arr[j].compareTo(arr[minIndex]) < 0){
: h- R) b& s& v% V' H' a$ _( V                     minIndex = j;
; S0 b4 Q9 ]% ]7 y3 y                 }
            }
' B5 U# k* t9 A  K            //将arr与arr[minIndex]交换位置
- q2 F5 F$ {; m3 s; o            swap(arr,i,minIndex);
        }
    }
3 V( Q- n: e# ]% N6 K( s
    private static <E> void swap(E[] arr, int i, int j) {
( Z0 |, B2 @' J1 Q1 U1 e: \4 Y! V        E t = arr;
7 u; B- a, R. o1 u4 n        arr = arr[j];
5 q2 I5 Z$ n7 n9 _( {        arr[j] = t;
    }
1 D! X6 i  y( m  w' Z% @
% m* L0 }: o% }* K    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
2 Z- `* K" f3 S        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
/ h% Z: A! p7 ^, |1 f, y        }
7 \' G$ q3 @. q    }
}
7 E3 @9 ^: O5 \5 c
" ^4 G5 I! |- E1 G0 m- a* I        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
, h2 L6 [$ B3 O: a' L3 H( B
使用 Comparable 接口
' o7 ~5 `6 C$ t/ Y6 {7 c6 z1 R: O9 F        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
3 m" S" J9 s0 v, M$ v7 ]
import java.util.Objects;
' x% e3 q( Y- @! ?8 |9 p
public class Student implements Comparable<Student>{
    private String name;
    private int score;


    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
' M9 q/ D1 g4 v8 f
    @Override
  y; x0 u6 Q% J    public int compareTo(Student another) {
9 P+ Q7 t- N' m        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
3 c: c# [5 I& W5 \        if (this.score<another.score)
7 V, Z& |$ D( o            return -1;
        else if (this.score>another.score)
            return 1;
        return 0;
8 D  `) Y* @; x: x1 }        //return this.score - another.score
    }
& g8 O. H: N5 ~
    @Override
& }7 ?% m# |/ G7 [    public boolean equals(Object student) {
        /*
8 b3 w" X' F) |1 `& U- [! v6 B- ~        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
9 f8 m' S& c, ^( n1 w' o            return true;

        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;
, {4 }# _2 H/ z8 E% P) ^. a
, ^8 Q, ^, k* C3 f" x4 r7 f        /*
        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
- Q. j  i1 ]- `6 O' |        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
: q& ]# J: h( L: K8 c- k        if (this.getClass() != student.getClass())
( D' L( l4 G+ h9 f            return false;

- c" {8 Z" S8 W& v        Student another = (Student) student;
8 a' o0 n/ W7 V: _- e        return this.name.equals(another.name);//写比较逻辑
( M8 r7 q9 Y( S) Q9 k    }

' }! s3 H' f5 W5 W8 j, T# r    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }
. }* |% i, u* [% m% D}
) y6 X- t# W7 U9 a& c! @
主方法实现类：

# Y0 ]$ c% k& ?' I* X: v, g' P% Opublic class SelectionSort {
$ R& ]& Z, _( z" C
" k& c( m! z  B    public SelectionSort() {
    }
7 g9 Q3 K4 p0 x: D% P3 ?5 Y3 n4 s
0 U0 `: q1 O/ Z- t    //
9 v. R' D; L3 l3 m* T( T0 x    public static <E extends Comparable<E>> void sort(E[] arr){
& a5 ~8 l2 U0 y6 Q8 I  c        //arr[0...i)是有序的; arr[i...n) 是无序的s
  S) z$ ^* L  H* }# Z        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
4 o6 ~' S5 z- W# O- h" c9 }            int minIndex = i;
            for (int j = i;j < arr.length;j++){
+ P" P  z/ m5 z6 N3 _  f( p! X' t( [                //在剩余的元素中找到最小的（比较查找）
. M/ a. m5 P% ]6 |* U5 [                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
- ~" }, A# ~# G$ {! y  s% s            }
9 Y+ B6 t' |! S7 H- P7 j9 n+ y            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
$ s5 R' ]6 D  R7 x' o$ `( X: E    }

# W! Y9 U8 |( g! u: x    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
( {) O. \1 G$ R& f        arr = arr[j];
        arr[j] = t;
+ O( I" _# Z, y  {  O; b7 d8 W0 X    }
/ M' ]1 P" n# w
    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
2 I9 E0 \: R/ p+ K9 u        }
4 L+ H  l0 I4 N$ w- F        System.out.println();

! q$ m" x( q* `# r6 h        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
0 X- P( Y" m7 z2 I
+ \- U! m- |7 t! q9 Q& ]1 N        SelectionSort.sort(students);
        for (Student student:students){
            System.out.println(student+" ");
3 H" Y. q: Y4 B# Z  b        }
& Y# i) Y; s1 ~/ B
    }
}
5 ~2 \4 S+ M* f5 g+ W4 ?8 {; v
- w) z8 _9 @2 I3 B* Y复杂度分析
9 y; D9 p  _  C* G        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
; `3 U9 z/ h4 ~" ^2 \2 ?6 u* i
6 i7 ~. R: @! b+ {8 {; f* H

首先在ArrayGenerator类当中生成随机数组
. X7 ^5 O8 U% p7 h. O  Z
5 Z! U- {% {/ i: c4 z    /*
# ^; q& ]+ d7 [    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
: ?. `2 ]/ s' ]/ k  k- F; ~     */
/ T' [9 u  R1 m% f+ E    public static Integer[] generateRandomArray(int n,int bound){
; X- `  l. c' c& u# e$ w1 a        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
7 H( B3 d4 ~' }9 {7 t* v        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
( s* I- s0 F2 f. D6 q    }
判断这么大数组是否真的排序成功：

& l* X4 s' T7 b6 |) X* J0 upublic class SortingHelper {
# t& M5 j# V4 A7 ~    public SortingHelper() {
: G! W. {: A6 J    }
, N9 _1 d. O5 L) I0 `
    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
4 _1 N0 H+ j  t6 I        for (int i = 1;i<arr.length;i++){
- W" G/ t7 W$ v: n% y) ^            if (arr[i-1].compareTo(arr)>0)
                return false;
1 ?0 X* E6 P9 U0 `0 B8 `) @$ |        }
        return true;
8 Z, h+ n) z" c# g. c' x) N/ v& [    }
}
" N6 u) F  `/ z1 Z5 k) w在SortingHelper封装一个test方法用来测试任意一个排序方法：
2 n9 s" o# ?% T/ C7 V6 |9 W* v
    //封装一个test方法用来测试任意一个排序方法
/ N2 T# l; _% t5 I% y    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
! A2 y) F. Y6 |% H4 y            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
% i7 r) F0 I2 l6 h$ p. l            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
测试时间：

public class SelectionSort {
1 E  ?9 o# e# M! B& j
    public SelectionSort() {
    }

2 N3 q* f( {2 e+ s. a, S; n' y    //
    public static <E extends Comparable<E>> void sort(E[] arr){
# u6 z1 }5 f: ]4 O: N+ o- i# U4 W+ w        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
$ X7 c- v, y. c3 c& Y            for (int j = i;j < arr.length;j++){
3 t2 Q1 h& i7 l  i                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
* p2 O& h2 E& _7 b1 U% @9 A                     minIndex = j;
                 }
. r0 A3 T* {, K            }
+ d. u$ d- n: ~, l            //将arr与arr[minIndex]交换位置
. R- w6 i9 u" s9 u' X* t$ D! y            swap(arr,i,minIndex);
        }
    }

, r3 L+ S. T7 D8 J  y    private static <E> void swap(E[] arr, int i, int j) {
6 L8 p8 N3 Z& n        E t = arr;
        arr = arr[j];
        arr[j] = t;
* A0 X( `0 I( {' z5 P- X    }
: l) X8 b, P2 Z) c. D( x
- o5 Q% C8 m6 Z: V    public static void main(String[] args) {
        int n = 10000;
& n& Y, m" R9 R6 h. W( N        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
/ i; F; c- D0 p& p# {        SortingHelper.sortTest("SelectionSort", arr);
' Z0 \" V8 A6 `+ x" e
    }
}

其中如果要测试两组数组：
* C2 p: j" A3 O& f: q
    public static void main(String[] args) {
7 f+ z% V: h/ C1 T$ A        int[] dataSize = {10000,100000};
6 z' R# b6 \0 F7 K) b" a2 r: y1 U        for (int n:dataSize){
! s( h4 J! n9 d; S            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
5 m! k1 ?2 B" a: L            SortingHelper.sortTest("SelectionSort", arr);
        }
    }

% B6 `8 j/ E# ~3 {/ A6 u) n8 Z* Q
! C# Y5 q/ c1 P5 E$ v: c 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
0 k2 v2 V# _. J# m版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" ~1 u% n! v  [4 v1 y8 i原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
* ?& x! g. F4 w* U1 N
- O2 p4 i: @$ L6 Z4 F9 R
  B9 R* \% l/ y  i0 J# E

1051373629

感谢楼主的资料
: h7 I* o; X2 q7 c6 Y5 q' r0 \