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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
& v: x/ Y/ a! @7 ]; U4 J( a
# a- C: A  m# m选择排序
. G$ G3 ]& T; ]# P/ D! P; G! Z
选择排序简单介绍

实现选择排序法

使用带约束的泛型
4 a: N1 s; R. [
使用 Comparable 接口
, X- ^5 Q4 M2 j, V- [) T
复杂度分析
( I: r& L  z& n  N7 w6 y' g
选择排序
选择排序简单介绍
+ L5 @5 t9 b" j) P* ]先把最小的拿出来

* V, ?) x# |0 y" z剩下的，再把最小的拿出来
1 X) {3 M) y  A9 X
8 v2 `6 J3 p4 ~9 z7 O" \剩下的，再把最小的拿出来

5 w  @' K# G6 q! r) O......
+ i$ Z- }) G; h4 o. W
每次选择还没处理的元素里最小的元素
) X0 d! _9 g) T% p& n
0 t% }' r# `! c: G) V        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
7 \1 x. h/ o& r& `5 c- K
  x8 U9 s5 h0 o实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
, g. T$ Z* J: o; Z/ n$ g0 `3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
7 A* U0 [+ l: i. ?, _
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
: x0 A, z; b5 l: V  b* z& M
2 u8 U9 D+ t& x/ g. Cpublic class SelectionSort {
& S! j7 Z$ |& R! {; C# N
    public SelectionSort() {
0 q3 |% z2 ^! J1 T* X, N    }

    public static void sort(int[] arr){
8 C) k0 P- m* H4 u        //arr[0...i)是有序的; arr[i...n) 是无序的s
7 G  n% J8 X& Z- R2 {% `, [        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
9 U' p1 @4 A$ Q# t            int minIndex = i;
1 ?7 h2 H8 B) J# v( g- T1 Q8 H) b            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
. p& I4 p2 P! b# @, X; H                 if (arr[j]<arr[minIndex]){
, J9 p/ |8 P; F) r9 q                     minIndex = j;
                 }
! [9 j9 r$ \8 x            }
) e, j" ?& @" K* P" R            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
  \! q3 R0 e8 c& I" b3 \    }
' @1 o2 b4 z" k# Y% z: |0 A1 [
    private static void swap(int[] arr, int i, int j) {
; p( D) h, A8 r        int t = arr;
( e( x* K9 o; u) i1 f3 x        arr = arr[j];
        arr[j] = t;
; `* U4 p$ \7 |    }

; G$ u; ?0 T- n- U1 H    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
- b! C5 ^+ s( F2 s7 k+ ~            System.out.print(item+" ");
        }
; B  _* _" R0 Q2 ~4 b    }
7 o4 w& E/ A; G3 i0 L7 ?! j}

0 c( l+ Y6 D! M/ r4 H: d9 L当前只能实现int类型的数组进行排序，因此需要使用到泛型。

使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
2 k# O5 v; L/ h+ t2 J$ a
7 A2 n: T" j7 w: ipublic static <E> void sort(E[] arr)
7 |6 ~( o# c2 D) }& {- _        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
2 ]1 }- F$ p# \" t: ?+ d4 o- E. M( N
- a# v+ s" H9 m  f# Q- A+ tpublic class SelectionSort {

8 `" X7 c7 f  A4 P3 O2 B    public SelectionSort() {
    }
, {: Z0 Y+ l6 w6 Y5 r4 d" e3 m6 h
: d" z5 Z) x( H3 y    //
+ ^% Q% T) y4 {, E) n& r2 J    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++) {
0 S) m6 [1 |8 B% c7 N) J( x! p            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
( N3 \/ A4 o7 N, T) ~+ Z# D            for (int j = i;j < arr.length;j++){
8 E* ?+ u/ n6 P. [" q7 ]6 P                //在剩余的元素中找到最小的（比较查找）
6 m$ A) W! V& f+ k& D$ e& J                 if (arr[j].compareTo(arr[minIndex]) < 0){
; a; I2 H' R: A                     minIndex = j;
. E- {% D/ q6 [3 ~1 ?4 b$ L/ \4 D                 }
! z& o  _8 X" U, s0 w: P! l            }
: Z/ j3 J1 V, F6 ^' Q( z/ U5 e1 c- v            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
% f2 r. X4 O6 N8 y8 |- P        }
    }
3 T8 m1 ^& e; Q: a2 H. C
    private static <E> void swap(E[] arr, int i, int j) {
3 g  E: w* Y3 ?" b( F: ?        E t = arr;
1 |% {; H- E) H" H5 I4 u        arr = arr[j];
        arr[j] = t;
    }
, X  b& t7 p8 C) C& _; w& q
( |' Y' _0 f9 Q: Z# U& m    public static void main(String[] args) {
( r4 ^! ^# \4 j7 a9 e        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
, C4 I; o0 [: n; t# u) L        }
6 W; {* W( g" x6 s    }
}

8 b9 {& M- }" U6 t" e- ]' c        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

使用 Comparable 接口
6 y* `: {" T6 A3 ]* B4 k$ ^1 Q: x        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
3 I5 f; ~6 w9 A# s
import java.util.Objects;

public class Student implements Comparable<Student>{
1 F, x9 e  c( i1 ?8 a3 a8 O    private String name;
    private int score;
9 ?: C- [- t2 T! w
& ]# s  p% H6 f- J
    public Student(String name, int score) {
        this.name = name;
# W' x* v4 W  S9 X- w. @        this.score = score;
    }
0 ~5 B( `7 m: ^7 q! a! ~- n5 p
    @Override
    public int compareTo(Student another) {
6 }8 W0 q. E( q( c        /*
4 R8 U& m" n0 ?" V, Y) b/ I        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
) T5 J* P# U: I6 C* s: F8 J$ k# ?        if (this.score<another.score)
            return -1;
        else if (this.score>another.score)
: M6 h; x! V6 l. V  h! k% J            return 1;
        return 0;
        //return this.score - another.score
    }
/ p$ t) z3 G* U- [8 A* S
    @Override
8 t2 D  t% [% M% q; H  o2 L# t    public boolean equals(Object student) {
  S: Q4 m, `5 r! B" w& E5 \        /*
        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;
5 H2 z6 y7 C2 h
$ |6 l* a* y5 u+ Z7 V        if (student == null)//如果传入的对象为空的话，则直接为false即可
5 ?! c. o, G% I; j% i            return false;

        /*
# u4 J) l  }- p- z4 Q% X        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
0 w4 c4 M3 H7 f& o1 u1 l        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
9 X# m$ {* C' Q) o) h* N         */
        if (this.getClass() != student.getClass())
/ ?" f$ O# C. w6 A# z" K            return false;
0 Q5 H% l( Z' C+ g
        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
; V4 ]2 O' K& |9 K    }
7 d% `0 X/ v4 m# H$ I8 z* |! s
    @Override
    public String toString() {
4 Y8 v* s! g1 q4 z        return "Student{" +
- o; f0 Z# \, _& H3 {3 M# O                "name='" + name + '\'' +
                ", score=" + score +
7 N, O3 Q7 i4 A/ u. @& r; p( J; G& e                '}';
% y4 B* W  X2 m' i/ s# u    }
}

/ z( E" X) j/ o9 t4 _. x主方法实现类：

public class SelectionSort {

/ r# B& [: W6 j6 D; r    public SelectionSort() {
" U- \& F! Y! s( {) U/ R5 s: y    }
+ f. \! C) k' p( U& N* @7 p
    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
  E* a( G$ y& j' o9 p9 M4 c: {        for (int i = 0; i < arr.length; i++) {
' e. `6 z! k3 v, P, W6 N6 I            //选择arr[i...n)中的最小值的索引
% [* ]9 d% w6 j( N) F7 D            int minIndex = i;
            for (int j = i;j < arr.length;j++){
. O( n, `* X6 [! \/ I, W9 E                //在剩余的元素中找到最小的（比较查找）
9 L& Z3 s, K1 c                 if (arr[j].compareTo(arr[minIndex]) < 0){
0 u. U3 b/ G# n                     minIndex = j;
                 }
            }
1 E) {# B$ z1 X  \5 h+ \- r! m            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }
: |+ S- ~5 n2 p3 a2 q- W% k6 C
3 U/ H0 N* |% `    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
$ j" Z5 T8 G% `+ f        arr[j] = t;
    }
" ]1 L" e% _# T7 q4 ?0 Z
    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
5 F+ Q( ]& F" H        for (int item:arr){
            System.out.print(item+" ");
6 d% a' {7 u0 A        }
# O" [  R7 b' E1 H        System.out.println();

        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};

        SelectionSort.sort(students);
3 N. V! {2 }3 ]  C        for (Student student:students){
1 }4 h2 p9 |$ W, y8 S            System.out.println(student+" ");
2 Q  g: N' C1 S& K- V5 F2 \        }

    }
}
% x  v$ N/ K* ?+ l) o: F, S+ S
  ]7 m2 D$ O/ z" c, M7 Q/ [6 B复杂度分析
7 e. g. y" {* p, c$ I' h5 R        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
( R9 D; j& p" m6 b# }' R: E. H
% j* x- F! E. V- ]. ~
7 y) C# X7 ^! \: K
首先在ArrayGenerator类当中生成随机数组
. @0 f, S. ~+ g2 z. X, N
2 d6 G1 G7 _! u- Y    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
, P5 X1 R. Q. G8 I( L* D; ?0 F     */
, ^% i* K% {$ A    public static Integer[] generateRandomArray(int n,int bound){
& z( o4 u, c9 E5 t        Integer[] arr = new Integer[n];
  n& ?2 H! o+ a* i0 _3 p        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
. q6 I; }5 B6 o" T, Q    }
判断这么大数组是否真的排序成功：

public class SortingHelper {
    public SortingHelper() {
    }

. q; \5 D, q- M% m    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;
        }
0 n8 s5 g9 w' J' \$ i8 e) e) E        return true;
    }
}
在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
9 ~3 U9 x# H# `/ V- w$ k    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
: \2 ?6 p0 k* I5 Y1 j            long startTime = System.nanoTime();
% B- ?, ]$ @0 b/ ^6 Y' T  M: x5 ]) }            if(sortname.equals("SelectionSort"))
+ b0 t. P9 S9 a0 X# |. C8 X8 F2 I) V                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
" B* h4 _: x. c# E# u/ [            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
5 F( V  X0 j$ a2 O, x            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
2 G% X. h" h7 f' g0 S0 o6 C    }
测试时间：
  h) }+ b! x4 I; t. ?% L
