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

杨利霞

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

选择排序
- E3 m1 k9 c6 }1 B5 K9 e. F$ v
$ B! j$ `4 A9 x9 A选择排序简单介绍

1 X) Q# s- w  C! d6 O# j* H实现选择排序法

使用带约束的泛型

) _# g) E* ^& A" k使用 Comparable 接口

复杂度分析

4 h* C7 v, \* H3 A选择排序
, V( ^. O- c! w: L5 y8 s1 D6 w. b选择排序简单介绍
先把最小的拿出来

) I5 ~! F" D! E( T3 l! _( ^剩下的，再把最小的拿出来

- m* Z9 S3 z- o. l. Q剩下的，再把最小的拿出来
" R- g4 u: J9 u5 l3 F$ L
......
4 A: ?  J: H' Q: n& w
每次选择还没处理的元素里最小的元素

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

3 f. C3 |% c1 V( S4 S# v        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
5 \: I9 b0 F) o" k6 Z  V7 ]
, ?3 H4 k4 c3 O. d$ ?  I实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
) J# b2 X% i9 Q2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
) d1 ~$ q) X6 l& B3 \( s# I8 l& N3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
8 t/ z7 O9 l" V. t
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

  v+ A5 g) p- tpublic class SelectionSort {
  y8 k6 ?2 f+ I! ]' R/ z
    public SelectionSort() {
- D# q, J& u8 U    }
. p. [" c1 V8 e
3 Q/ T; d3 }9 ]7 L8 I0 ?9 o0 `    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
/ r9 R) t& c! @/ f; w% F" h            int minIndex = i;
" Y  w% D4 c; H* ]4 r            for (int j = i;j < arr.length;j++){
$ c, M, ~- t0 O; r5 ?: M9 O' j8 N$ i% {                //在剩余的元素中找到最小的（比较查找）
5 H, P8 j. a) h5 x/ d: M                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
                 }
7 W$ J3 _6 s0 R0 h+ c            }
7 S" C6 ?* ]4 v# C% x3 p            //将arr与arr[minIndex]交换位置
4 n6 ~6 p5 h5 s- P! C            swap(arr,i,minIndex);
' e$ v/ g8 Q, K$ ^8 x$ v/ x1 [        }
    }

( Z, L: m0 X: q+ D    private static void swap(int[] arr, int i, int j) {
3 V; Y9 O5 M: o  l, E3 p# s        int t = arr;
        arr = arr[j];
        arr[j] = t;
* x. ?- ?9 ?2 W8 y6 J    }

; z3 l; q/ t! Z& r    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
6 o9 N2 S9 d8 s6 `2 E$ V" \& x        SelectionSort.sort(arr);
        for (int item:arr){
/ U5 _$ S3 X* n; X* r            System.out.print(item+" ");
        }
7 J9 ^) }6 e" S1 j4 I- _    }
}
5 c8 ?& i; R* @8 W- v1 ^! G8 R
5 m0 y2 N9 m- G. J当前只能实现int类型的数组进行排序，因此需要使用到泛型。

使用带约束的泛型
) S* R) l8 t4 c2 M- ^  |3 A        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
! a5 c" L" k+ w( W
public static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
* Y; ]% W" ?+ w- F3 N- ^
public class SelectionSort {

    public SelectionSort() {
    }
- [6 Z, ~! h$ J. W, M
    //
( H: o& J1 N2 P    public static <E extends Comparable<E>> void sort(E[] arr){
7 }9 \! |' P5 _) F) _: j6 H4 ~& {% P        //arr[0...i)是有序的; arr[i...n) 是无序的s
" L$ M5 R9 D( \% w        for (int i = 0; i < arr.length; i++) {
. {+ N- D* I2 t$ F# r- E' Q            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
6 G/ r' \# X# E& U# r. b5 e' F3 Z            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
( j: z0 ?# b( D3 t- `                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
% H9 r3 H/ y. U0 G1 @) w; u                 }
8 V) N* ?, _- C1 c/ I2 s  F5 v            }
            //将arr与arr[minIndex]交换位置
6 W1 p* [% ^4 {2 v            swap(arr,i,minIndex);
6 U$ }9 V; S* \+ |, u" c2 L0 ]        }
    }
