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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
- R2 m. Z; h+ k2 Z& C  |3 ?目录

选择排序
5 Z& L- L2 B) J3 G& {# z
选择排序简单介绍

4 V. ?* I$ Y3 b9 b实现选择排序法

/ ~5 d" x4 |' A2 ]7 y" _使用带约束的泛型

使用 Comparable 接口

复杂度分析
& B4 i5 o# K/ x  i% s, S" J, R0 t0 w' z- x
7 |0 J6 A# K) U( N1 B选择排序
* W% J" h) b0 E0 n0 K选择排序简单介绍
" R9 t! K! c* C* h先把最小的拿出来

剩下的，再把最小的拿出来
& V; w3 y7 D* t8 B; D
剩下的，再把最小的拿出来
3 P" N  `& K) p* F; x
* _' _  }( L' F- t! Y6 Y3 C4 G* d" ?; e......
7 F4 ^5 V' K: D: V1 G6 f
- M7 ?# ^6 \4 T0 f每次选择还没处理的元素里最小的元素

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

        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

& ?1 R& x3 d  W# N5 |; K% g实现选择排序法
, {9 x% G6 C! C0 O% o1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

9 {" Z  n. ^' b+ C  V. l- E        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
- ]  v! o0 T( d$ ~% Q( o7 B" K" \
public class SelectionSort {
5 j4 o# @5 v+ R+ D! f
    public SelectionSort() {
    }
, U0 f% l- `( v" l  O
    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
0 I- n6 z8 ^6 ?* w- s) D            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
" X; V& ]* M2 A0 A, Q# m7 m1 k            for (int j = i;j < arr.length;j++){
& P5 d9 P8 Q( ]& P                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
                 }
            }
7 g5 ~. g/ s3 |5 _) u            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
' U, Y1 d  i- d% n4 m        }
8 \# C; l# G8 d    }
5 L& _/ r5 J* C& M% m1 g
7 Z3 Y9 d+ p5 ~" M* Q9 A    private static void swap(int[] arr, int i, int j) {
        int t = arr;
3 E$ ^, J* ^0 V: ]        arr = arr[j];
8 s' w* ~5 |8 Q7 z        arr[j] = t;
9 {5 O1 g* J/ w# ?    }
+ H0 H; q) d. n4 e4 S5 N0 C
  D/ P/ k; k8 R- {    public static void main(String[] args) {
+ I+ g, X/ _. v. q1 n1 a        int[] arr = {1,4,2,3,6,5};
. I* v) h7 \$ n+ n" v        SelectionSort.sort(arr);
0 q2 w, e8 {8 U* e        for (int item:arr){
            System.out.print(item+" ");
: D2 i2 k# k' h/ L        }
    }
; _$ X% J% g  d1 E$ x2 G7 a}

8 Y" ^& k: ^9 V+ G当前只能实现int类型的数组进行排序，因此需要使用到泛型。

1 S( p! F6 z( o6 @使用带约束的泛型
1 o9 R; h2 m! y        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
3 D8 `: @; ?2 G- w% f. ?" R
public static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
/ \" W: i1 N3 W
; m2 d  x6 s% K) q" kpublic class SelectionSort {
$ K! g4 |' d% R7 X) W& Y
0 H: o! h4 K9 ~2 W# o; P& y    public SelectionSort() {
! ?9 e0 c, H( M) g, f    }
7 |+ U" q4 {% x' i& I# a( \7 q$ M
    //
3 `" q3 a* K$ I$ ^2 M# |0 D# t! 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++) {
  K, n2 K! y; m  g            //选择arr[i...n)中的最小值的索引
: [. M3 c& Z5 f6 l! q* N9 [, Y% ]            int minIndex = i;
/ r6 T* Z1 x% i: y5 G            for (int j = i;j < arr.length;j++){
) p, ~3 T  z) R- C                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
  M% o- g. w2 X! Q6 `            }
1 W  n! ]/ ^8 Q2 \( W0 c5 |) v2 {            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
3 O/ @2 K. g" ?% E, {        }
4 ?# w3 r4 L  x' M# z' V# m2 A    }
) g* \# M$ }& M; ]2 O, x
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
8 N# t: r! c8 y% }& t+ P" P        arr = arr[j];
* a: H3 t0 q4 ]$ o0 Z1 ^3 k        arr[j] = t;
    }

    public static void main(String[] args) {
  I$ ]) S2 r, j) t6 G0 s" i        Integer[] arr = {1,4,2,3,6,5};
