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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
4 v: r* Y2 O- o
' G/ x# [# w+ Y* E# ?3 V) z* Z) |# i选择排序
* A6 e/ G: d3 b. `
1 G: x* S9 N, j* N$ D  u! R/ T' g选择排序简单介绍

实现选择排序法

7 t! |# E) D# E  I' P使用带约束的泛型

使用 Comparable 接口
$ {2 x1 ~( J  I7 X; r# A
, b4 Z7 w$ ~3 ?, p" F复杂度分析
2 y3 W$ X. `% V: l. X; r& b% {' X
1 a" b4 C2 n; @% \9 ~选择排序
* D( x+ p1 `+ T% m选择排序简单介绍
先把最小的拿出来

/ v3 L2 \8 C* @* H5 t# u, E剩下的，再把最小的拿出来

  d2 R( O# a3 w' i3 [9 U剩下的，再把最小的拿出来
) s4 I! Q* O# J; X! @' F& I0 J
4 y/ e3 b) D* u7 R" g! G......
# P; Z% j) |1 d" U! g# f8 Y
3 s- `) b* H1 d' C每次选择还没处理的元素里最小的元素

        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
" U' K0 n  ?& U- }6 J' {/ V
7 ^" n% Z& ~; q1 k        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
) F' W- Q) c0 s, z
! V/ N6 u* d3 M5 q* O6 K6 ?实现选择排序法
1 G% f7 ^/ h- H+ V/ G# O* Z1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
: }5 _) `8 B* R3 q, f0 n  _2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
$ k# \0 O- G& e3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
7 q/ F1 m! D. w1 @5 K
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
; h# g0 N! B* N" m" t& f! `& M
public class SelectionSort {

- _+ \' [. D8 M* n9 N+ F    public SelectionSort() {
    }
6 h0 _& s( j$ Z! D) M& U, p
" k7 h, y  _  a6 @    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
. h& _! R/ i: r* Z            //选择arr[i...n)中的最小值的索引
0 h0 S( X8 r& z7 Z9 y7 a9 e& ]            int minIndex = i;
9 N6 r. |( ?4 w% M% F            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
" h7 l9 f* K3 h  ?+ ?! d0 U3 _                 if (arr[j]<arr[minIndex]){
1 P* e: u+ I3 w7 @; H                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }
; V* E5 l3 O$ J5 G8 d' _& l
, w! b: A9 `) @8 I    private static void swap(int[] arr, int i, int j) {
        int t = arr;
        arr = arr[j];
        arr[j] = t;
6 B1 d" X) o( u' I    }
0 X& S6 |. K0 I7 f& w- B
( X; j) _( a! c- M  H& `4 F/ ~: `% n    public static void main(String[] args) {
! s, @: [. a: L& k% n/ V! x        int[] arr = {1,4,2,3,6,5};
# c4 p9 K. O) N7 C        SelectionSort.sort(arr);
        for (int item:arr){
6 c6 X* K1 E. R3 ]: ^4 M            System.out.print(item+" ");
5 f1 P. ~" d; j4 C. o- Z        }
    }
}
) U; F3 F9 u- o7 D2 f7 n
# l0 c: h6 J6 S当前只能实现int类型的数组进行排序，因此需要使用到泛型。
# v0 [) n: Z  s: D& }# U$ F
7 L/ }- a; Z$ Z使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
! O' t& P$ F4 w; x1 d
public static <E> void sort(E[] arr)
( f8 B6 G# U( s" d7 x+ D        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
) K7 p- D' F+ Q7 E( B
+ b- u2 F+ g8 _" Epublic class SelectionSort {

    public SelectionSort() {
3 R9 {6 {, M2 _% \, U! f    }

    //
    public static <E extends Comparable<E>> void sort(E[] arr){
/ Z" `) b4 b" `+ r        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
* G; f! i# \: l- b# Y                 if (arr[j].compareTo(arr[minIndex]) < 0){
' |: c- }6 e( O3 d# E0 J7 R                     minIndex = j;
                 }
