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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
! B/ ^- p+ Q; ^# w- ~0 F: a" s5 [7 i# \
选择排序

选择排序简单介绍

2 o7 o2 U9 i1 p实现选择排序法
4 x( E# r! z; x5 A
使用带约束的泛型

, [. l, W+ Q; j8 C: Q. e使用 Comparable 接口
2 l+ S  o! F6 w% Z7 L
* q$ L  ^3 r; W复杂度分析
# V' w% P. h( ]; l  v, }3 _; k4 a: h
选择排序
选择排序简单介绍
! Y! H1 \0 i# Z* O, ~) q先把最小的拿出来
: z0 E" l+ W: E. I' h! ?
剩下的，再把最小的拿出来

" A5 d% l  @2 J' K剩下的，再把最小的拿出来
' o- c" E1 H! T) o
; u+ r. ]) F& }( M/ x+ [; f% i) z......

每次选择还没处理的元素里最小的元素
5 Z/ C( a, m0 ~
        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
: H& \' Z* Q+ ^& ~8 e
& D& a& v3 a  {7 t        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
+ z$ D. W1 P  }2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
0 ]2 H  N! i6 m3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

/ f- @4 P* I" |% G5 u- b: |        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
- o. [7 j1 i! r/ E! r( u  c
# H$ g# B, c) o9 Lpublic class SelectionSort {
2 R7 ~: }2 ]- I' H
    public SelectionSort() {
    }

    public static void sort(int[] arr){
, ?; u* E, }) m        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
* R! ]/ n% \' z5 X7 x            for (int j = i;j < arr.length;j++){
% _; l' a$ q  L8 I3 Q1 R$ T                //在剩余的元素中找到最小的（比较查找）
2 {  T  v: ?' Y; W4 c4 P) b! p- Z                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
( n) a0 |9 {3 Q1 w5 V/ V: |                 }
            }
( H7 l' L  W- I! b; T9 n# o+ _: _            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
/ N: [' U' u# V# }) L; ^        }
( c4 Y' o2 J0 L+ T/ Z; N: P    }

    private static void swap(int[] arr, int i, int j) {
* ]3 d  q' f8 I9 D1 s        int t = arr;
        arr = arr[j];
        arr[j] = t;
    }
! u# K( W9 d3 q& m8 h  g
    public static void main(String[] args) {
1 e& z3 \! V  Y- z' V        int[] arr = {1,4,2,3,6,5};
, l3 Z5 y6 V2 Z7 R8 u, }4 \        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
        }
    }
}

