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

杨利霞

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

9 |& \: c. t2 H6 h! ?选择排序
" N1 f' x. S9 a& u1 B$ s4 {
选择排序简单介绍
& A1 E; ^$ Q* c/ R$ B: L9 G
实现选择排序法

使用带约束的泛型
4 I; D6 ^  R' g( A+ O
使用 Comparable 接口

/ J- X* ?1 ?$ |, g' F: j复杂度分析

  A4 Y* Y9 B  r6 A+ U选择排序
: J# t  Y2 \4 [" _选择排序简单介绍
6 ]; o* a( \# @) z先把最小的拿出来

- o; {. p# a  y1 T& P剩下的，再把最小的拿出来
& `/ A- h2 |: j! M# s/ L
; l" v, R* b1 u  @* r9 B剩下的，再把最小的拿出来

......
5 d2 ?7 U% [, M# p
每次选择还没处理的元素里最小的元素
  i% i! ^! B5 e3 Q
7 v$ z) h) |8 y8 A8 h( ~7 S5 a        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
( k- ?& F, G; T, d9 `* ^2 h; K% n
        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
2 N& d# j6 T4 S# L
实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

; ~( ?2 Q7 R6 c. @/ m        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
' d1 g6 \3 ^, q- q: D4 R. v& t$ {3 X
public class SelectionSort {
. J* R! R6 i/ x
! v' ?, Z% W4 W) }    public SelectionSort() {
  _# }8 j( F) w- ]. O    }

    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
  M+ Y  ~9 a, r        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]){
                     minIndex = j;
                 }
' K, i9 {, n* C5 W0 @& ]9 i3 Y            }
# K: O3 d& p& t, m) g7 P8 v1 L            //将arr与arr[minIndex]交换位置
: V0 }0 j1 s+ P& r2 L            swap(arr,i,minIndex);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr;
, D& S1 q1 s  c7 M& L" W8 A( f9 h$ s        arr = arr[j];
7 s7 B9 |7 d* I7 o" j. {9 L1 X        arr[j] = t;
7 w3 V1 z/ l7 L    }
2 M' ?) X. T8 D
    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