! b/ ?+ e1 ^9 G7 y* E            }
            //将arr与arr[minIndex]交换位置
" m4 K* M$ _' J1 T$ ]; @            swap(arr,i,minIndex);
$ T# _4 e2 \. W& o2 a% V        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
, d. `# \- C- {: G( P9 A3 ]        arr[j] = t;
    }
- u  E! k" m8 X  q1 Q( r: v: M
& Z" ]# }6 U% n    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
: Q. j' L; X: [- t! k0 l0 G* p        SelectionSort.sort(arr);
+ K- w( j/ `8 K. ?# E        for (int item:arr){
- C8 n1 y1 N: j4 W0 C            System.out.print(item+" ");
. l% P5 p, F% [; B; l; u5 i  g        }
! J$ X, E* @1 f3 k    }
" T. U; f. f; j}

: x) M  f: M! v) s8 I/ h9 n        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

+ x* ]+ ^5 R$ t0 E! R使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

: [9 g1 D+ o7 c0 i7 w. K+ j  Gimport java.util.Objects;
) m* c& b  X* {* n7 X
" M( {3 b: g  F3 b/ E$ q1 F. Tpublic class Student implements Comparable<Student>{
    private String name;
    private int score;
$ y- B5 J, K# W3 Y2 Y: a/ s5 R2 x
7 ]2 W9 E) l$ T- I# A7 m, m3 L
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
2 T5 L* N3 D5 }/ h( O8 T, k2 C    }

    @Override
  h/ M) d" j5 ]# ?    public int compareTo(Student another) {
        /*
) W* e% V; x) k& a6 o- p        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
- n2 d  ]0 d6 U  x        if (this.score<another.score)
            return -1;
2 L9 C6 E) p# c        else if (this.score>another.score)
- G" \  M8 [8 |' S" a' _  g% A- H            return 1;
        return 0;
        //return this.score - another.score
/ U" F5 S: f% s2 o. V    }
- S. y' o5 I) l/ q& j" e
4 O7 h) }) x; v9 N4 s2 c, m6 q) a    @Override
# U9 w+ c9 N9 U9 C* \    public boolean equals(Object student) {
% C( J1 Q# G' M. X5 L# @! t  b        /*
! T" }  Y' Z/ Q$ M0 c3 H4 O        强制转换有可能出现异常，因此需要做出判断
        */
9 g' g: O: T- y0 M# o. ~        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;

6 [$ t; b3 j* ^2 C  }        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;

        /*
" R# `9 w' Q. l        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
8 v1 T; X5 j, f& j0 L        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
1 [2 o3 V7 v6 F* }" }) s/ t        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
1 m8 A+ B" V* i+ B$ a2 q4 g% i6 a         */
( `6 B/ F9 o9 |1 f        if (this.getClass() != student.getClass())
5 [, t2 l5 ~0 }6 V! {) u1 @            return false;

' K/ A# m" \. Q4 d" \        Student another = (Student) student;
2 ^# [! g& b/ E$ h7 H& X  y        return this.name.equals(another.name);//写比较逻辑
    }

' ]: e3 Y7 J; T9 E8 ]    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
! N8 Y  s, `& w! ]0 V/ R: J* m2 q/ z                ", score=" + score +
! a, p8 j2 H8 L6 t! g                '}';
4 ?# H2 ~$ }; O/ C) u& b+ U3 f1 L! u    }
}

主方法实现类：

