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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
4 l0 p6 g  F! L目录
. t' @/ [2 d  |
- N; Q. k: w, A! q8 c选择排序

- f' p/ e, U) `; e% P+ z选择排序简单介绍

7 `) f. J& Q* [0 }实现选择排序法

% I3 P; F5 I! D) a使用带约束的泛型
+ e0 Z/ g/ ?& s: N/ B& V* O
使用 Comparable 接口

复杂度分析
7 p) i" r! P2 T9 }
选择排序
" t  S' z% ~9 V2 v' n6 c& @; u7 G选择排序简单介绍
先把最小的拿出来
# W1 e" M( j1 L( Y% {9 J( S5 j! k
剩下的，再把最小的拿出来

; I0 @; c2 D3 r8 Z9 }, v剩下的，再把最小的拿出来
3 R, E+ ^% O) k7 p
......

' N1 M  F* V/ R/ l5 o& j$ S. t每次选择还没处理的元素里最小的元素
9 o- R# U) Y( P- s8 @1 W
) q9 o' K2 D+ @0 a, ]0 C        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
/ T: [: E9 a# ]
        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
4 R/ v3 q3 ^7 N3 r! z, V. b, N
* x0 A9 s/ g1 `: u6 ]2 i- `6 }        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

public class SelectionSort {
! C" |- |3 `+ ]( u% B! H) Z9 j
, ^- s$ V0 H! C( u  ]    public SelectionSort() {
    }
0 O1 h9 ^& P. U# _
    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
' F" S# y! Y1 T+ ~. q  [4 n6 T, Y! [. [            //选择arr[i...n)中的最小值的索引
) u; \% v: a7 R. w8 G            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
! X) G" \& T: {$ C4 {& i* l$ f                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
- P) h" _/ k6 T! \0 \& |        }
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr;
        arr = arr[j];
        arr[j] = t;
% B, o9 {6 R+ \( M0 J" m    }
( w: f, Y4 c) e# r& G9 ?" F- f
    public static void main(String[] args) {
3 Z1 |# q$ N- d6 l        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
        }
) E6 l  [) \- j* B7 w5 n; c: x    }
}
, b1 v( a! t- `! v
0 N3 ~4 A4 q4 O当前只能实现int类型的数组进行排序，因此需要使用到泛型。

使用带约束的泛型
* W6 A7 y/ x$ B' U& ~) A! O( Z        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
0 W- f* `2 @& J' o- e4 z
5 m5 [' D; r% ^% Z% |2 jpublic static <E> void sort(E[] arr)
2 B9 G4 x' m+ G, n        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

public class SelectionSort {

8 h- X7 X, r; K) `: q/ p    public SelectionSort() {
    }
# y1 C$ m% |7 _9 A
    //
; n; t6 j  s& S# h  |    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
; w# }  s6 n( l8 Z- D        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
" ~) p: D* x9 o& @5 z5 J7 A            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
7 ?* U6 O! `' p" X  q8 _% m* [                 if (arr[j].compareTo(arr[minIndex]) < 0){
7 A$ ~( m& Y! }. T, p5 M' h7 J                     minIndex = j;
8 F9 T1 ~. P; h/ A/ ^" J                 }
            }
            //将arr与arr[minIndex]交换位置
* Y' q9 v* W# ]; w7 m9 x            swap(arr,i,minIndex);
; P4 c9 l; B4 J2 y4 T# b, ^, N  Z        }
    }
7 w2 x7 i2 A; h1 M
    private static <E> void swap(E[] arr, int i, int j) {
9 g& P& ]& E: l9 S. d2 L, B        E t = arr;
4 V: L; U$ f$ _8 M0 T# j        arr = arr[j];
& ~6 [" K; Y+ z. `' P3 q        arr[j] = t;
    }

    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
8 G( O+ I2 O2 _  @' X3 E        for (int item:arr){
            System.out.print(item+" ");
. ]  l$ P+ W: s# O2 i        }
    }
}
9 E) M# N& J. Z1 G* Q8 F
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

9 f% l4 \* l2 p3 ^5 x5 C, v9 ~" F6 R使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

" j8 ]# {. R  dimport java.util.Objects;

public class Student implements Comparable<Student>{
    private String name;
    private int score;