5 d# ^+ z# s* ]. A* f        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
5 [8 q( ^4 [3 s- N; Z3 e        }
9 H* M1 E) y' r% p6 E    }
}
- C9 t! {2 Z1 F% d! q: X8 q/ j
7 H7 M+ ?0 k$ u. u8 ^当前只能实现int类型的数组进行排序，因此需要使用到泛型。
; K( \) L$ y6 K" ?
. R! A! a1 d4 L) k0 T; y+ k' }( c使用带约束的泛型
: A' W4 `! a2 P, l! w; P9 @* i, w        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
+ z; C6 O) |' H& b% t
public static <E> void sort(E[] arr)
) {6 W7 J; d8 p6 Q# ^, b7 e        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

public class SelectionSort {
. Z! U1 ?4 F7 l! a6 l
" I6 L& K2 y# T. L; ?    public SelectionSort() {
( R6 [& h0 O# F/ ]- g9 M    }
( `& q) S+ N5 j7 J$ F: |5 l% V
* w" C* z$ ]6 b; x    //
, ~/ q% C% w' k. T3 E3 v    public static <E extends Comparable<E>> void sort(E[] arr){
5 |, ?/ S+ ]) A0 T        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
( |0 G3 u0 R: l8 d; r            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
8 ?! L9 ^# S: f% j4 {. C( L/ S                //在剩余的元素中找到最小的（比较查找）
$ Q) H/ R$ A/ v' I: W4 t                 if (arr[j].compareTo(arr[minIndex]) < 0){
5 @5 ?+ [2 r6 b$ v$ }$ X/ p* m' C/ @                     minIndex = j;
& h% S( B0 u7 Z6 D                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
/ }! _5 F1 e1 F3 l        }
) `' f  F: O. W: t. @  a0 R  W+ y    }
* s- j3 r$ D: z% y6 F* |
    private static <E> void swap(E[] arr, int i, int j) {
4 `2 g' ]  t" }% g( V( m* ?        E t = arr;
        arr = arr[j];
2 v, P9 y1 i6 _6 C8 d# e: p6 M        arr[j] = t;
2 R" L  N0 I2 W2 e    }

0 J1 s! o8 h5 l8 Q5 D    public static void main(String[] args) {
# c2 G2 J6 S3 d9 a/ @$ u+ n" Z9 F        Integer[] arr = {1,4,2,3,6,5};
) k9 s) j- ]% h7 j        SelectionSort.sort(arr);
- ?6 |9 @& R: P) V/ D+ c        for (int item:arr){
            System.out.print(item+" ");
6 m% u6 @% T! c1 P% u- L0 d& A* P        }
3 x( Y& G/ l9 O, F( ^/ p    }
6 Z9 ?. |( b2 |- g7 C}
! z! d. W! y- g+ Z: m
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
6 ]& v" i) i. [( g
使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

import java.util.Objects;

( d4 x1 q% @; f$ Y. X$ }public class Student implements Comparable<Student>{
    private String name;
$ G3 V' V7 N( Z  T6 K4 }    private int score;


    public Student(String name, int score) {
        this.name = name;
4 s- |; B5 r# q9 |% G( F        this.score = score;
( j% u8 k1 S- K3 s$ [! i/ f    }
& \; y0 s) p  E0 N* e& P1 X
- b0 Q( V! A1 v; u/ y    @Override
    public int compareTo(Student another) {
        /*
- w- D5 n6 P$ w) k7 T# B        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
, u. R' M- @0 y3 F. f7 N2 P         */
; q/ m# V$ [4 }3 z; D3 m        if (this.score<another.score)
            return -1;
9 H& g! _% n2 r; S: Y( Z        else if (this.score>another.score)
            return 1;
        return 0;
8 h" e  m/ O( [. V6 N6 H        //return this.score - another.score
    }
5 Q/ F6 J- S# r. d* U6 w
    @Override
    public boolean equals(Object student) {
" n, y5 `9 }& M% g$ \3 ^        /*
        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;
5 y) {9 @* ~) ~  K& B
        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;
5 V6 W" P* P3 g6 o1 N( M  y$ D
# d/ I4 K2 O7 T- y9 G        /*
$ h/ n0 p$ a: t2 T8 z; _        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
6 c$ r* p* T; g3 ?5 W5 j& T        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
& i# f4 W0 t% L/ O1 S        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
+ p9 ^% O8 a+ z3 _         */
        if (this.getClass() != student.getClass())
            return false;

        Student another = (Student) student;
; `# E* s  P# o" \        return this.name.equals(another.name);//写比较逻辑
    }

! C- ?' S* ?) Q+ S& p3 b3 v* I    @Override
. p1 A( e. _/ s9 y    public String toString() {
1 y4 e0 F" T- |  H1 `        return "Student{" +
                "name='" + name + '\'' +
5 {+ T5 ^. o, v: w) |, A2 X                ", score=" + score +
                '}';
    }
}

7 T4 C: M4 K- L, E7 K主方法实现类：

' D5 i, t# U* P6 gpublic class SelectionSort {

    public SelectionSort() {
) T7 N- c1 ^! H' A    }

    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
+ }4 a1 J" C4 m5 y! R9 O2 {        for (int i = 0; i < arr.length; i++) {
( \* ^! D# g+ |+ w            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
' M( Q+ T' U0 P% A9 c                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
8 p; f$ h6 v, K$ a0 K            }
            //将arr与arr[minIndex]交换位置
. U8 F8 Y7 j, m* Y            swap(arr,i,minIndex);
        }
7 P& g" y7 i- G1 w    }
. D& a+ b6 [  Q( h! f7 P  s7 I3 {
9 ~8 z  c- Z2 f& \( p    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
; B. M* f* J, @# e5 O        arr[j] = t;
    }

    public static void main(String[] args) {
6 d5 C0 T8 X% t# ~        Integer[] arr = {1,4,2,3,6,5};
0 ~! h$ ~: K. {/ E3 z5 k/ T        SelectionSort.sort(arr);
. b2 c5 w) b  w. y' Y, M- ~3 ~* V        for (int item:arr){
) D6 p/ _+ I4 C# L% M$ w  Z" j& B            System.out.print(item+" ");
        }
( B: Q* ^6 I; E% k        System.out.println();
) D* R6 n% Q% m2 C& P* l
        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
5 o0 r# z" L, F8 Y( f# s- G                              new Student("xiaoming",66)};

: f  q+ [. G6 y; M) n4 V, B        SelectionSort.sort(students);
        for (Student student:students){
$ V9 l5 r1 \* q  i/ q            System.out.println(student+" ");
        }
; d; n) y* L. C
9 L" O% U1 \0 ?, A/ J7 J    }
* i0 L4 W! w8 d5 p}
* U# N# a; d5 |8 \; p
3 a9 E# @2 y6 G/ W复杂度分析
, w# b' f- f. r1 E7 a% M        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
( k( ?7 M5 y  z! I. v


* O6 l$ I  B. Q. _首先在ArrayGenerator类当中生成随机数组

    /*
/ s+ s/ c4 |; |7 R/ D. f    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
# Q; U$ K% A1 ^# T     */
    public static Integer[] generateRandomArray(int n,int bound){
: U) Z- D# v/ ?% t9 x        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
/ s) T% m& m! V: _" ^6 P9 p            arr = rnd.nextInt(bound);
        return arr;
0 J* i1 L% u$ n8 Z    }
判断这么大数组是否真的排序成功：

public class SortingHelper {
5 Z1 f* M1 c1 t. i    public SortingHelper() {
1 @" H; z) r5 `+ u( [    }

- L' x% d, L- J8 @! Y! p4 F% _" }  m! c    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
                return false;
        }
        return true;
4 n7 Y8 U( O4 Q  {  A. V    }
# c7 L# l7 b8 G}
  ]5 x( Q8 h9 D/ f7 i$ d在SortingHelper封装一个test方法用来测试任意一个排序方法：

0 ?* \7 e1 H# ?% T6 R2 R    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
" ^/ q' I: G( M$ g- }            if(sortname.equals("SelectionSort"))
1 V+ W) U" k, v: y3 t                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
5 k( g& j2 V+ x% `            double time = (endTime - startTime) / 1000000000.0;
8 n/ A, M& D- y0 l% r2 v            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
5 [* i- W5 ]8 W: f/ r; @测试时间：

* l9 v! U* C5 G) K; qpublic class SelectionSort {
/ B% W4 C9 x; I+ V. D7 Z& n
    public SelectionSort() {
    }
6 w! H) t% s  |6 N. w; j# M; l
    //
1 `" }, o5 w6 }# R% H* s) X    public static <E extends Comparable<E>> void sort(E[] arr){
6 \7 S5 Z. n9 O. W0 W: K! S% D2 {        //arr[0...i)是有序的; arr[i...n) 是无序的s
# ?- E( o: N, A- v& i$ m" Z6 X        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
2 z, a3 N7 e, j# n            int minIndex = i;
: N3 G0 \' ?- l2 F4 q" U* Z            for (int j = i;j < arr.length;j++){
! s9 s- l" e0 v/ ^                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
% X' S! }3 b. I- I6 f: t+ R                     minIndex = j;
                 }
            }
8 N8 I2 M$ z! N" H' T& m/ k0 I( _            //将arr与arr[minIndex]交换位置
& A  I4 G/ t+ }: K) c3 Q' r$ T. W: B            swap(arr,i,minIndex);
; {8 a8 ?. Q: P! A        }
/ F% D- N$ o0 b( \& v2 o- m4 K4 @    }
$ U( Y( _1 A. }3 ~# ]" l
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }
# N7 i1 U4 h4 j9 }1 r% g& f; Z
    public static void main(String[] args) {
4 l" E/ k# ?3 e7 W        int n = 10000;
6 L& E% K* o- f) n8 R) L: J# I        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
( d; S8 ]4 [! l( \4 Q9 e) r        SortingHelper.sortTest("SelectionSort", arr);
# @6 ?7 o( g" S4 c6 ]/ R' `9 I
    }
}

$ B5 |9 l$ o2 s, ^1 b5 p( W其中如果要测试两组数组：
4 {4 N- V& N0 h7 a
' G9 A; U+ V1 o  d2 m    public static void main(String[] args) {
1 l, O5 o6 E1 g        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
, H& O1 M  t: m- ?$ C' h            SortingHelper.sortTest("SelectionSort", arr);
        }
    }
/ T3 |1 S  _" x5 |9 y

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

0 K1 A. a; H' j
( U+ Q( M. n7 ?% M

1051373629

感谢楼主的资料
* f2 w1 A* d& I