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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
5 Y6 D9 j5 o* {  f目录

选择排序

/ c) s; V# r$ Y6 |3 O% @' {选择排序简单介绍
% y$ T7 f6 x- J* T
" P3 f! Y& y. j1 Z9 f7 r5 T实现选择排序法

使用带约束的泛型
6 Y1 w" T$ Z. c
使用 Comparable 接口
9 _, g5 P3 A4 \0 [2 x# z7 B
复杂度分析
0 h/ H! F$ A$ B0 s9 D
; p5 B  P- b! U5 `) D2 k# d选择排序
+ C( ]' b7 y9 P选择排序简单介绍
先把最小的拿出来
$ K, p, r7 l' ]! s) ?# Y
剩下的，再把最小的拿出来
2 ]8 o2 r* g8 W: d4 W! N0 C
剩下的，再把最小的拿出来

......

; f% k/ S0 F+ U) y每次选择还没处理的元素里最小的元素
$ Q0 E" G! G8 F( o
        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
7 [2 {, \# _) |* e4 @  m# w
        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
2 F4 \2 D1 n1 |' z7 X( W9 y4 g/ @
实现选择排序法
2 Q9 v5 C. Q1 s  U1 _$ C1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

public class SelectionSort {
+ b& B( d& G9 y1 z2 V$ T1 m1 b' S& K
    public SelectionSort() {
5 j* I2 a8 d4 b    }
+ E# a# ?) C; t' u
3 \4 R% S8 t0 m2 b) p7 z    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
4 F- {# ?/ M; d# x$ t! Z. p) |            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
: ?" b/ B; @( Q, v: ^            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
2 t0 p8 {" U$ G                 }
            }
1 c. O: ^% X. S            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
1 L: C( V2 O. u9 a; Y. i- V        }
7 V9 C+ ]8 ]$ a5 \    }

3 N. _: J0 O) y! q) q    private static void swap(int[] arr, int i, int j) {
        int t = arr;
$ A! \" n; M( ?$ W6 d6 n        arr = arr[j];
; ~$ l/ v$ A$ L: q1 C6 g5 E: D        arr[j] = t;
5 Y5 l$ {/ Y# b# c+ o+ L( k: g    }

0 j' x/ y0 [$ E8 Z' r    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
$ X4 Y( _6 G! q        SelectionSort.sort(arr);
& L- _; b+ u$ J9 D+ m        for (int item:arr){
/ W4 b' l) ?4 K6 `# N            System.out.print(item+" ");
        }
    }
9 R) g( [2 q( @" D) @}

当前只能实现int类型的数组进行排序，因此需要使用到泛型。

使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
0 ]4 {. Z5 c3 X# b" C
5 q. z9 z5 `5 k9 Q0 Z$ Apublic static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

public class SelectionSort {

    public SelectionSort() {
* S9 y5 v0 J) W* ]    }
( P3 z+ L$ C* v! i  z
  `7 c0 l5 }/ U3 S    //
    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++) {
* X/ }4 ^- B9 @" u            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
6 p8 V8 F1 m0 a- r            for (int j = i;j < arr.length;j++){
. Y' e6 O  j  \) r& V- i                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
; K0 m7 Q6 U; p, Z* o9 I8 {                 }
3 ?/ |/ }* o6 ^: n& F/ |            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }

/ j0 m- k7 D3 s) N    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
$ b; R3 H+ j* n        arr[j] = t;
0 G( X! C1 b, y5 O; ~9 K% Y7 Q    }
8 F  N6 z$ {  q
! I+ T9 A4 n, W5 l    public static void main(String[] args) {
8 ^+ M; z/ @' S# s) B# R        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
0 T0 j2 }9 t! J* p            System.out.print(item+" ");
        }