7 y- Y5 o# n: V, H8 h* |+ w- P9 M3 C" F2 H
* Z+ w6 h: @8 R    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
. _0 R( {7 }' C& ?/ K0 r        arr = arr[j];
( ^# b/ Y) j# _9 h5 u' n8 s4 v        arr[j] = t;
$ m& |4 [" \3 q    }

- S# N# L6 c: U9 c* {2 J, s    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
" }- |( |' _* V  r; _% Z; n        SelectionSort.sort(arr);
        for (int item:arr){
3 g+ I/ Y0 `* u- _            System.out.print(item+" ");
        }
    }
* {. `9 N5 p% C; u. ~1 _}
6 S' p; a/ Y3 k3 {( ~2 q; K( b, ]
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

4 h# ?. L& i. O5 A使用 Comparable 接口
8 a5 W# L! X) d5 N. A        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
' h/ T+ x4 `' t$ X% ~& e7 j
& Q+ |. H0 b# Q; l& }0 A% h7 oimport java.util.Objects;

* y7 p8 Q8 R/ ?% Q- _! kpublic class Student implements Comparable<Student>{
* ]5 G; ?) G7 E    private String name;
    private int score;
- G! ~( H7 B. o$ g+ b. I* A0 T% v

    public Student(String name, int score) {
/ T! \. \3 k4 m: d# ?! R        this.name = name;
        this.score = score;
) D4 Y9 J  `4 g5 J1 |    }

8 B5 ~$ z8 }' i8 @; B: `- ]    @Override
1 ~! `! w7 f2 Z3 X5 g# J    public int compareTo(Student another) {
        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
( F# L9 S, M2 ?$ x1 w& x         */
9 Z% z# p' Q* X        if (this.score<another.score)
            return -1;
        else if (this.score>another.score)
            return 1;
        return 0;
        //return this.score - another.score
) V4 L' c  R* f1 `- \4 @4 G6 G    }
7 z0 b- Y1 L; o: h
    @Override
  Q5 m9 ^' E5 n' [    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
        */
0 M& t8 U% j6 _8 g$ }. x. N) R3 d1 l        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;

        if (student == null)//如果传入的对象为空的话，则直接为false即可
# k+ G+ i. r% r) m) v1 h' n. n# Q! Y            return false;
" g% L# ?& i8 y$ q5 c/ Z$ [
        /*
, R3 }. Y7 u& v' ]; \2 g# {7 y1 k        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
* |% R4 j. v: e0 h4 v! S# V' K         */
        if (this.getClass() != student.getClass())
            return false;

        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }

    @Override
    public String toString() {
/ R$ H' x% q8 S$ m        return "Student{" +
8 k6 {. I- ?3 l' v! {                "name='" + name + '\'' +
                ", score=" + score +
                '}';
/ ~/ g9 Y( ^5 _; a    }
$ @: T4 o' n6 ~* ~3 \( j}
/ V$ T+ k1 H5 Z/ `; Y8 B/ I
主方法实现类：

public class SelectionSort {
* m% S& m5 F" S# i
    public SelectionSort() {
    }

    //
: k( \% r3 n6 t4 ?5 t% Y% k    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++) {
* e( M! V' q6 k7 r  p5 l, h            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
# V8 |4 E' |) e0 [8 t            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
. D/ Y, S, d5 `1 S& t                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
8 ]) S( ~- I0 c6 F            }
            //将arr与arr[minIndex]交换位置
; c5 @7 D& W' X6 o( ^6 d            swap(arr,i,minIndex);
! j7 g3 P- |8 Q# p+ D        }
    }

! p" ]5 E0 \, }" C9 Y    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
5 T* }7 M4 `+ J, }; a    }
+ a9 g2 H' O0 T. K# S% @& @1 V' n. E
; n2 m# Q  r9 z- B  K) b8 p    public static void main(String[] args) {
5 i& w5 l& o( P& Y        Integer[] arr = {1,4,2,3,6,5};
8 x7 s6 O" P, I2 ~" Z2 X7 j8 M0 Q        SelectionSort.sort(arr);
& H( f1 P0 y% B# W* t        for (int item:arr){
  Q" Z" c; _+ W4 q+ `% J            System.out.print(item+" ");
