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

杨利霞

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

选择排序

& v: X* M/ p; p4 n/ k选择排序简单介绍

8 k( A' z% W) P7 H/ t实现选择排序法

使用带约束的泛型

使用 Comparable 接口

复杂度分析
# f0 G3 a& ~" g3 X( L& U4 T
8 I6 e4 \# l6 ^  e! z, L9 G选择排序
选择排序简单介绍
/ T, {/ O2 Z8 Y0 Y/ ^3 U( C9 ^先把最小的拿出来

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

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

......
2 H& j& [$ h# T" U) s/ ?
每次选择还没处理的元素里最小的元素

9 c1 U3 K, ~$ s7 f! B, U0 L( O8 Y4 H        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
+ A: \: j! p5 H( B
  {8 F3 }& K, P; u2 \        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
; }, `; Y/ {+ X7 Z
- y  Q" @$ k* m8 ]) U6 t实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
% w1 D1 Q: e2 x9 v3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

6 f$ j% P2 T: e        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

public class SelectionSort {
% q1 I2 z, s, o2 Q
    public SelectionSort() {
    }

    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
1 o5 l/ j) g& y+ x( g! F        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
' l$ C- a" K0 k/ b$ {            int minIndex = i;
4 F0 M2 K* k0 \. S- C; p            for (int j = i;j < arr.length;j++){
9 X' F; t+ w& R' i7 ^                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
3 w  a. z; @$ ^& d                     minIndex = j;
) R# s- l  G9 v$ {' b: I2 u) P                 }
: I! ^1 @; y0 y% R+ J5 {" I- {            }
            //将arr与arr[minIndex]交换位置
% Y6 C  [+ Z  W% ^$ n            swap(arr,i,minIndex);
4 j. R* Q0 O* D        }
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr;
        arr = arr[j];
        arr[j] = t;
! T% x1 O0 R3 s$ D- L  R% `" U    }
5 _+ ]  [/ ~! e% l& }
: |$ q3 P" N% p8 t; z" c& o0 A    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
) r' j" R7 u  k, W  \        for (int item:arr){
/ K$ R7 o* D0 h$ U            System.out.print(item+" ");
        }
    }
}

% @9 z# z" u8 w' x4 b当前只能实现int类型的数组进行排序，因此需要使用到泛型。

使用带约束的泛型
/ J1 s8 P2 ~1 ?0 l* A  p% H6 @% j# A1 N        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。

public static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
3 k$ B3 N' ~. O1 B( A
public class SelectionSort {

    public SelectionSort() {
    }
* U2 ]7 \- j# _5 B' O) C
    //
    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 W8 C" ]! n. {4 S            //选择arr[i...n)中的最小值的索引
