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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
9 R/ B, d0 _6 A6 U7 r
# v1 G7 @' z0 l2 p( y选择排序
9 L" H1 E' Z5 W) Q* S! {
( H( j2 f6 q$ k( q7 H* Y选择排序简单介绍

实现选择排序法

使用带约束的泛型

使用 Comparable 接口

复杂度分析
" G! Z# k! v$ j" b" v4 x7 t9 U: J
选择排序
, J4 J- R- i; `$ L选择排序简单介绍
先把最小的拿出来
8 i$ \/ y& j8 Q$ S; q: S
! \. [. `" U% [4 ?' f& r, S; y* m* y剩下的，再把最小的拿出来

剩下的，再把最小的拿出来
5 a2 O7 V) v$ n6 K& w
$ l* w, w+ b% Q  ~% I8 ^3 n& M! m......
1 h$ P2 [" H: _. _; v2 ^2 M1 v
每次选择还没处理的元素里最小的元素

$ z' P$ B2 i' D( l  |8 R        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
* u! R' M3 `+ u& C3 T
        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
0 k0 h3 o9 f, h* C% A5 G$ ]5 t3 `
实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
4 Q! b& U( Z: F0 A! Y2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
. X5 V# C. A8 c" r3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
: |# E% q' D3 F2 g! g
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
9 ]5 q, H! L) C9 Q4 k& C* p
public class SelectionSort {

0 x8 b0 k- w; n( H: X) r" B    public SelectionSort() {
    }

    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
9 v* d$ \" L5 ^: ?        for (int i = 0; i < arr.length; i++) {
! `9 Q. h! J# c0 R' M            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
1 n* J$ {4 y) |& w: `  g$ j" ^0 [0 x            for (int j = i;j < arr.length;j++){
3 Z6 g: w2 ]6 n8 `3 k                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
                 }
. x8 r. P1 a. J& N  a            }
# h2 t+ t7 X) Z+ ?0 k" R            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
8 R( ]- ~; a' T8 m8 Z! y9 c    }
, D+ Z1 O2 Z: T6 P+ w8 e% C
    private static void swap(int[] arr, int i, int j) {
        int t = arr;
5 M8 r: g  Z' ^( X# I2 ]        arr = arr[j];
$ g) M, I# |! u6 S! X4 A        arr[j] = t;
9 Y" E6 G( \7 v# o7 T3 t    }
- I6 t# ~" I# z  ]  U3 b; c
- X1 j) C1 }; y9 {    public static void main(String[] args) {
* |6 H  J4 D  g) x        int[] arr = {1,4,2,3,6,5};
( P+ c' I$ g, k6 {4 T# L& N9 a        SelectionSort.sort(arr);
0 n: M8 x- G& @  |: a+ L3 t( [        for (int item:arr){
( u' [+ Y2 v. ~: t" }+ I2 [( M            System.out.print(item+" ");
+ b5 a& \2 N' z: D0 a        }
) ?# ]/ C1 h; Z" _. K    }
5 I# W# D: k1 d" F}
3 D( u& f- X; O, w! k
1 x5 S3 p- |; f% }当前只能实现int类型的数组进行排序，因此需要使用到泛型。

, j. A1 X& K7 }& O使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。

public static <E> void sort(E[] arr)
# S1 N" R  C8 E$ j) j' M; [2 \        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

public class SelectionSort {
5 {, x# g& j# ~0 s/ `& [
    public SelectionSort() {
2 ?7 T; H* e# j, h& D    }

    //
: T2 C) S- @4 U# s% Z    public static <E extends Comparable<E>> void sort(E[] arr){
/ j8 `3 z; C& ~' C: @        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
* R" \, J* H2 }& K. E, l5 b            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
+ M  V2 M6 @; r                     minIndex = j;
                 }
            }
9 b5 U; J0 H! T            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
/ L+ B$ L* }# t- Z3 u' d        }
. _. @7 ~& ?- g5 B    }
$ E6 l$ n7 x0 @3 O- Q' s- E& t
/ ]7 q( X$ f! h! U' ^1 n    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }
5 K" Q# H& }# X
$ W" o6 W! A5 I/ d4 }    public static void main(String[] args) {
8 H3 C* b% X8 t5 d, P- I& G7 X        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
        }
- z/ L( a+ w+ T" f& |' N    }
& O. K! V' S% d/ i( ]- h  G}
. j8 c$ e0 x" ]
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
0 v/ @2 H  {2 o1 M+ H3 W4 J- t) ^
使用 Comparable 接口
8 H# w! y0 |4 F8 M        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
* G* K* J5 |9 p  {1 v- V
; y5 {5 i8 Z1 W' E8 Himport java.util.Objects;
, @3 `. Y, I" Q% u
9 S5 L! B: q* t0 I/ p8 i" [+ Kpublic class Student implements Comparable<Student>{
    private String name;
$ |$ t" p5 A4 U" j    private int score;


" G& G1 o) ]4 I! {9 q+ n0 x1 Q    public Student(String name, int score) {
) P( H+ p2 I3 S7 j# b' C/ ]8 P        this.name = name;
        this.score = score;
    }
% _( m. U$ [5 b% E, S% N, Z
. p7 [+ `' c3 u6 Z/ t! d    @Override
/ v( M  D* m  C$ T4 V, `    public int compareTo(Student another) {
        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
: j& }0 P5 B% L! s( q5 v3 ?4 z         */
        if (this.score<another.score)
- e% ?0 y8 K- Y, r0 R- L+ X            return -1;
$ g+ j5 c- e- I, U* J3 V( c        else if (this.score>another.score)
- O1 r6 O6 K0 I  x            return 1;
0 r3 B3 O, ?2 n0 h1 O        return 0;
# B  _$ H! a+ n: b* X6 a3 z        //return this.score - another.score
    }

, f. N9 `4 C4 l5 H: j2 `$ o# k: H    @Override
2 H3 I7 ?# W: m+ R    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
9 }& d1 E4 h, W( J! v        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;

! S5 b# L2 u: M( z- {3 u        if (student == null)//如果传入的对象为空的话，则直接为false即可
& S: q0 |- \' ~/ }$ U            return false;

* O9 c2 c# t0 D! U* G& E$ z0 M        /*
7 v/ o: \9 J* v7 \; G        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
, n4 J# \$ H0 O) N        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
/ S0 N. a* q) L, N. `        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
+ y: Q1 F; f! {' F         */
        if (this.getClass() != student.getClass())
" j* n% L! g7 v# {) Q6 D( a            return false;

; u/ ^3 c8 @4 u! l* \9 `        Student another = (Student) student;
  a, ?$ w, k! z  }2 n4 {- `0 F+ P) E        return this.name.equals(another.name);//写比较逻辑
- }/ L3 a# }7 {2 Y8 |( G! m    }
  |( f7 l4 [* Q6 p* m
    @Override
, v: L! _2 [7 c; n; P    public String toString() {
  ^  S! {1 k6 R7 ?5 W        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
, y( v  q+ ^4 i$ f8 G, O                '}';
5 R5 @9 {  q. E+ r    }
9 {( \* v8 s, |& w0 m' Y}

7 @) V% A/ d" i主方法实现类：
( \' s& e1 x6 A- e: M# Q
public class SelectionSort {
; g: P5 D+ V1 F7 F  E( q4 |( l
    public SelectionSort() {
    }

    //
. T7 ]- I9 X# Q; E( c7 J- m    public static <E extends Comparable<E>> void sort(E[] arr){
. I/ h+ e1 z( t4 A/ E6 h" X        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
# i# c* _: N9 {( O            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
# b( b3 ^; B# w- O                     minIndex = j;
/ I1 }5 n5 x: G# u4 f* i8 y                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
! b7 F- Z0 F& K1 W, T, n        }
    }
* N' ~' Q" J7 T3 Y, o6 ?  w
    private static <E> void swap(E[] arr, int i, int j) {
; q; v; e: w% |( l1 b! M6 G' O        E t = arr;
        arr = arr[j];
        arr[j] = t;
7 e( _  I- X# ?, o' R    }
; f, `- y2 g, ]& C7 E7 z2 f3 {5 _
    public static void main(String[] args) {
* Z2 K6 I8 p" b2 K5 D. J        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
6 `0 d* o: a$ m; J4 Q& B8 U. F        for (int item:arr){
            System.out.print(item+" ");
        }
        System.out.println();

' ^5 j1 {* U& _4 y        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
4 D/ l- h1 l) @( L1 E1 b9 _                              new Student("xiaoming",66)};

/ ?5 L+ i: G3 U: y& Z; J& U        SelectionSort.sort(students);
        for (Student student:students){
! r7 a0 e! A, a) s            System.out.println(student+" ");
        }
' e+ k/ s9 Y$ a- D
    }
}
: U) G. c4 A0 k2 U! [, v( L
* c# b. m$ k0 }$ M7 y5 b" ~) t, R复杂度分析
+ \+ _$ j( x# q$ f8 S1 Q; F  q        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。


! U1 d" a9 ]% O8 r! e/ [( [- d1 `+ W
首先在ArrayGenerator类当中生成随机数组
( |& l5 b# M2 k1 E" a/ D1 _
& m8 I1 @2 \( U: z4 J: K    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
' K5 p7 \& V; R5 q9 G     */
+ y# Z$ N% {1 F' E) k- m    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
+ i/ W: Q$ b4 Q; A% @& Z        Random rnd = new Random( );
% e7 u- P5 w1 z% I, \5 g        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
    }
判断这么大数组是否真的排序成功：
# v2 c  U# O& X0 L2 \
public class SortingHelper {
  G0 T0 x% r4 ?1 O. q$ x; j    public SortingHelper() {
/ H3 J% o4 L/ V7 |+ E    }

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
0 ]% I& I9 Q5 [1 k/ P3 ^        for (int i = 1;i<arr.length;i++){
: |/ C: b0 h" Y* G: |# \5 g            if (arr[i-1].compareTo(arr)>0)
                return false;
        }
" j* [7 c5 V" ]2 d        return true;
    }
- O( i/ }, w% D/ [, o2 j0 Q}
! r6 d# K3 N* n2 s+ U: \在SortingHelper封装一个test方法用来测试任意一个排序方法：
% c' A. W0 i/ \6 u- X4 r: p; \
, ?0 [( H: w/ _7 r8 a/ e2 |    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
: x% v' Z( t( D6 t2 z- p. k8 j            if(sortname.equals("SelectionSort"))
3 D, _0 {" |( P- m; S$ @1 a7 a                SelectionSort.sort(arr);
" K( s( O% `; I  s            long endTime = System.nanoTime();
# v+ ?' B7 p4 ^; I* f/ W; N: Q            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
; k% J( O- e7 Y5 b- e                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
# ?* j, a) w' C5 R- x" K测试时间：

0 B4 |% M8 m2 {public class SelectionSort {

, K1 p8 B- S/ i    public SelectionSort() {
    }

7 i1 G  `6 q4 I* y    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
( O5 J1 `# w/ ]        for (int i = 0; i < arr.length; i++) {
1 w( M6 |; N7 u% a9 D2 i2 m            //选择arr[i...n)中的最小值的索引
- v; [5 A9 q2 k6 `; h            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
. V* ~; w$ \8 H8 g                     minIndex = j;
; G" b, I+ M$ U9 Z# j- Z/ a) r                 }
            }
4 E. M+ o; Q5 ]3 K* D            //将arr与arr[minIndex]交换位置
9 b! K" _- W' k3 C            swap(arr,i,minIndex);
        }
- e1 g! w  \. u9 }) ?    }
; I9 c0 R0 U6 a& E' g4 t
4 L: ~  a& m3 j$ m: p3 Y- C+ e    private static <E> void swap(E[] arr, int i, int j) {
$ R) K, k% n# x$ s        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int n = 10000;
, W% r+ g* o" L, |* k        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
+ j! v  Q3 E( M, Q1 x0 ~, f}
+ [3 D* P" r/ A- l3 Z
" G( |; y9 _7 s+ F  ~) S. k1 v其中如果要测试两组数组：
! n) ]2 [' j# ]# Q7 W( @4 v6 R# `0 t
    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
% b2 w+ B9 x2 M% z3 e( c4 r* x        for (int n:dataSize){
2 X7 u# J* P( s, O            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
; y0 V$ t/ Q# G) ~2 U            SortingHelper.sortTest("SelectionSort", arr);
        }
1 z$ k) [5 S8 b3 {6 t: O1 H    }
) h# t8 x/ X: L. @. I9 D
& J' Q- H# M" ^. G  \' X# N& z
9 W* X  M' j2 l 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
$ J8 S" J+ e6 I6 |- |6 i原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
2 Q1 s1 _2 t1 Q% i; S" E. V' j% n
; b/ R+ ~$ }( U% Y8 F' K+ x1 ^! D

1051373629

感谢楼主的资料
+ F5 v$ d  `9 y6 W8 @6 S9 E! Y6 f' t