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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
( ~5 w# n/ l" N目录
1 J* A) M$ p. p' g% M1 m
选择排序

$ P7 `8 ~7 m  _选择排序简单介绍
# c4 c, n' p2 t7 l& r
实现选择排序法
# T# @7 v" V* L& _6 M* ?8 @
# A. @+ z3 x) {$ L2 B使用带约束的泛型
/ X+ a! X' M7 D6 h/ Y: R9 ]
使用 Comparable 接口

复杂度分析

选择排序
选择排序简单介绍
2 U% i, A+ U4 V先把最小的拿出来

5 r5 S! @/ E/ m6 {. p- k* K  }剩下的，再把最小的拿出来

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

  a9 p. W: T0 y0 `......

  Q( l0 D/ \# i每次选择还没处理的元素里最小的元素

        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
; q5 E' j2 L8 w; D. O
6 ~% m0 L' @, ~* M- u        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
% ~5 ?, ]$ {& i6 n0 |, }
实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
) @! m) k: z% \. w3 S
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

public class SelectionSort {
7 q- c, t- {- h2 A- P8 x
    public SelectionSort() {
1 D) K" q' V0 K* P' R+ O    }
3 o$ a* B; @# s- g
    public static void sort(int[] arr){
  ^6 F8 ]$ M3 L& r+ A        //arr[0...i)是有序的; arr[i...n) 是无序的s
4 K0 @1 y& b1 L: [        for (int i = 0; i < arr.length; i++) {
+ ], y9 k8 c1 P$ s3 c: h) \+ d( w8 L            //选择arr[i...n)中的最小值的索引
, O7 O' {0 P& ?4 _            int minIndex = i;
* u/ l7 P; k9 X4 P. P            for (int j = i;j < arr.length;j++){
. N: e3 |  m. n% U                //在剩余的元素中找到最小的（比较查找）
! `/ Q' w0 I+ i5 q. m# F                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
' B' x5 n6 N( w( ^6 r; U                 }
/ l. Q1 b, D3 i/ [& }            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }

    private static void swap(int[] arr, int i, int j) {
; w- ]$ P4 E' p        int t = arr;
, ^/ P9 C3 U3 z, T8 [" K        arr = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
; B- F: g3 D, q& V7 `        int[] arr = {1,4,2,3,6,5};
$ z& K7 k  H2 N, n9 Z9 j9 q8 L0 t2 R  Y        SelectionSort.sort(arr);
        for (int item:arr){
+ L' z" @3 V! F* }1 [0 M5 D/ S            System.out.print(item+" ");
        }
    }
}
9 t: M1 |) i' z/ j7 M( p
当前只能实现int类型的数组进行排序，因此需要使用到泛型。

( u. y& t& S+ Q3 ^$ V& T( S: R使用带约束的泛型
  p: N' t/ f& f        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。

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

public class SelectionSort {

    public SelectionSort() {
    }
5 u2 J1 q! A6 x5 e, r5 G6 C
3 O" o& |! |& n7 K# F% j0 o( z    //
    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++) {
; ~' j0 l* J; T' D3 F2 }/ F            //选择arr[i...n)中的最小值的索引
* Q' R* ?8 m% ?$ G            int minIndex = i;
3 {& E9 o5 F3 |8 o9 G% u2 e6 n            for (int j = i;j < arr.length;j++){
1 _0 z' n" _0 I3 K) W                //在剩余的元素中找到最小的（比较查找）
2 V& n) h1 z- ]2 g! _                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
0 y+ S, i" K. u* @+ w  a; _            swap(arr,i,minIndex);
/ r2 [3 K. N& q2 f3 `/ H        }
    }

- w' i7 B4 c9 \    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
/ E( x3 L9 x# _/ x    }
0 c; X% {) ]8 Z6 o9 J9 X" w7 c
    public static void main(String[] args) {
$ \* P/ n3 [$ [" `        Integer[] arr = {1,4,2,3,6,5};
, G! d% F) S9 ]6 W' w        SelectionSort.sort(arr);
6 J0 E$ D5 r4 H. Y6 f% D- K        for (int item:arr){
9 T! ^; w! R0 B4 V; @            System.out.print(item+" ");
        }
9 g  n$ P! U: z    }
# ~( T; @' z- E% c. i}

        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

9 g. R& g# L4 [7 }使用 Comparable 接口
- T+ f5 |' e# A9 O. `- H0 ?        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
  z6 [& l$ ?" `7 x; y
import java.util.Objects;
1 k" u7 C1 \# T) b# h6 p
- J# Y1 v1 D' d" ]; M3 s; k1 Mpublic class Student implements Comparable<Student>{
7 n6 L5 p" G$ }) ~7 \5 g- i' Z9 F0 e    private String name;
    private int score;


6 z. ?) L2 V. D' b    public Student(String name, int score) {
3 |2 L3 F: n. a4 d        this.name = name;
        this.score = score;
7 I" z! [5 Z! y' ]    }
; l2 {% @! l  ^1 z+ @+ {& V2 }
    @Override
    public int compareTo(Student another) {
        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
        if (this.score<another.score)
            return -1;
7 t( [  b8 Z; T4 u& {5 p- W        else if (this.score>another.score)
            return 1;
        return 0;
        //return this.score - another.score
9 O# ]- c* J7 b2 b    }

    @Override
/ q6 W( q8 q( O  l% V    public boolean equals(Object student) {
7 o) O8 t0 f  o# L" q9 l        /*
        强制转换有可能出现异常，因此需要做出判断
        */
  j4 s+ ?$ f; H5 ^0 B: {        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;
% W4 `. I6 d( L
        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;

7 k9 j. O7 p: m4 R7 F        /*
1 M  u+ k" c* |# m# A0 v  ]9 Q        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
( T# q9 D! z" b- S0 }- `2 O1 ?        if (this.getClass() != student.getClass())
            return false;

        Student another = (Student) student;
) Z5 Q+ }, g3 n( {+ r        return this.name.equals(another.name);//写比较逻辑
    }

1 f+ ]6 x3 j; f* Z, C/ r    @Override
  D6 z, C+ [$ `( P  f    public String toString() {
        return "Student{" +
) Z& W. ]/ [( }5 G                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }
}

! E" k  k- z2 T主方法实现类：

0 i; n( q4 V1 r# ?" W" \public class SelectionSort {
+ g6 S4 Z2 j# V( h) n1 i, Y
5 {* a- {# v: L& ]* A2 y0 `    public SelectionSort() {
    }

    //
2 X- w+ N+ a; T. a. U    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++) {
5 x4 S* R8 ?4 C. j: }            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
, f/ t+ i9 m; `7 x# n                 }
& q, q9 T7 B8 H+ |. j+ J: T6 r            }
; I6 O  b: }: Y% Z- {& a            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
6 [7 w  O2 r' L* b        }
( w3 u0 S& t! y/ F9 m( U    }

    private static <E> void swap(E[] arr, int i, int j) {
+ ^. J$ H& ~) k8 q5 S% U" H        E t = arr;
& d- A* m9 d8 P6 Y. d7 _        arr = arr[j];
. x- Y: J& q. e( S: }" N2 R- n/ q        arr[j] = t;
    }

  n" r* r6 H4 q    public static void main(String[] args) {
& @% L0 q) D- k! h! V3 @        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
- {1 ]  q6 e0 i  V        for (int item:arr){
3 A: K8 p  ^4 D; {4 p2 \            System.out.print(item+" ");
5 |0 k! h# ~9 S5 F) i9 {1 v+ ?( E        }
+ e8 E+ C! C! n  d" m9 P        System.out.println();
* f9 b! ^! D6 `  D9 m9 S' u+ I
/ _" n, Y2 D' b7 n& p        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
6 e' T3 C$ f" j& `+ y# Q
        SelectionSort.sort(students);
        for (Student student:students){
            System.out.println(student+" ");
        }

    }
}

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

% o" t( y" b2 W

首先在ArrayGenerator类当中生成随机数组

. I. d7 g) ?2 J' ]5 Q- F( j    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
+ V4 B9 O& q1 u8 A1 h     */
( |2 {6 ~! a% I, f; L+ n    public static Integer[] generateRandomArray(int n,int bound){
6 L4 [4 O) U0 R1 W$ `9 B        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
! N; o5 G( E( O7 @2 F            arr = rnd.nextInt(bound);
# I* L  {8 t* b# Y/ W0 d1 g1 i        return arr;
    }
判断这么大数组是否真的排序成功：

3 U' y5 ^9 T5 d+ hpublic class SortingHelper {
, s8 F  k* Y$ l4 f% k# y# Q    public SortingHelper() {
    }

+ {: e2 M; t% C' t& K$ N    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
/ D1 c, F& ?! L: P6 l        //判断数组前一个元素是否小于后一个元素
0 w! X! T) J) D7 ]5 w2 s% U  ~        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
                return false;
5 b, I  E: c3 P2 j7 [2 C' |        }
        return true;
4 R6 |+ M4 ?. M+ H3 B, X    }
}
9 ^0 f, V% b9 T5 L/ N5 l9 r1 h4 s在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
; \2 r# f- V: m2 t5 O    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
# q" a$ |5 S# V8 g7 |' t                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
7 [- n5 j  T0 G: Z! [4 n; w8 {            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
% E' D( {; |4 {" t9 b                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
: V  Y8 L. s! O2 M7 ]1 Z9 n# p测试时间：
/ F( ]8 b; ]4 h- s* b8 Q  ]
public class SelectionSort {

    public SelectionSort() {
$ I% w. |' J2 d    }

2 w" Z* p5 h0 L! H    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
6 p/ x' m6 R8 @8 C: G6 J. C        for (int i = 0; i < arr.length; i++) {
- b, u" m" X, P% v$ }" ~8 B            //选择arr[i...n)中的最小值的索引
* z! T4 Q# L: h; d. M! c            int minIndex = i;
- L% e8 B" C2 ?, y9 I            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
( w8 x0 G" q' V9 J/ c! \3 G                 }
% \, ?* |4 e+ L& h) ~, g9 Y            }
+ Y# o$ q4 o, i, i, c            //将arr与arr[minIndex]交换位置
0 ]; A% `" k" E7 x            swap(arr,i,minIndex);
6 k8 f9 [; [/ p! h) N9 }        }
6 \% [2 Z- c6 {2 o8 [' D    }
- u* Y0 K. a$ v# d! M
    private static <E> void swap(E[] arr, int i, int j) {
; @% `2 D: [. a( q        E t = arr;
        arr = arr[j];
        arr[j] = t;
, h  ]" A( Q/ ?5 D! N6 C- m    }

/ V4 o6 f2 G- K3 d) Z    public static void main(String[] args) {
" V. [) i( p! t# v4 @( H0 ?" J        int n = 10000;
+ c/ L- T2 b/ _        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
4 I3 m/ B# V% h7 t        SortingHelper.sortTest("SelectionSort", arr);

# [% ~" l& a: N' y4 M8 _/ o    }
}
! E1 s3 U) u) T8 h2 U+ ?; N; |. G% ^- a
其中如果要测试两组数组：

0 D- b  O; f4 B- G    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
/ S4 }4 m7 L' f: R) o            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
4 h1 G% I6 B7 q+ E  ?+ a        }
- [" d$ B8 r: a& D" c# j7 `; S' g    }

' `# g4 |' I% }
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
  G' A! h/ @- E8 V0 L# T4 \————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 J8 j) _: g5 h) i+ ~" P原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

- J/ n% M- r+ {, z, Q3 a
) n* n& N  J. g+ f0 b( Y1 U

1051373629

感谢楼主的资料