$ C# M; S# X- n7 P6 U* U. P            int minIndex = i;
" R, I+ X; C; P            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
0 k& d0 _" a9 G                 }
5 i. s6 x" ?- ~            }
5 H5 t9 L4 h& l6 L% P; ^% r            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
) I/ W/ I3 ^" T% o+ M        }
% [! O  ^  e4 l3 }4 `    }
( ~. q$ U, B6 a( T8 P
* B* {5 y# q% K3 h    private static <E> void swap(E[] arr, int i, int j) {
; t) f" N6 ]$ f* j/ w5 `! K        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }
8 ^4 u7 i2 U- k. e, G3 P- X
    public static void main(String[] args) {
- B4 U5 m( h8 _6 }% ^. ?% v  Z        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
; k( L2 F/ D* Q4 G3 e  [1 {            System.out.print(item+" ");
& J" o/ `: ]: ]* w9 e        }
2 b" g$ A( U% K: v& I, _! n    }
}

        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
: \: K' K; a' k, j* f
& h; r# ~) F3 O5 i: G使用 Comparable 接口
+ p- g' x4 i7 X        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
3 T9 A2 @1 A5 W& D# F& q  X
import java.util.Objects;
2 j  ^, w* y9 l1 |) T
public class Student implements Comparable<Student>{
( Z- w- {  d) m, f$ ^& R# Y    private String name;
    private int score;


/ E1 G, p. `8 G& y( V4 u- p7 u! d) s    public Student(String name, int score) {
        this.name = name;
  m# t# S1 A: p4 e1 D& |9 ]: c        this.score = score;
    }
. o6 U# p$ i9 o& h
    @Override
    public int compareTo(Student another) {
! U8 u* k1 d9 b        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
( `: f( B. \( }7 B4 }3 _, J        if (this.score<another.score)
3 q' S' E6 s& M& c4 B6 o$ {  f3 U1 [            return -1;
9 w9 \8 \7 @! L8 F        else if (this.score>another.score)
; E/ @) Y  B, \" {5 ?            return 1;
* M6 m6 J4 _5 D! E3 @+ U- i$ Z; O% x        return 0;
  L& a% j( J. C" T% ~& X" e4 e        //return this.score - another.score
4 t, `8 f+ `4 S: N5 B& o* Q    }
- G  M, y  L8 t; _# Z+ S8 i
! r, J% d9 o8 T7 e* f    @Override
    public boolean equals(Object student) {
        /*
8 U' ]& Q2 k8 V9 j        强制转换有可能出现异常，因此需要做出判断
/ ]2 T# Z+ {/ ^9 ]0 b2 m& g3 }5 T        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
9 @- ^- I; X; q% O& ^            return true;
% p+ O' K5 V* e& w1 M3 k( a3 p
        if (student == null)//如果传入的对象为空的话，则直接为false即可
% Z/ z1 ~, e( b4 C* J- q+ \            return false;
3 F) A1 r7 V9 z" B+ z' M6 n
        /*
        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
) Z2 ^# U* l6 j* p% {         */
        if (this.getClass() != student.getClass())
            return false;

        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }
) A1 d) m# P/ G. i: Z
$ c* u* D+ X% ]. \- I    @Override
    public String toString() {
- z4 I8 _" @1 t" V- }6 I8 }" t, {        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
) ?% {$ U" N) [; F6 d+ c                '}';
    }
}

) v% ^5 k1 Q2 H' j主方法实现类：

public class SelectionSort {
! P" u4 O' ^0 y" [0 h' C  S
    public SelectionSort() {
8 p" T; S0 G* Y* p) i    }

    //
, E6 o2 X& T5 c+ E; O    public static <E extends Comparable<E>> void sort(E[] arr){
1 A1 s! C4 l" Y/ N$ j        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
) O2 e4 g3 R- h* d- R            for (int j = i;j < arr.length;j++){
/ q% J8 p$ x  p* f9 c! z                //在剩余的元素中找到最小的（比较查找）
2 A. x! H/ U+ x1 i                 if (arr[j].compareTo(arr[minIndex]) < 0){
( ?9 L3 W2 k7 Y) b+ P                     minIndex = j;
* q5 z* {4 W1 w& g6 c2 {                 }
            }
            //将arr与arr[minIndex]交换位置
1 g( u# E- }. V            swap(arr,i,minIndex);
5 n  E; A8 _/ m3 G1 m0 o- S        }
0 F! R, `' c! C- D    }
! T) M1 [+ Q6 Z5 |/ n
- H; b* h' ?; ?( \  P    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
6 ?1 o# U. r, E        arr = arr[j];
* B  e* b! d3 M7 L0 ^        arr[j] = t;
; @  j8 L% Y" k: c    }
1 }4 r; }5 N/ n$ p" Y5 H
    public static void main(String[] args) {
% Y, w" y7 ?: T% j, N        Integer[] arr = {1,4,2,3,6,5};
, }- Z2 N" X; J        SelectionSort.sort(arr);
        for (int item:arr){
9 o$ G. G0 F2 a2 r            System.out.print(item+" ");
) J0 f3 j: K$ n: A        }
        System.out.println();
: L( n6 o2 h& {- C7 i& F
8 q+ M) o8 l7 x( o. s        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
3 N) m4 ?5 F: z4 v                              new Student("xiaoming",66)};

        SelectionSort.sort(students);
        for (Student student:students){
/ L+ c  l. f" @9 C2 c' M+ u# D' n            System.out.println(student+" ");
        }
. x5 x: t- Y3 }: L# R6 s" t
7 B8 T# `0 z  b9 D* S    }
}

3 _( X: ?+ l- Y  D复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
) {  F0 }; k2 l& V( R
# m# ~0 Y1 ^( ?7 P1 m3 I! E& n9 w
" @+ u/ g- c/ p% B
2 Z- j# u4 a4 Y  W! Q# \& o首先在ArrayGenerator类当中生成随机数组
+ M- `$ s* ^4 L  X' b' y
    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
  O; B3 d; B8 S" D, t% ]9 F/ f$ v     */
  X, h. G0 S& [# B4 X! J: S    public static Integer[] generateRandomArray(int n,int bound){
3 `5 v; }+ b  }5 |8 B* G        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
' s; r7 J4 v$ v            arr = rnd.nextInt(bound);
& u/ }- P* Z4 u) J$ @+ V) M2 `        return arr;
    }
# R% h" ~1 P! ]' b判断这么大数组是否真的排序成功：
- }) ^! g' g' v& T7 h
/ Y% i7 J& x- T9 q& X0 Xpublic class SortingHelper {
8 \' r$ m1 A+ h0 g  h    public SortingHelper() {
1 `3 Y7 D7 S6 m2 _    }

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
1 F* Z$ u  A/ H6 x8 @            if (arr[i-1].compareTo(arr)>0)
" \. P9 v) |$ I9 l8 `                return false;
& h4 Z6 v& i' T! e, U        }
        return true;
    }
}
) T6 b$ @! K9 e! \- p! d在SortingHelper封装一个test方法用来测试任意一个排序方法：
% m! n1 W! G; g7 |7 k
    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
