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

杨利霞

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

8 o/ g: E* o! y" n) ?! d  B选择排序

# U8 k% h) w7 x  Z) @2 c选择排序简单介绍
8 A! d3 c7 E' R$ j' @# d
实现选择排序法

使用带约束的泛型

使用 Comparable 接口

复杂度分析

选择排序
8 j* ~' J" x! x2 S5 Q选择排序简单介绍
先把最小的拿出来
$ y% V1 c# }% p
剩下的，再把最小的拿出来
+ B0 I% r  G1 Z+ [, @
剩下的，再把最小的拿出来

......

2 D0 L: N' i5 I5 t3 m2 ^每次选择还没处理的元素里最小的元素

        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
! s0 U1 x1 I* k- E, O5 P8 y
# j: `# |& f& d9 s$ a) R: Y实现选择排序法
9 P% p* f7 |2 B$ s4 E( z' G& ]1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
$ `2 o# E- W/ Y2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
4 V( D/ D$ s# E" e3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

3 U3 I  H4 ?5 S  [/ [7 z        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

& q+ A6 j( J7 E; A2 P* Y" s/ @public class SelectionSort {
. R$ ?' z) i5 I
6 c7 q' c# R/ s" I7 h2 c1 [; g    public SelectionSort() {
    }

    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
9 \0 B& F: C7 P- m. X# V        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
# R7 V  \- X# H8 v                     minIndex = j;
3 u( g7 G9 ?' v& A7 T5 |. M$ r                 }
            }
3 k* E8 Q( Q$ b. n! z7 k" _            //将arr与arr[minIndex]交换位置
8 B# Q! l% f/ K+ w) T7 n8 I            swap(arr,i,minIndex);
        }
    }
" w* Q' i- w8 C: v* h1 d, J
) ?* K( G+ C) c: d( c    private static void swap(int[] arr, int i, int j) {
- a0 l9 B1 m% U, N4 F' q) X1 A        int t = arr;
+ ?5 Y0 Y3 A# ?0 C/ t        arr = arr[j];
        arr[j] = t;
% o+ ]- R4 ]) [; N% u    }
1 F$ m; b' o- a6 X+ E5 \
    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
9 N- B4 i$ Y: a9 B* E        for (int item:arr){
  {9 A4 ~3 B) f7 a- L. O            System.out.print(item+" ");
: w* V0 h. K0 `1 _4 i3 ?* K0 u. N        }
8 U& s) u7 \5 Y9 T% r, q    }
}
4 R7 j) }9 g/ U7 N/ S
3 D& `7 X' h$ p3 }6 m- j当前只能实现int类型的数组进行排序，因此需要使用到泛型。

使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
2 f+ i+ i* }0 o, M/ f! l
6 h) Q8 C2 V4 J/ y$ R0 q" Z/ Opublic static <E> void sort(E[] arr)
, r5 v7 F/ m7 h        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

) }! j. ]; V/ ]: X2 h- ppublic class SelectionSort {
' Z* U/ n$ D' s; F# O: h1 K$ _
    public SelectionSort() {
    }
4 H& Q2 W$ `- V2 G
; [; r/ f# `: g6 x6 c& U    //
    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++) {
. `8 K0 t* _" W# D9 v6 g            //选择arr[i...n)中的最小值的索引
& y4 A, n" }+ F" P            int minIndex = i;
, X& k8 C  [1 t, Y4 Y8 H            for (int j = i;j < arr.length;j++){
% p1 v' A, x+ ]                //在剩余的元素中找到最小的（比较查找）
* T7 Q+ ]5 P! _2 o7 L/ J4 q                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
' b; |6 m( D8 J: }4 o% V            swap(arr,i,minIndex);
( I8 K) r) l/ c        }
    }

* S# _7 R+ W) G8 d    private static <E> void swap(E[] arr, int i, int j) {
+ ^; g! ^- M" J# Z% U        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }
& k) {6 d4 i  i: |: f3 C" H# `
    public static void main(String[] args) {
- a  A+ R3 A( e5 S) X6 N# V& M        Integer[] arr = {1,4,2,3,6,5};
2 i0 y1 Y' c' J, j        SelectionSort.sort(arr);
0 l# S! k% S) C  N( g+ Z! {        for (int item:arr){
9 i. D7 o. h5 ]' I6 P& @% }            System.out.print(item+" ");
4 r  L- Q) x* l  {        }
* }  d  R/ [. Y& \! p8 q    }
% h- o5 F2 C6 s7 m& ~# C7 V}
; A/ p3 o& q$ }' Q7 X5 L
: g+ N% z2 i$ w. W9 N" d        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
4 C! b4 E5 ~9 R& _
5 [' V- R1 K$ l  i8 G使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

* y: p' ^( x3 w& Z7 T5 j4 rimport java.util.Objects;
! b5 Y2 D' j. ^+ e
public class Student implements Comparable<Student>{
; F+ {+ m+ r8 l3 W! W1 @0 C3 ?    private String name;
" `( l: a' {+ f4 [    private int score;


    public Student(String name, int score) {
. e% C: m. c3 S$ \3 F# F- l        this.name = name;
        this.score = score;
6 C$ R% V* a! {- I3 V    }
+ m2 c" W! }2 o
% r, D: z0 s4 o8 H- R# ]    @Override
  H$ X7 b1 }5 n! r; C/ E9 @    public int compareTo(Student another) {
        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
( m' ?; p0 U6 ]* N$ n         */
! M2 p9 F/ k: \6 Z& |$ i5 o        if (this.score<another.score)
            return -1;
  V* M% r2 h0 ~6 P# U  Y5 N' k" ^        else if (this.score>another.score)
0 P7 o2 |2 W7 H7 D- [: \! C0 ~            return 1;
        return 0;
        //return this.score - another.score
5 q' L% ]+ H- G1 Q1 L/ |" {9 e    }
( o. m& _' F% `7 m6 D
    @Override
    public boolean equals(Object student) {
- y. N- t9 T* v  V- H        /*
2 {# ?% y# r0 I6 w) s, m; A        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;
/ S3 E; ~) V! t& x2 E  d  [; T
        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;
7 R: S: [0 [, p: C  a+ M6 W$ `
        /*
. k$ B7 E' h8 n8 u        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
0 L8 s7 R" N+ A4 ?9 d, s        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
5 h3 t' b: r6 s  k        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
% E8 P! c2 F) g3 C         */
        if (this.getClass() != student.getClass())
            return false;

        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }

    @Override
3 K6 ?. E$ Q8 R0 E0 s    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
; K2 g$ @0 o% D- ^$ k                ", score=" + score +
3 V/ r+ G8 S5 U* h1 L. l0 q                '}';
9 h1 v' Q, q7 N7 c    }
9 b' \/ m& c3 q8 I! l- f. N- a}
; \+ C6 K& B. T" {" _7 B, l
  a/ ]1 Q6 n. l- P9 E$ X1 z2 I9 F4 P主方法实现类：

public class SelectionSort {

5 ]' ~% W5 f- A- P# g9 O( t1 r: W    public SelectionSort() {
    }
8 G$ ~% m1 m2 N% n& @
5 M) _2 g8 J* s0 X* b9 X* i4 W! O2 Z5 e    //
! |) G* I' c$ G5 i; O    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)中的最小值的索引
  j4 r6 B& v+ P# j            int minIndex = i;
            for (int j = i;j < arr.length;j++){
4 l8 y" d8 W4 U+ ]                //在剩余的元素中找到最小的（比较查找）
1 e8 b. v. R. e2 d/ V                 if (arr[j].compareTo(arr[minIndex]) < 0){
8 b* b& D* ~( |2 G. Q# _8 Y1 ~                     minIndex = j;
1 i& E% U! x6 P$ {& \2 w                 }
            }
            //将arr与arr[minIndex]交换位置
+ E! a& }0 }5 S* r: Z% M- U3 ?            swap(arr,i,minIndex);
" x; v* v. k' M" d        }
' h: F/ D' r; x0 d6 w( ]    }
" K- U( ^& I2 w" J4 w3 i/ x
0 D: e  l! T  U* S1 J! J    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
2 O4 r* D5 Y  [4 P        arr[j] = t;
, v, t, v% b$ Y$ m( n! _3 l    }

    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
# ^6 X; [* ^# ^2 B8 ~        SelectionSort.sort(arr);
        for (int item:arr){
0 X4 u7 [* D' D/ Y& [            System.out.print(item+" ");
8 F# H7 j  @9 z1 c  s/ ~* S% B5 r: L) G        }
        System.out.println();
8 J# P& k6 m% y2 F
4 f6 t# Q& S" L5 [5 W        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};

        SelectionSort.sort(students);
        for (Student student:students){
            System.out.println(student+" ");
        }

, F6 ]2 B# z+ ]' K3 ~    }
}

复杂度分析
: T8 f  v+ W+ v: Q9 q        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
; s1 E) C' G6 P
6 t" k% C" X6 L; z: t* A" ]

' Z+ d* g) F$ j- `首先在ArrayGenerator类当中生成随机数组
5 S' F5 R. a6 |/ h/ C& O8 t( y
- {- |) X& m' a6 }' d    /*
% q; S' \4 S( g0 L. O* X  _    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
  J8 Q( R" i9 @" E    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
% F/ a: U0 _2 B+ _6 c        Random rnd = new Random( );
7 {: r& v/ S+ Y. h5 Z! e        for(int i = 0; i< n;i++)
# Z/ L/ w- l" N* e. \5 l* p            arr = rnd.nextInt(bound);
4 K' N) M! c) n! x  C        return arr;
0 h% z0 [4 ?& R& \# o3 t    }
判断这么大数组是否真的排序成功：

public class SortingHelper {
    public SortingHelper() {
6 k$ ~- B, I/ Z- \. r6 |6 w    }
0 P- e7 f6 K5 n/ l4 p
5 \( |3 z3 Z! w3 a+ x9 T+ J    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
- d% z  I1 h* G& g2 L3 e. P        //判断数组前一个元素是否小于后一个元素
+ }$ a& ?+ w# k  J7 Y4 X0 ^8 H3 m! |        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
                return false;
5 d3 g; j7 H" j$ @        }
        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"))
! ]/ Z- X# _9 @3 _$ [                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
3 ~1 K) l+ m" y8 h            double time = (endTime - startTime) / 1000000000.0;
5 D  R  j3 x. ]            if(!SortingHelper.isSorted(arr))
- O; C# X- t+ S5 y7 N$ [- x                throw new RuntimeException(sortname + "failed");
% C. L3 U' ?- ]# y! I            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
! @8 e/ E$ g0 ^, A. F    }
测试时间：

public class SelectionSort {

    public SelectionSort() {
6 I5 i9 j# e9 y, x) Y# y8 l    }

, l) R( x2 G2 y    //
    public static <E extends Comparable<E>> void sort(E[] arr){
8 y# N$ a0 d+ O) z8 G        //arr[0...i)是有序的; arr[i...n) 是无序的s
  B* T( }$ Y  a, E$ w. O+ H/ a        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
1 L! m) w/ x  F( l  `2 V2 c            for (int j = i;j < arr.length;j++){
) H5 e/ J# |5 ~# v" W                //在剩余的元素中找到最小的（比较查找）
, V; F1 j+ A7 }& b                 if (arr[j].compareTo(arr[minIndex]) < 0){
- S  m. a) y! H) m                     minIndex = j;
& B: N7 C' ]  c. |' h                 }
            }
# W: C/ ?9 ]0 @, r7 s            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
8 f" j+ p9 B9 N7 W        }
    }
% N' F2 }$ s9 P- B$ z
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
2 M8 n1 j( U' _1 A2 |        arr = arr[j];
% I6 O- f! w: ?  y+ ~        arr[j] = t;
    }
1 L4 ]; ^4 |, E2 S  X
    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
- r" f) n& J* O# d7 o        SortingHelper.sortTest("SelectionSort", arr);
2 ?$ w+ \1 c1 B* N" p$ [, v5 z- C9 ]
    }
}
% V2 [( L0 {9 w3 S7 s5 D9 {
其中如果要测试两组数组：
; n  C2 ^; A- f9 {
# L! |1 H5 |' n; a7 B. E% }    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
. V9 g  q% i3 e) w: m( ]4 E        for (int n:dataSize){
& U% s) Q6 e: h: |) F            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
% m- h3 N( f5 z! i( V        }
" P% H2 ]4 A- G, ~6 J# T    }

7 C6 `& Q$ S5 B" y" s
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
# e4 u! X3 c3 P2 c: p$ V( B版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 U" O6 l0 r! z& m/ l2 f原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

! p+ |1 C4 s3 K  p, }! m1 y
6 }7 W9 E$ D! N2 b8 A

1051373629

感谢楼主的资料
( \2 B& w: A! c