( T* Q9 J$ r4 T- n' K' d        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
9 N+ B4 b  f2 q  o3 o% i0 Z        }
% x1 C; m  f. k& i: T3 a    }
- F# k6 m6 h. ]}

        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
1 Z" k: R* e( l' F7 b8 Y
! U6 ^9 ~) y  h, j  i使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
9 s, m9 K& S& L  N4 D
: f) K) g7 a8 I! H- ^7 Kimport java.util.Objects;

public class Student implements Comparable<Student>{
    private String name;
    private int score;
; P! t/ f( t& {% E. j  R; {$ U

6 j% ^! b  d9 e: @3 U    public Student(String name, int score) {
. l3 \8 Z& w! M* v  D- L        this.name = name;
        this.score = score;
    }
! p) z1 d' W0 Z7 E( Z
0 Q0 p" W. f6 J3 F& b    @Override
    public int compareTo(Student another) {
- A; ^3 y+ m) i        /*
) v4 I1 y/ r) `9 B3 v8 c        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
' _" f5 I# Z+ ]" i$ ~( P( Z        if (this.score<another.score)
: z8 l6 }9 W* t            return -1;
        else if (this.score>another.score)
            return 1;
3 _$ v5 O2 i% j+ V5 W! \        return 0;
+ h8 u  _! R3 Q1 a* Y2 j        //return this.score - another.score
    }
7 P4 N) L; B5 i! m0 g- `
    @Override
    public boolean equals(Object student) {
        /*
+ y- `. e- G9 D/ m- c" b5 d$ c        强制转换有可能出现异常，因此需要做出判断
* h9 Q. v, e# M4 r9 u3 ~        */
; n9 n0 v3 N7 d/ f3 o+ y1 N# E        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;

        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;

        /*
  t" ]! F" b  m        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
: p6 j2 k7 S- B" r' ?/ U        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
* r0 U. |+ X- |. {$ Y* N& Y         */
' \+ s, x' f% |9 W, ^- C# G4 z        if (this.getClass() != student.getClass())
* m" A6 z. i# l9 f! R            return false;

        Student another = (Student) student;
3 m9 v, s+ d# a" q; }6 @  X        return this.name.equals(another.name);//写比较逻辑
. \, t5 Q7 T' h7 |. k' y    }

& Q* f+ V) P, Q9 m    @Override
; }' B! i- r# H    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
. y: ?! i" j  B5 t8 o/ N! L- Q1 N                ", score=" + score +
7 D3 V. r/ \( J( N& S, l                '}';
1 l4 j5 z; m+ x) M' E4 j# y    }
+ l+ k  Q  H" O9 x; [}

主方法实现类：
* E; p$ ]) I# W
public class SelectionSort {

    public SelectionSort() {
: H/ y; {9 o6 `) V; x  `. q+ X    }

    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
( d6 w3 c$ B# j1 e        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
* |7 I/ L/ L1 G/ \9 V            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
7 y! {4 e: P0 {, k* _                     minIndex = j;
7 [+ _& K8 c7 s                 }
( n% Z; ?, `) s: [, I% T; g, `            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
& J% ^) v. H' S. |1 Y. B0 X! z        }
    }
! e7 K5 E" J+ C% m& y* x
4 Z$ X; }' b" k  h    private static <E> void swap(E[] arr, int i, int j) {
" D# s! E2 e* f* U% c        E t = arr;
        arr = arr[j];
; q  o5 u) V# X4 s( y3 q) U* a        arr[j] = t;
    }

% ~+ p; r' Y" M# }    public static void main(String[] args) {
% N* i7 S5 ]% f* n' _- t4 f        Integer[] arr = {1,4,2,3,6,5};
5 c% e1 |" a. I7 G1 T  B* Q        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
  h3 K1 L% }' e: h- S; A* Z  y7 d        }