: f$ H' A7 h9 |& ?$ L        }
        System.out.println();

        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
$ b, N7 J/ {+ F. s3 b( q" w                              new Student("xiaoming",66)};
3 X+ v! ?$ o7 A7 y" p- S
- x" ^: C) f# t9 ]0 U# H% \        SelectionSort.sort(students);
) `7 ~: [0 x( a3 o1 b        for (Student student:students){
            System.out.println(student+" ");
! u1 g+ T' Q) U  X        }
9 C. w* I* m0 z) C8 F$ f
+ ]. _, p+ E; S9 p    }
* J( U4 y7 c* W}

- A. G8 u7 K9 \3 u: c$ {复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。


0 }6 m7 F7 u; {
首先在ArrayGenerator类当中生成随机数组
' a$ I  y/ [6 W* Z9 o
    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
% T  t. u, @- g     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
9 G8 h; q3 n5 T1 ~  H        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
    }
) V. ^/ t: C1 }1 l7 Z% O( Y判断这么大数组是否真的排序成功：
" e, b5 y- ?, {# ^0 c+ G
3 g( N" [, ^4 f' q$ X- wpublic class SortingHelper {
    public SortingHelper() {
+ e& L: R& `8 r7 o8 Z5 T5 R7 h    }
5 P: c/ t0 Z: G. t# u$ ^
$ s! K" Q3 S+ G& h) q: Q. s    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;
) D! @: A$ o/ [5 O, t        }
: s9 j" `4 o. N5 i        return true;
9 f5 t0 f2 ?& q1 L) h0 u9 a    }
}
7 w/ Y: t( H& k9 i6 I% d6 ~. z在SortingHelper封装一个test方法用来测试任意一个排序方法：
3 n  ^6 l( l) f6 k; y4 y! @5 Q
' s  k! ?" O( a# X    //封装一个test方法用来测试任意一个排序方法
' u; A! U1 ~" D9 @7 r5 w( O    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
, X4 s' F  H4 J! A  z. Y+ f* F                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
. C" k2 a+ U- s$ _; w- X3 H' A& _            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
测试时间：

public class SelectionSort {
/ D. Y$ r/ G. H) r& I
6 V$ Y: p6 @2 p6 B! m    public SelectionSort() {
    }
2 ~. J" X/ k- J% y
    //
! Y) d7 I6 j1 {# w. d# |    public static <E extends Comparable<E>> void sort(E[] arr){
8 W( n/ l* h# S9 G) j: I. b        //arr[0...i)是有序的; arr[i...n) 是无序的s
9 _0 H( S1 ]2 k* p        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
: R0 H9 D+ U" A/ V; \3 w            for (int j = i;j < arr.length;j++){
) h8 N: |) \3 n0 W                //在剩余的元素中找到最小的（比较查找）
' U5 ^1 C, {+ g  y! D8 c                 if (arr[j].compareTo(arr[minIndex]) < 0){
. e1 S. Y" O2 M                     minIndex = j;
, i) n, J: E+ \7 i. a                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
9 U; Y0 X+ z$ A& p/ E    }
0 A& e) E) m% f/ j
/ ~! v. s6 g- M    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
! k4 K/ {/ x, p3 \+ Y3 F5 j; R        arr[j] = t;
6 i# |4 {8 Y. p& ~+ O, C& U    }

7 _; i) r7 J6 \8 g! M- u* _    public static void main(String[] args) {
8 d6 t. W8 t6 G3 z        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
0 G- m4 L  R: [$ J! ~- G. h% `& z8 k        SortingHelper.sortTest("SelectionSort", arr);
' \  U5 z8 I: b" C! O5 C! z  B* N1 v
    }
! B& O4 k) ~4 p8 a3 o  N6 v}
$ M( B; w+ W3 h6 B
其中如果要测试两组数组：

    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
        }
. b! e: q' n6 ?2 J    }

( C  P* @' G+ f3 m/ X
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
# ]4 a4 i2 m: l  V————————————————
5 |6 t5 x; t3 U版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
( \  ]2 B2 U- u! D8 j+ m原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

; A- C, x! L. }" T; H$ i
- P  }+ \9 Y) B& S4 C( y

1051373629

感谢楼主的资料
; ^- e) f" Y$ Q