, ]1 }$ X$ C, u. U7 \public class SelectionSort {
. w# n" k; M5 ?# ~3 _
5 B/ C& G& b, R1 v  X    public SelectionSort() {
    }

0 {+ c8 O+ \( j( k, K8 Q9 |    //
    public static <E extends Comparable<E>> void sort(E[] arr){
; s7 B% Z& @( Z  }6 [  I. E" {        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
" ]" Y1 a* `, J. }& B            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
5 B) J9 P4 Z& c0 Z, S2 E                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
+ h2 F  P) ^' f) Y$ }        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
1 D% R- I8 \2 ^  }+ C1 j' p) f1 [2 d        E t = arr;
( J; Y) k3 {0 n3 D/ n        arr = arr[j];
0 F  _* q2 d9 ?2 `$ N        arr[j] = t;
" N; l/ }8 f, }5 O" c( r2 _3 `: i    }

    public static void main(String[] args) {
3 A+ G# m2 ^9 }: b1 T: I" A        Integer[] arr = {1,4,2,3,6,5};
! U6 `! ~+ P  a% M, c& k: M; s9 |        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
' B3 A1 a3 H7 _        }
        System.out.println();

1 x3 W+ {! Q; u$ i4 {7 T2 `        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};

) d5 M& Z4 j' W8 ^+ a        SelectionSort.sort(students);
        for (Student student:students){
9 v1 v* l# `* H7 X            System.out.println(student+" ");
        }
( Y( @' u5 C( D! {& ^% Z. |
8 c$ m$ O1 Y8 H8 L    }
( s/ s1 f, C: L5 X( I& c: p# e}

复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
  o  r1 q  `- W" P+ f$ T


5 \! z3 X% ~# J$ b5 c1 N首先在ArrayGenerator类当中生成随机数组

    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
' l  Y1 h; `- Q+ ?' Y  A9 q    public static Integer[] generateRandomArray(int n,int bound){
4 s, i8 B! g1 n7 j* ~8 O. L        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
* a5 ?2 S5 x0 E# T' t5 Z$ Q        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
; G  }" B5 ^  n/ L    }
判断这么大数组是否真的排序成功：
$ x% D4 a9 t- Y* [8 ?4 s1 P9 L
public class SortingHelper {
% N: Y9 o7 [6 b9 O+ J& E  O, G    public SortingHelper() {
; l  S% E5 u- o- A    }

1 e" Z0 z( V- |0 n( y    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
" e+ G3 U7 [9 j! z; }" Q        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
                return false;
  p- ~- B, P+ Q) }" k        }
3 R0 ~5 G. q; U, o; t1 [( x! E        return true;
    }
}
在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
, L1 G9 I7 r$ n1 y- V                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
) \1 W0 R1 o- |* j* f            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
! q( g7 N& }  x1 E4 g; _* k" l  B            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
5 J' |& G9 D$ r  U8 I4 x测试时间：

public class SelectionSort {

) i4 i* p5 u: X8 V& |, E7 Q9 h3 M    public SelectionSort() {
7 s; k- |) I/ k( U# V9 ^! h    }
# z! `4 I& r+ A# y) V
" a3 d+ o( n" H$ A* A8 l    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
6 S6 K; U" {: k5 m, u        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
5 r  ~9 u) h* b! X5 x, l            int minIndex = i;
4 J+ \8 q. g& T: \/ u  R: y            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
# K3 q1 ~0 f$ S; W* B                 if (arr[j].compareTo(arr[minIndex]) < 0){
9 K. `  N& E/ Y                     minIndex = j;
) t: p' `4 U, _% v5 `; R. Q' l                 }
            }
+ o6 y6 L9 B) O, v7 L& I6 h            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
' s0 e9 a0 e& A; N5 f    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }

; E  X4 v! y/ m4 t    public static void main(String[] args) {
        int n = 10000;
3 g: }# ^  K" i        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

5 P/ |* p: ~/ U2 C1 q) {7 b, }6 s( F    }
}
9 \; T1 W3 \% g9 h9 t
' S$ V+ m; z( c# Y其中如果要测试两组数组：

' Z  ?+ L! S" _6 s    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
4 i7 O. U  A) x" M            SortingHelper.sortTest("SelectionSort", arr);
5 x6 f' a- @/ W+ b        }
    }
2 z1 ?- ]3 T) c( h! s2 h( ~

可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

9 h( j; _$ s$ l; O) B1 Y2 O/ y

1051373629

感谢楼主的资料