8 S- S7 D+ @  ?7 \! S$ t( i* H            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
9 J' R# S4 V: E                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
  M7 e" v* B! j# z+ n            double time = (endTime - startTime) / 1000000000.0;
/ y: M, a, r7 X            if(!SortingHelper.isSorted(arr))
" R% Z2 q& K; w( R. J                throw new RuntimeException(sortname + "failed");
6 z: W  Q8 ?/ I9 b' m            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
0 I1 _2 L7 l8 X6 N' r( X, G    }
/ V( R7 I) o& v) x# V- o测试时间：
& `6 Q* ^! S  M" z+ P3 M
public class SelectionSort {

$ t/ U; Q! q6 \  u9 s- V6 S    public SelectionSort() {
7 s# B8 j- C8 ^9 t/ c, t: O    }
6 B& r. L, V6 C% S) s4 e
    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
1 t, |& m8 W& s" b' ~# `& |        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
7 w( F6 T- n* C! i            int minIndex = i;
+ M* ~% b  V5 j( X            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
9 h2 Q6 e9 ^" w3 O                 if (arr[j].compareTo(arr[minIndex]) < 0){
7 h* i) w' E/ V: a                     minIndex = j;
( j% T( o$ X8 L1 l' T                 }
% f2 H0 {- P5 c7 N' g2 r- t& ^6 |            }
3 G) L+ R- ^6 r2 o* G" c            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
) {; m' h  ^: y8 x) P% |        }
    }
9 f' J$ A! _" A) g  l4 b
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
0 N$ R8 B3 }3 y5 i# j        arr = arr[j];
        arr[j] = t;
    }
6 g$ P% }6 j& ~5 u
6 A3 A* c" }1 G* X' H& x    public static void main(String[] args) {
+ c6 J' K6 k% R: U7 g0 P        int n = 10000;
% b1 g% R( M; Q+ C        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
1 s1 R& o3 t0 |+ J- k9 j! C        SortingHelper.sortTest("SelectionSort", arr);
$ \  s+ N) @" m) q! M2 ^
    }
) d- V) r1 _! A+ z8 F$ b% \* ~}
$ n2 V) k8 }9 k, S  A0 u
' \7 V& B8 q, ^' d其中如果要测试两组数组：
! ?  v& [3 X) u4 {  a4 V5 P
; ~! g1 s; L/ X' h% S4 P9 ^& P8 f    public static void main(String[] args) {
5 K4 U! ~& M9 b0 O        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
, c0 x0 m! L9 Y7 C5 k" ]            SortingHelper.sortTest("SelectionSort", arr);
8 i/ f; I. ]5 F& Q        }
    }
4 Z6 p% c, k7 V. @2 Q( O8 l
) `' _: |; B* t' I2 {
) s5 y/ Y/ N: f9 h) A8 ] 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
, c3 v$ Y; A3 @; ~; {! }; ^3 D版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 \; J, l4 {$ B4 R原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

2 i1 S) \- b- E1 m& p& h* J; B
( ^/ S8 L- \# Y  x* \, `3 p

1051373629

感谢楼主的资料