7 G& t( J8 a& ?, C& ?4 q9 V4 q当前只能实现int类型的数组进行排序，因此需要使用到泛型。

$ Z# i! t1 g  i4 t+ o使用带约束的泛型
* K/ t6 W. C8 u- ]8 n        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
5 o! F1 W" v3 r! t/ n& P
2 h8 G) p( B" g' W+ M3 ^8 Hpublic static <E> void sort(E[] arr)
3 d* L9 ]; J& [: f6 o# g        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

public class SelectionSort {
7 `1 l! {( a' L1 B8 B9 a/ D
, I" ~1 H9 X4 E- ?7 h    public SelectionSort() {
3 a! ?; A7 J. ^. ~. ^0 L: q# o) R. n    }

    //
: [- D4 o6 g0 s/ e' T3 T9 x    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
. O6 L. C% x4 B/ d0 `        for (int i = 0; i < arr.length; i++) {
: r0 {  A, N2 l. i            //选择arr[i...n)中的最小值的索引
; Y6 V$ X6 S7 p3 |            int minIndex = i;
            for (int j = i;j < arr.length;j++){
" M- i/ N" e9 d4 W                //在剩余的元素中找到最小的（比较查找）
4 J/ n5 f0 A6 d2 d                 if (arr[j].compareTo(arr[minIndex]) < 0){
% U" ^+ J$ T/ r) e; h# ]! Z* K% \                     minIndex = j;
' F6 |+ j) K8 Y- k8 t                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
% V3 L5 }+ s$ v2 j% Z9 N" J! @% Z    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
9 @- _- d, c5 g        arr = arr[j];
' V+ Z+ k* v: t( x3 v        arr[j] = t;
5 a( {- Z  W% h7 C# I2 Q    }

    public static void main(String[] args) {
* }2 s2 G1 h& l+ n2 b        Integer[] arr = {1,4,2,3,6,5};
( c" L: s( }/ `1 g7 v        SelectionSort.sort(arr);
        for (int item:arr){
" a) t- u3 O/ E' |            System.out.print(item+" ");
        }
    }
}

( Q( i! y* H. Z' I; D        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
% h3 e' T6 E9 z
* l+ S! t- t+ t* {- y+ q使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

2 V* d8 f5 }" t$ T7 @import java.util.Objects;
3 T0 e' b9 n# D# Q' b: C/ H3 I' Q
( n  G9 E" d2 a* N# ipublic class Student implements Comparable<Student>{
    private String name;
: P0 h) c8 b4 K* |* }) [    private int score;

6 ], H, |. _( y: w" ]# g' m3 `) z
$ [' T5 Q! B/ i4 j. P) p$ K! `    public Student(String name, int score) {
        this.name = name;
/ i% x- {  v% I  |  B* u- s        this.score = score;
% E1 b/ f# B: a7 c  O4 f    }
1 V, ~! f# b  L6 E6 X  Q( B  O1 H
    @Override
    public int compareTo(Student another) {
        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
0 q7 M/ B. F& Q- T7 _        if (this.score<another.score)
, l; D! \. S2 D8 ?4 [# i8 l            return -1;
        else if (this.score>another.score)
            return 1;
        return 0;
; n! |8 I- K/ C& K: u0 H        //return this.score - another.score
: k% b! _$ E" M$ x4 a: R* y    }

    @Override
    public boolean equals(Object student) {
5 S, |; O8 ^$ H# |& M        /*
        强制转换有可能出现异常，因此需要做出判断
        */
9 V2 X, b& [! X$ C        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;

" a  D7 R3 q5 p8 I  i" g" {' k        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;

$ j! A% e3 m5 O: g  m  O) Z        /*
        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
' d' V- y8 f. O# Z        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
        if (this.getClass() != student.getClass())
            return false;
8 f$ s+ n5 u# N; q
4 X& f: L+ t! l1 B9 ]4 J4 _& W        Student another = (Student) student;
7 _$ N; T) ~4 B- I+ |        return this.name.equals(another.name);//写比较逻辑
! b$ p, r1 w% u" _    }
# I. Y4 j: M$ H, j/ c* u
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
) n. s3 D6 I4 T2 h1 J- {% @3 z, B+ u                ", score=" + score +
                '}';
" L, f" O% m  i0 ?4 r    }
}

" \' |9 r+ n' \9 d主方法实现类：

public class SelectionSort {
( \, i# z4 E! ~# x4 e( B. x0 ?; C/ I
    public SelectionSort() {
    }

1 W. M3 j! g; }! L+ V    //
" d) s$ U/ ~9 O0 M$ t, p    public static <E extends Comparable<E>> void sort(E[] arr){
3 h& G8 t. k+ w3 `1 o5 |8 b: [0 b7 U        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
, i1 W, i: y. q4 x5 I; I            int minIndex = i;
$ T9 ?" Y5 N, W2 U- w# k            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
: a  _, I" N' L6 o* y; _                     minIndex = j;
9 A# L" B) G$ K$ n                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
8 n0 o2 V+ M# a2 }        }
; ]3 S; h9 ]2 K    }
( i; ]" W4 b5 i1 a* S' [
1 a; _6 _6 n3 N3 \4 Y1 U- t5 T) N) X    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
5 }; S" v, L1 E! s; p) w5 v        arr = arr[j];
% X6 ~& m; E9 f3 ]        arr[j] = t;
    }

6 F5 p# i' D$ n  Q6 m/ {4 x/ Y    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
6 e) F: Y- O8 ^        SelectionSort.sort(arr);
, m; }1 A% j  Q- [$ G# g* V        for (int item:arr){
            System.out.print(item+" ");
0 N$ S7 U# i0 j0 G- R5 D; j. S        }
7 [. `% i9 l. W( @$ b5 a& g        System.out.println();
3 T+ X2 s. c5 b! |5 L
( \' L4 y1 Z- W" [3 e& \        Student[] students = {new Student("Alice",98),
* E$ m( v6 p( v4 Q* D( Y5 o& Z- n, o                              new Student("Bobo",100),
                              new Student("xiaoming",66)};

; L( [2 t* n" l/ }        SelectionSort.sort(students);
) j7 Y; C4 \/ c* u: G        for (Student student:students){
3 A( p, _& ?8 i$ ~$ k! X. _            System.out.println(student+" ");
5 Y$ V, E1 a0 T* X' W5 b. J0 i; V        }
" S, ?+ Y9 ~) B) R# s
; k  u7 o( N$ h! F    }
% n2 V0 ^8 Z/ f6 h}
0 Z' Q& P( e" w+ M8 h  S$ P& e0 J
) N- w1 r" i$ y# p1 y5 B复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。



" V. D$ q0 w  p& z4 U, y首先在ArrayGenerator类当中生成随机数组

    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
! ^; N% Z" t, X+ K' {1 u" ^        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
+ c0 q: C7 H2 B/ a9 h* a# ?2 w+ v            arr = rnd.nextInt(bound);
        return arr;
    }
判断这么大数组是否真的排序成功：

public class SortingHelper {
    public SortingHelper() {
    }
% V8 `1 m; u" T
    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)
8 H6 h0 r8 v9 f5 A* U! O+ [                return false;
) b8 D! U+ z/ q9 o0 [        }
        return true;
: E- b  ?6 \8 A8 g    }
}
" k4 ~/ K0 {6 n  t9 B3 I+ s在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
) p! m" Q0 Y& y2 a0 e& q8 g    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
  U  _: x! I; E5 [3 o+ O            double time = (endTime - startTime) / 1000000000.0;
2 A; u9 [- x+ H0 }9 `( |            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
: q, X( {+ _/ i) f' ^4 ?测试时间：

8 G, Q5 _7 |, m) f! Gpublic class SelectionSort {

    public SelectionSort() {
    }

    //
/ ~# d& _+ Z) a9 y& m( ]  X    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
, r6 Y2 Y7 x/ c  [% H- S! W        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
7 B: X4 ^+ X$ w0 O/ J8 Q            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
  _7 [: j( S! U) ]/ g( H( m                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
2 d8 A* B% A$ x9 F            swap(arr,i,minIndex);
4 r- A) f0 A/ k& }4 s) e( S( U        }
4 V" t* |; F  k1 P; B    }
& B& m7 }$ W1 u
* T9 l  n+ R" L- u% l2 v    private static <E> void swap(E[] arr, int i, int j) {
5 ~9 V9 X" D3 O  K  {        E t = arr;
$ ]; Y( y7 I* O+ }        arr = arr[j];
% Q2 }! g; X) J3 l5 c2 h        arr[j] = t;
    }
1 J+ G$ ]7 Z/ S; Y6 @2 f- M* N
# ~" O. J& O" u/ r* v$ o    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);
# c+ W/ j  a+ C
    }
' N# ^5 c* s( \" p}

其中如果要测试两组数组：
$ h- s! R, C7 q4 h0 V0 n$ ?
2 ?; J, B  q) j4 ^7 @    public static void main(String[] args) {
% b4 B% }" L* @6 K        int[] dataSize = {10000,100000};
        for (int n:dataSize){
# r% c3 S" P3 j# c6 s            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
* }. H6 r+ M5 Y/ R            SortingHelper.sortTest("SelectionSort", arr);
        }
    }
5 c* @6 i4 U% x5 z' ]
  c$ J; L5 D+ ~: @
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
: }7 |6 w4 K. S' @4 q- e" W: f版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. ?: k" J  [1 Y+ \' A5 @原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

1051373629

感谢楼主的资料