public class SelectionSort {

    public SelectionSort() {
% j5 Y6 A& [: z3 m  Y% J    }
. v  \1 X- G/ P) e& y
& c6 x  `, d& W( b2 x$ @. p  p0 _1 ~. Q    //
( c: {3 }, o# m% U    public static <E extends Comparable<E>> void sort(E[] arr){
% A$ f# v/ e( Y$ h$ v3 K/ O        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
+ P$ A) ~: z8 _% P            int minIndex = i;
            for (int j = i;j < arr.length;j++){
9 ?& j, a' E1 Q& P( O                //在剩余的元素中找到最小的（比较查找）
! K$ ^; M2 \  z$ R                 if (arr[j].compareTo(arr[minIndex]) < 0){
: m. U$ r- E! R" x6 C' A8 P3 F                     minIndex = j;
                 }
            }
$ W) t/ @8 P2 \% N) O            //将arr与arr[minIndex]交换位置
. `- h5 L0 [, H1 Q( m! l4 H            swap(arr,i,minIndex);
3 W: E) s; `! {( r. Z6 X        }
    }
5 ~1 N2 Q) x7 S6 K( W) i1 }
' x: i( O; H/ z0 t+ t    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
  B# c+ |9 j3 P# Q+ P$ r- H    }

    public static void main(String[] args) {
: t( q( y: f( y* W  x8 b2 v& Z3 R        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
4 o; s: i0 }1 }' z# m}

其中如果要测试两组数组：
1 N! K+ O6 s0 c! z
, L+ ^: H' y( ?    public static void main(String[] args) {
; J- n, e0 `5 y* N$ F, O        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
4 O( x, R6 Z; e            SortingHelper.sortTest("SelectionSort", arr);
2 O+ C# ?4 ]8 y, P        }
    }
/ `6 `0 T# z  y  J( [, P8 p
3 o+ q- N, \- M- ^+ E; p
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
& o5 d8 k( \6 T* n————————————————
+ Y. D0 X: }2 S* U" e2 ?版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: W1 {; d! |% F% T$ R+ M2 ~, }& ^原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

1051373629

感谢楼主的资料