2 K6 ?4 y; p5 I4 i; J    }
}
  A# v' n$ J- @3 g! \3 x
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
- M3 H* `: P& q" z; J4 c
使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
- `  T) X0 d2 ]7 h$ b
& v. D+ k3 D, q" ?1 v7 }import java.util.Objects;
# Q- i# r& C# h) t: I
public class Student implements Comparable<Student>{
    private String name;
    private int score;

/ r3 b2 h& U& x; B: v: d* C  g
) g# N. L! r+ ?% d    public Student(String name, int score) {
' B1 A, J. ?/ o& {/ u        this.name = name;
& ?1 @0 n1 s* l" e* k$ y' g        this.score = score;
; F$ p- X- u. w' s& {% I# \. c    }

    @Override
    public int compareTo(Student another) {
0 t1 M- y% w* D9 I( J( H3 |# H! b        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
$ c# l0 |7 F+ j0 b8 n         */
        if (this.score<another.score)
            return -1;
        else if (this.score>another.score)
: b, \8 |' h* d            return 1;
        return 0;
! {4 h6 v1 ^1 m0 Q& U        //return this.score - another.score
    }
1 S- ?) T1 i9 G( X2 q6 H8 Q
    @Override
    public boolean equals(Object student) {
- }# H* u2 Z! e& {9 y2 _        /*
        强制转换有可能出现异常，因此需要做出判断
) B" T- I: p3 G) [8 Y% }8 ]        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
: d3 @. m& [' y3 O  T            return true;

        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;
4 F0 s3 m( y' v+ ^" u& K; i
        /*
" ^8 Q3 p# }8 p        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
, E" q3 l& R# E# H        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
; j# G$ I, S# r; R' K3 _$ {. S        if (this.getClass() != student.getClass())
            return false;
$ ?& F  y; K7 i
5 H* A' K& V* c: U        Student another = (Student) student;
( B0 _* `/ l$ w" K        return this.name.equals(another.name);//写比较逻辑
0 F; Y3 E' `3 m0 v9 C- }    }

    @Override
  S$ j+ ]  U$ O) i    public String toString() {
& M9 v9 E/ w9 I        return "Student{" +
                "name='" + name + '\'' +
) a" e/ u" n; F7 L1 n                ", score=" + score +
                '}';
5 G6 O$ d  e' G6 Q' f    }
}

8 @$ a) ]+ X& A% L主方法实现类：

public class SelectionSort {
2 S& Y8 F: p2 @5 i. _8 K  }* k2 E
    public SelectionSort() {
* X5 E6 d. y5 n    }
  v* q6 P4 U; M* {" ~' D9 v; ]
    //
8 I) x1 O1 b" w% e3 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++) {
            //选择arr[i...n)中的最小值的索引
$ H9 w2 ?3 [0 I% v3 F            int minIndex = i;
3 f: S2 B1 L: x# [6 }1 C0 R            for (int j = i;j < arr.length;j++){
  F& F0 S& N+ F* X( L- |% x( P                //在剩余的元素中找到最小的（比较查找）
" c9 y% ^  {* P" H& @, e2 ?6 V                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
( [7 _* c' N! z8 J" B+ p' Z                 }
, g  b" f" P1 B; h            }
            //将arr与arr[minIndex]交换位置
5 @8 i+ I2 H) S9 z2 l6 q% [            swap(arr,i,minIndex);
# f# k9 d' D9 }: h0 u        }
- v# ?  ^" q4 u( [0 ~; O  i$ \* S    }

; t, O$ ^9 q  g4 c, p    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
6 L6 S( n6 n( {        arr = arr[j];
9 A. |2 E, r. ~/ S        arr[j] = t;
% P- P# G  f/ ]/ S    }

- A0 W8 h$ W! v) N2 ~    public static void main(String[] args) {
8 }  N7 I# j$ z& H# e( Y1 l+ @        Integer[] arr = {1,4,2,3,6,5};
& T' L# U2 R: o$ L$ s* |9 P' d( `        SelectionSort.sort(arr);
        for (int item:arr){
% ]1 p' e4 S) |- ?" |% }            System.out.print(item+" ");
) |% \9 G( |' j. E        }
5 o8 s6 |+ N* A        System.out.println();

        Student[] students = {new Student("Alice",98),
' o2 t& D% y9 m' T: Y  M; e                              new Student("Bobo",100),
2 v; C( n/ l$ Y/ }                              new Student("xiaoming",66)};

: Z. I1 n& I3 R5 @  G. Q: y) n        SelectionSort.sort(students);
# j- u/ {  Z3 W5 A8 F9 k% c& F        for (Student student:students){
2 Q5 F1 j1 J8 v            System.out.println(student+" ");
3 y2 i+ X1 W( X# n        }

    }
}

3 G& S7 x1 y# A2 {. f/ \/ U+ X( ?复杂度分析
* i. ^4 X( L/ ]6 i5 V        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。



* p4 p/ V% b1 Q* j) {首先在ArrayGenerator类当中生成随机数组
) [( M) R. S' v9 d$ d" J+ k
! k  I1 R0 k' Z( _; a1 Q    /*
* N' n. G8 @0 N% Q4 z1 j    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
1 r* s. {" P2 u5 J( q7 _. V8 ^     */
    public static Integer[] generateRandomArray(int n,int bound){
7 O4 d' T3 C8 |( k! `3 S8 n) J( D        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
! q# ?4 p4 s8 [3 p) {3 Y% W3 Y        return arr;
    }
' D8 A5 E# H% s$ o判断这么大数组是否真的排序成功：

/ h# s* _; J/ W/ y' K7 wpublic class SortingHelper {
7 {) O4 i% [; \+ H9 v% Y    public SortingHelper() {
% \! ?5 n8 I1 _: n' m2 W    }
  d& c1 Y% d5 A4 V# E3 E0 N% ~( q
    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
3 K& d5 b, G5 ^        for (int i = 1;i<arr.length;i++){
3 `) e/ ~. A( E- R: ?            if (arr[i-1].compareTo(arr)>0)
9 {6 B$ o* {8 j                return false;
        }
        return true;
    }
}
在SortingHelper封装一个test方法用来测试任意一个排序方法：
( i9 w7 m2 ?# T) E$ y5 c1 F. n
    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
; B& k' w7 t" Z' O9 ~! A8 v            long startTime = System.nanoTime();
. f6 l$ Z' H6 y. n7 I; |0 L- r            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
2 c' G1 k0 B' `. d  Q+ `# x5 R            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
" y, G" G0 c! p+ p% b7 v! i                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
测试时间：

4 S9 J+ w, q: `  n7 r: |public class SelectionSort {

, K! X( G+ [2 J7 a    public SelectionSort() {
  W, b3 }# K) R" c6 p    }

- A+ W: q! U4 S# H) W/ O: t    //
, D4 Y6 a  }) A% ~: ]    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++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
' A' V3 S' ]6 K' j/ Z' J            for (int j = i;j < arr.length;j++){
2 R) e, v' y0 P* r+ A' A+ Q                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
5 D: {, f1 ]* T# j3 {5 P  T( I; \                     minIndex = j;
+ u; I5 j; R5 K                 }
5 i7 {7 E9 t9 x4 i6 D            }
( s$ c0 `- K% j  x1 G/ m            //将arr与arr[minIndex]交换位置
1 F, b, |+ @% ?) Q            swap(arr,i,minIndex);
        }
, f$ U1 ^# ^$ M. J2 i  c$ m    }
" M# ]0 p( E/ ~$ u% a" U2 ^
    private static <E> void swap(E[] arr, int i, int j) {
: N- O% `1 w' `2 S) M8 [" C; \+ }        E t = arr;
        arr = arr[j];
0 I4 f4 ^. G6 M4 j. z1 K4 ]0 z        arr[j] = t;
    }

    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
; d( U0 q+ c1 \' `  e, X}
$ H8 c1 W% i1 r1 ?1 E  n7 q' m
其中如果要测试两组数组：

    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
/ i; g1 b2 Z5 m5 j0 H& \! y        for (int n:dataSize){
" W- v0 |8 a4 X" y            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
1 ]8 ^) A" Y) Q5 L2 s- {# N8 z            SortingHelper.sortTest("SelectionSort", arr);
- c6 y, {; |' G        }
    }


6 x; @4 ~5 `+ e 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
5 z* q& V! O( L+ O! y版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
7 U6 {2 r$ n) X5 e

6 W# z+ i( Q/ d

1051373629

感谢楼主的资料
. D9 P/ z- r/ M( Q5 v( O