    public Student(String name, int score) {
        this.name = name;
3 _/ D" H! `/ Q3 E6 b. t5 S1 f        this.score = score;
( G+ s0 y7 Z3 P2 e' O; f4 x8 p# d    }
( x* |3 B! u' R6 w1 j
  X" U  Z0 S1 s7 q; S    @Override
/ y& w3 b+ w' W# U+ L7 ?1 z    public int compareTo(Student another) {
" _: |" j0 t  q1 f; S4 _5 b+ s: g        /*
5 k8 H$ [6 a+ e. V: d, r        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
3 Y7 M. C' D  `4 z: W        if (this.score<another.score)
) N9 {% [: E, X3 H- ~            return -1;
2 K) T! X# \: D. {/ B        else if (this.score>another.score)
6 S: o( ~$ G7 g, E2 c8 R8 q            return 1;
        return 0;
5 u% F  w. l" v- R5 W( v        //return this.score - another.score
    }

    @Override
0 [) Z2 L: J# }) o, b) R    public boolean equals(Object student) {
        /*
( s9 d& g+ D' ?" x) B; {! g) b        强制转换有可能出现异常，因此需要做出判断
, _! I+ A6 m  D2 \* w        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;
, Z) W3 ]: B) O. m* i( i5 [
        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;

        /*
        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
        if (this.getClass() != student.getClass())
            return false;

% f2 ]1 s( l5 Y. W        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
* `& a9 r. ?% ~' C    }

! U; T- N$ r+ @/ v# h( L7 r    @Override
0 L! {6 s0 \( _# h5 c1 D    public String toString() {
. a% c2 n" s( ^5 B        return "Student{" +
3 A8 \  P5 F3 |                "name='" + name + '\'' +
( V; I, o1 i/ f: A; \/ s                ", score=" + score +
: R3 q. h* C' F. F                '}';
) h- k) ?% ?* ]1 W: Q5 `$ v    }
}
0 D2 r; v* N- H% x) Y
主方法实现类：

% r# e, |" H" u! o- m1 k' X  Z, i( G! s4 spublic class SelectionSort {
- p8 c; B0 H% @/ R) s: ?) |; c7 O' C
    public SelectionSort() {
6 B* p2 M1 ~% T5 P7 f; I! S9 w    }
' r% z  i9 ?- b1 B  w7 C
    //
    public static <E extends Comparable<E>> void sort(E[] arr){
8 w. J/ ?; V% c+ i$ C+ r! }1 k        //arr[0...i)是有序的; arr[i...n) 是无序的s
) ]2 h) A/ d9 s0 I" w( n2 f* x/ w        for (int i = 0; i < arr.length; i++) {
0 t: G/ u  A4 E) c; u            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
; u5 j1 L8 F" W3 I; p                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
& j% T) y, J  `* s3 u. t' [7 J            }
5 S# o. `0 F) H& m7 n9 \/ X            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
" c! u; h3 S% B8 ~7 \    }

2 P; v* Z1 ~- L    private static <E> void swap(E[] arr, int i, int j) {
- g- Y+ e2 O! K0 O9 C  n        E t = arr;
( h( Y( [' P5 V8 o        arr = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
# I7 y. c$ c4 G! M/ k* n; h            System.out.print(item+" ");
        }
        System.out.println();

        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
$ v# |8 i: U8 O) @- z! ]                              new Student("xiaoming",66)};
6 E" S% Y& C- R6 ]- `: z. w, N
        SelectionSort.sort(students);
        for (Student student:students){
            System.out.println(student+" ");
8 U0 W- |& r) [  w7 B" @        }
" l6 |, Y* h5 t* |* Y, J
) o6 k1 Y) s6 o3 C* T3 E    }
}

' h! h0 ~9 @! b4 }$ z( p$ y$ e复杂度分析
- K. N8 J) ]" Q1 n        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。

' J) b% T9 ~" ?  `8 p

1 Q, T( A0 F& q$ J  `' }( y  z  L首先在ArrayGenerator类当中生成随机数组

    /*
7 s: @0 z: n0 m    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
* u/ J6 P$ U0 N9 A' _     */
    public static Integer[] generateRandomArray(int n,int bound){
' b6 ^/ @6 C  t5 G5 S2 A* D        Integer[] arr = new Integer[n];
1 d! N1 n' ^5 C( g        Random rnd = new Random( );
' \3 u9 ~: M4 f! L  U        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
    }
) n. h' m% E9 \1 Y. {判断这么大数组是否真的排序成功：

public class SortingHelper {
    public SortingHelper() {
' F% i; h# ?! ?! _0 {    }

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
$ B- J! g; k) M2 i        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
  n7 y" _/ A0 x1 x1 Y            if (arr[i-1].compareTo(arr)>0)
* b, D% N8 t1 L0 M                return false;
! @0 Z4 Y) q5 E7 }        }
        return true;
    }
) d( G3 |/ h: U  g9 }}
在SortingHelper封装一个test方法用来测试任意一个排序方法：
2 k. x( x" q% q* ~
    //封装一个test方法用来测试任意一个排序方法
  c/ m+ p- g( r    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
; ^2 [; r0 p# C0 Y: F                SelectionSort.sort(arr);
1 w% ^$ f+ W# \- D' S            long endTime = System.nanoTime();
8 Y6 f3 H3 l4 I& O/ a3 p            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
测试时间：
  }9 L( x  H# J: V$ ?6 y4 P* V8 f1 w$ V0 A
public class SelectionSort {
4 j+ z# f; [; T
* Y% t/ Q6 L. d. }( c    public SelectionSort() {
. }# a8 v+ D+ g! x4 C3 ^    }
( f( e. S( d7 f
    //
    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)中的最小值的索引
0 F% A, V+ V! n! v            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
" N2 P: v2 w' h4 f+ q4 p                     minIndex = j;
1 _2 `0 P. [! s! {" H                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
- y2 A. L! b0 J5 s* z3 U7 ^0 o        }
    }
" Q! P& |0 G, L& y
    private static <E> void swap(E[] arr, int i, int j) {
: j- [+ u- t" u! R; T2 g        E t = arr;
        arr = arr[j];
        arr[j] = t;
8 P1 f( H0 M7 s" A    }
6 `! o. e! [) a, M$ s
3 Q% K# i6 }( {8 a% h8 d6 D% ~    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

' W$ \. _- r$ b2 G, c    }
% N1 S1 N/ d, M/ [1 \4 Y5 {+ I}
; v  X$ _2 i6 x% U0 z
其中如果要测试两组数组：

    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
5 H- Q; z$ e4 o+ t) L3 A7 N9 K# q        for (int n:dataSize){
7 `  u, v& R3 _7 @3 k4 `            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
        }
    }
" Y% T. h1 O! A+ a9 V8 S
6 z1 @" D) M/ t
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
, P$ U5 v' G4 u/ E! a; z3 F: h- F————————————————
) f7 [* y9 m) N: i2 O版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
6 G" O8 _9 A! H9 A5 }! H/ p

; r+ \# I$ e/ R

1051373629

感谢楼主的资料
. @5 B5 w, R  M! S" Y