4 w9 {5 `/ f6 ~" t        System.out.println();
5 ^+ t3 U' H/ ?5 M% k% A
8 S! A/ n" C/ b1 k" v/ c        Student[] students = {new Student("Alice",98),
7 p8 n( L: {/ `* i. O" Y$ j                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
0 d1 v1 a; S! x, H8 l# \; J& H
# b1 A) m( U8 Q2 H* G" ~. b! T        SelectionSort.sort(students);
        for (Student student:students){
            System.out.println(student+" ");
        }

    }
/ N7 ]( G4 n1 S& R}
$ }+ M4 D- A8 W' [5 i9 N4 W0 h
( d; ~9 \0 |9 P( S/ {) [复杂度分析
# z2 b# J; h& i/ B! h3 w7 T& @6 L' R3 h; o        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。

/ M5 k+ B( M  k2 V
/ k7 t- R: m8 d1 r; R8 B) n$ I8 H
首先在ArrayGenerator类当中生成随机数组
" b& W' d2 ^  k" n& m
+ G, }' ]2 r" s5 ^6 N4 ^; A    /*
! c+ `$ k( Z4 f, Z5 F    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
3 Y: B4 l4 y. t. D# t    public static Integer[] generateRandomArray(int n,int bound){
% }$ p( e2 H4 A5 E5 {        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
* d/ U( }4 }" Y5 T5 y        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
2 o; D: D. {0 ?9 v- }2 M    }
7 |: Z" Z0 q$ K. b" s判断这么大数组是否真的排序成功：

public class SortingHelper {
    public SortingHelper() {
    }

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
& |* g* V  G0 j* P2 R! Z. ~        //判断数组前一个元素是否小于后一个元素
6 R& m1 ]- O# P4 \* B1 u        for (int i = 1;i<arr.length;i++){
4 A) v$ d9 H  ^7 {            if (arr[i-1].compareTo(arr)>0)
! u# j& o9 n; u6 b                return false;
5 O8 }+ N, S0 z" r& B        }
- D+ ]0 G* A% ~6 o        return true;
    }
}
在SortingHelper封装一个test方法用来测试任意一个排序方法：
( r+ g/ r. P" x$ \  ]7 U
    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
) w! J* d$ J4 h; _2 P            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
; S9 q' A3 a0 R0 S1 P( }            long endTime = System.nanoTime();
1 r' S% F- _; O5 v7 U            double time = (endTime - startTime) / 1000000000.0;
( g" _+ X; V( Z. r- G; A            if(!SortingHelper.isSorted(arr))
2 J1 R/ h9 j6 y+ Y4 ^1 V0 N: V7 |& _, M                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
5 l. Z- Q4 ?: t  ^! ^, Z    }
测试时间：

  _% X1 s; k- ~public class SelectionSort {

5 u! U1 p& I1 K, g1 Y) o/ V7 X' P1 F% P    public SelectionSort() {
    }
  g- f* N0 p2 ^& X
6 ?9 b( t9 X. J1 P6 H    //
    public static <E extends Comparable<E>> void sort(E[] arr){
* h5 E4 Z9 B) a* u: F) c8 r        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
4 k+ j8 E* {' k1 `4 n# o8 K+ c! ~- f3 U            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
% \2 u9 H1 `% T: j5 Z- X            for (int j = i;j < arr.length;j++){
( ?! ?! ^3 P, G4 m                //在剩余的元素中找到最小的（比较查找）
# J" Y) O+ m8 K  T7 P/ |# V+ O                 if (arr[j].compareTo(arr[minIndex]) < 0){
. c  F" B- R# H% S                     minIndex = j;
8 a- r$ W8 ?2 [9 o                 }
% o: W6 ~) V% \! s( e/ [! O! e            }
; @+ r1 w3 }% @8 I+ |( P) o. A' G            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }
/ D+ U$ p  S6 Z; A, R5 B
' C6 B/ v7 {0 ]( T+ N+ M2 `    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
, i1 M) d3 x* t5 a        arr = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
% _* O% d: _, }$ V' p        int n = 10000;
1 f7 D) I2 T. R% y( L        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
}

其中如果要测试两组数组：
0 \, m% K$ T5 s
    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
        }
    }
/ n0 O. {0 F2 x) ]

, D, \1 r/ G$ Z) X: r& f 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
3 y1 K9 ]: P  D+ Z, d版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122


, g8 O$ W" F! q) L8 R1 k) ^

1051373629

感谢楼主的资料