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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
( d! K1 P3 O& ^: }  J* c8 C/ E目录
$ z$ w$ P, R( G
选择排序
9 N7 J+ o; h* U# ]1 w8 v4 X
选择排序简单介绍
/ {8 \9 K4 G$ L& ]7 ^" [
/ P, O7 u2 E3 d+ H" w实现选择排序法

- s( _+ v; \: N  B9 M& v$ ?使用带约束的泛型
% @3 b+ |1 j; t5 d+ l! H
5 _8 d* ^( q# S$ G使用 Comparable 接口
. {$ a& a1 e, C( o
) B8 j8 E4 r* B0 Z复杂度分析
1 g  E6 F7 P1 N- I7 j  S
. W3 t" [! q* i- O' v5 r选择排序
& n! I1 p9 M5 d- h! n: v. Y" L选择排序简单介绍
/ C; M6 L$ ~# T( \6 o5 H先把最小的拿出来
( L3 w( O9 ]) J* Q! i8 _. n
8 }& o1 f& h5 b. A. K4 J0 z: q/ M剩下的，再把最小的拿出来

剩下的，再把最小的拿出来
- |4 v/ F" D" n5 z7 F3 c
......

每次选择还没处理的元素里最小的元素

: g! _2 k. c; M: t2 l8 ?/ z        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
( I. m( @, w3 e. R2 H7 k2 m" S7 ?& j
% j0 _! q& `- C  N) k/ b& g  ^# }        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
* I( M. D7 G$ l7 u0 U7 y( K/ L2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
0 f8 S2 V0 C0 t% m# O/ G
! b% l' r4 @7 t: O0 w0 b% d: z3 g1 I        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
/ \: [* h" L- z( ?7 j+ c/ H. S! l
( m3 u2 z' q8 a. X& h* ipublic class SelectionSort {
. `# w; e  p: A2 i  B; A
; x' }$ d; Z7 ]- W    public SelectionSort() {
+ X9 X( Q* C1 e    }

    public static void sort(int[] arr){
, C  j9 W4 H" p# \' Z1 c: K        //arr[0...i)是有序的; arr[i...n) 是无序的s
/ D- o2 \, C' d        for (int i = 0; i < arr.length; i++) {
4 V) i% y; T# o; d4 y' U5 A1 V            //选择arr[i...n)中的最小值的索引
6 U' ~: ?( C. e4 ~            int minIndex = i;
3 K6 n, {2 S5 `/ N7 u" u; N9 H            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
4 ?+ m! ]2 f8 X/ w9 Q                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
                 }
            }
9 i& G' G9 j7 f8 |! f            //将arr与arr[minIndex]交换位置
, _& \1 X$ B$ e9 F8 L  k# v            swap(arr,i,minIndex);
# z& L2 F( q7 ^9 m- }0 t        }
    }
/ M  w  [; C: A) N' j0 }  e
) y2 B# @7 @( \3 a9 {+ K9 ^) g    private static void swap(int[] arr, int i, int j) {
        int t = arr;
        arr = arr[j];
        arr[j] = t;
3 u$ u7 z: ~4 i5 F5 B5 _3 y    }

    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
. U! v; n4 h4 h' i        SelectionSort.sort(arr);
6 D# g+ \- e  [7 ^1 K4 B/ `        for (int item:arr){
2 B: M# z; i. t            System.out.print(item+" ");
3 o' O7 c3 F) V9 E" I7 a        }
    }
! l; `* g5 _( o$ N2 E}

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

/ g6 {* x" i8 y1 f0 t, T使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
( t* J% U) `" [+ C  F2 J
public static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

! A6 z3 t! r! N9 |  k& rpublic class SelectionSort {

6 w3 ~7 `; E; O; u# b  S; ]) I    public SelectionSort() {
- P; Q' H: p4 T3 |8 t3 t    }

    //
    public static <E extends Comparable<E>> void sort(E[] arr){
- Q( m" @) C3 @  P2 G' _+ ^        //arr[0...i)是有序的; arr[i...n) 是无序的s
. H8 H% N( A7 I; [2 O* Y4 c* T        for (int i = 0; i < arr.length; i++) {
" M1 U' c1 `& p( i: w) p            //选择arr[i...n)中的最小值的索引
- T. s; w) P( [# l' @% T8 W  R            int minIndex = i;
, u- L6 Q$ ?1 o) W            for (int j = i;j < arr.length;j++){
+ s6 ?9 R/ [" a. L, W3 ~                //在剩余的元素中找到最小的（比较查找）
0 e0 J' i6 T; o3 I                 if (arr[j].compareTo(arr[minIndex]) < 0){
9 I4 e) E/ @' `                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
! y8 Z& z& ^7 A) K+ o    }

# V) C; n' y  m7 J; B3 ^- _0 s7 |9 F    private static <E> void swap(E[] arr, int i, int j) {
+ a7 A6 |) @/ Z        E t = arr;
        arr = arr[j];
        arr[j] = t;
9 v6 Q4 Y% [6 b3 u) g- [, J. m    }

0 u3 q, Z, g6 V8 m0 y2 ]    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
* h& V* ?! Y' E" B7 r        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
. A( r) D) i' D- {* ~2 ~: J7 x6 ~        }
$ F, r& |( M) O- o    }
}
' p  g% d. d* e& M% i3 w$ J8 U
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

. A$ a5 l1 n9 \& S+ o1 x使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

5 ^+ v1 R$ |$ K6 v6 Cimport java.util.Objects;

- C# P( l2 M2 @' apublic class Student implements Comparable<Student>{
; v* @: B$ X! k: u    private String name;
    private int score;

* K4 h$ t7 w, Z, V. S8 i" L1 v
    public Student(String name, int score) {
9 z2 [# O- {6 @* c& X' `0 \        this.name = name;
        this.score = score;
    }

5 j. M% y% V" ^+ x9 n! U/ P    @Override
# v2 g: O. C5 I/ i$ f    public int compareTo(Student another) {
        /*
/ L% G/ V" A& U6 b- J7 K' ?! F9 p        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
( o9 n  `2 z, _, c: P7 q& U         */
        if (this.score<another.score)
2 q$ ~. ^; R, `' m            return -1;
/ B  n- n$ h7 n& _( l$ ?2 D        else if (this.score>another.score)
1 J! G- F5 [: K# k! U            return 1;
5 a) R- f! }! y        return 0;
. z/ R  D$ i# I- s2 ~        //return this.score - another.score
8 J6 T$ m- U' w9 {& ^& s1 R1 J    }

+ J. j$ E  Y8 B- z    @Override
    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
        */
( j1 E) V( X- u+ B9 j/ Y        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
9 d3 N, o' ?7 T2 n' p% i            return true;

3 a4 V3 |; D9 `: R/ q3 l        if (student == null)//如果传入的对象为空的话，则直接为false即可
) q2 L1 Q1 g% B            return false;
8 N( ]8 l5 \5 Q* _
9 y* E1 c* N5 b' O$ e+ B        /*
        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
5 _4 A% P; b2 ~2 R3 [        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
        if (this.getClass() != student.getClass())
            return false;
& U7 u# d2 S  e" U1 C( U. s1 B
8 d) m3 I* z$ {2 c* i        Student another = (Student) student;
- L3 \$ j# w" B) H$ Q: B: \) J        return this.name.equals(another.name);//写比较逻辑
) {+ {( J0 {! ^( e/ Q( l    }
% ?9 @: }1 T9 K6 k' z4 D4 m
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
( z6 K# t4 N8 `7 G$ ]& s                '}';
    }
}

主方法实现类：

public class SelectionSort {
3 b" K: o' E" u5 M" C# U0 g! i
    public SelectionSort() {
! n5 M* Z9 W- a    }
: e" |. `/ @% `7 b3 h9 w/ ~
    //
    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)中的最小值的索引
# R' G% X- h  M% G5 Z- D, e            int minIndex = i;
9 e8 T* y; d9 k# B; ^% H  F            for (int j = i;j < arr.length;j++){
" p% E. _* }! H$ P                //在剩余的元素中找到最小的（比较查找）
0 P; q' _; n5 J: Q+ e/ t' w8 v5 D                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
- w& w  o: x. O3 f8 E                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }

% T2 n% `& |5 s( k    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
" z. k9 d8 w( d% D6 o- V+ k        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){
            System.out.print(item+" ");
) d6 j+ S  e! O# t) z        }
$ s1 ]- s' z9 i1 V9 Y/ [$ v9 ^$ E( H        System.out.println();
5 T1 Z) Q. G7 u. u+ X
        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
4 f* j# L" R4 I+ U' W2 `                              new Student("xiaoming",66)};

        SelectionSort.sort(students);
        for (Student student:students){
# g! z' I/ V6 q- w- R9 J! o, A            System.out.println(student+" ");
        }
( z& Y/ n3 M5 q
    }
}
5 |9 g4 ^% v( Q) y: f1 V
复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
8 C, f9 W3 c- d/ S! l0 m


5 m2 T* d; n( L7 z) S5 T首先在ArrayGenerator类当中生成随机数组
" [! S% W$ @6 X( A" ^, D
    /*
( _3 q) p1 z1 l! Z. g9 B. ^1 d    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
/ o: ?1 f9 `+ K1 I        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
4 K8 G4 a5 t" R& s$ }9 X8 p$ }  e- o        return arr;
    }
5 f4 d# u8 p3 p% N) L判断这么大数组是否真的排序成功：
* M' K: N. Z. k' l! ?& l
public class SortingHelper {
    public SortingHelper() {
& y' K7 ]3 j  x4 m    }

# I# ~( O+ Z3 h, u1 w# K$ Y* l    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
7 N( S1 x) z9 Q) \% a        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
  n& y  D& I& W4 l. N( G            if (arr[i-1].compareTo(arr)>0)
                return false;
        }
        return true;
: }+ _4 x4 k' M' @6 X    }
}
在SortingHelper封装一个test方法用来测试任意一个排序方法：

9 ?- |: F( z9 }! f    //封装一个test方法用来测试任意一个排序方法
+ u: f! C9 ^+ V' J" S5 M    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
- ^2 ?! h( U2 i9 c0 {  h            long startTime = System.nanoTime();
" h3 P2 S7 I' z( ?            if(sortname.equals("SelectionSort"))
6 @7 |  S& W# ]                SelectionSort.sort(arr);
6 Y! `8 Z/ C8 C: Z            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
" R( Q; V) Q; p$ f7 Q5 M            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
' ]' [: ^# o* Q& ?. B7 m$ J, @    }
3 E% s2 X% E% \' q  p% v; X  s7 [测试时间：
$ k& k- j- a4 L$ Z4 g
7 H" i( A- M  ^$ v5 A/ K2 ?0 A  l4 opublic class SelectionSort {
/ i7 W# i1 D. Y3 l' |
    public SelectionSort() {
    }
% Z$ l" f0 Q( Y- r
; n3 Q2 T  Q! R/ a9 y    //
    public static <E extends Comparable<E>> void sort(E[] arr){
. k8 U# H9 Z% E; @% F# B        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
6 f+ `& `3 z  u# T( x            int minIndex = i;
5 Z' L. I2 b. y5 u, k+ s2 u& q            for (int j = i;j < arr.length;j++){
) G( o0 u8 H& h# J                //在剩余的元素中找到最小的（比较查找）
, M/ w# d* E# W0 H+ q                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
0 @) o9 ^' k8 s. U3 Z3 |                 }
* K' O/ i) g( S6 c1 g0 g+ b' S            }
            //将arr与arr[minIndex]交换位置
, a' H$ V0 S- S& Q9 q            swap(arr,i,minIndex);
        }
3 o0 _4 k% J# \9 B& b' X. R& B    }

+ v- T$ [& d$ B3 E    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
1 U9 Q: C3 a7 i        arr = arr[j];
        arr[j] = t;
  A4 ?4 }3 m0 ]; v; k7 J  c' h4 n) U    }
5 H" t% n4 W. d( ^/ z4 ?2 M1 B2 |
    public static void main(String[] args) {
        int n = 10000;
% h  Y* {7 j$ A* t$ m# g+ C0 t% O        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
. \5 ?" v" [1 \        SortingHelper.sortTest("SelectionSort", arr);

    }
}

其中如果要测试两组数组：

    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
        }
2 d& T4 J0 l+ c9 P9 |2 N& u5 s( {4 P    }

3 a0 _2 U, t; B% B$ r
) r0 k5 z+ B/ U; u, r! f; V 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
8 Z9 s' L- e+ e, K————————————————
  `6 g  \6 R4 R4 o版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
2 k# q: [7 T, ^, S. [原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

4 m" X# W7 G' P4 c: v: c

1051373629

感谢楼主的资料