数学建模社区-数学中国

标题: 算法与数据结构（第二周）——排序基础：选择排序法 [打印本页]

---

作者: 杨利霞    时间: 2022-9-8 10:10
标题: 算法与数据结构（第二周）——排序基础：选择排序法
算法与数据结构（第二周）——排序基础：选择排序法
目录
& ]' C1 y! s4 L/ i. o/ e, L5 w
选择排序

$ Y- M2 x% G1 I9 ?* r选择排序简单介绍
7 Z3 c" S! ~7 ]! t% w* `: v( Z
, A2 h0 A/ n; j0 d! V8 N实现选择排序法

使用带约束的泛型

使用 Comparable 接口
1 d! H* T* q0 N
3 ~& z5 [  |* G4 Q" Z复杂度分析

+ ]5 ~  f% ^8 u4 a- d+ s  }! F选择排序
, y; |4 @$ `( N1 f选择排序简单介绍
& A  s8 N# ?: I# u; e先把最小的拿出来

剩下的，再把最小的拿出来

剩下的，再把最小的拿出来

......

每次选择还没处理的元素里最小的元素
' l. z. f9 ?3 s# S5 \) i
  q: P9 {$ M0 o  f8 x        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

2 X5 k$ T' L5 S6 U8 ~: {7 N        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

实现选择排序法
5 h  B: v) r8 s1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
7 c4 @' l& M% F" |5 I' H2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

* F' g2 o# p7 o5 W& }1 Q% |        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
" }3 t8 T' R: B9 n- t7 V, P
( _5 H9 v# Z, R) ppublic class SelectionSort {
9 P- r' l2 ]" B" }/ K  H
    public SelectionSort() {
    }

! ?9 E* D1 i' W/ t7 u  p    public static void sort(int[] arr){
* ?2 H3 L/ J9 l, E  G        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
8 ?3 ], p$ \; ~: o: `, X0 Z            //选择arr[i...n)中的最小值的索引
" g% s& P2 L7 S            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
7 R6 Q- ?' f1 }$ j2 K1 M* b$ v                     minIndex = j;
                 }
1 C1 ]2 w) c3 d4 |; h            }
4 i- q% w: y7 w3 G8 v            //将arr与arr[minIndex]交换位置
# L" H: F8 B! z1 m) h, n            swap(arr,i,minIndex);
0 x3 q6 {8 ?+ g) M8 r        }
    }

$ R& P2 g1 s* P  X3 l    private static void swap(int[] arr, int i, int j) {
1 f1 D- ]- n- e! d* f( o        int t = arr;
        arr = arr[j];
- h! C$ x1 @2 w9 M        arr[j] = t;
1 Q8 Q; o0 z. s- @    }
4 S" B0 b8 U. r( L
    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
! ^2 W( f* W( ?, _: M        for (int item:arr){
% q8 a/ e! R' R8 m            System.out.print(item+" ");
8 I8 `$ u/ g. @# R6 b4 ]; p( V        }
( ?) Y" c% b/ F8 x5 }$ F    }
/ Y4 z9 ^/ A. f( T; u& P& i3 k: D}

- W) M1 c2 P0 s, N5 W当前只能实现int类型的数组进行排序，因此需要使用到泛型。
1 ^6 M( @( j- [7 o$ ~7 J2 p9 z
" A2 R; ]/ P( }% F2 \/ }# `使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
9 w: r/ `1 I" e: j1 C% N
( k- f: f' g4 w  y- l9 Fpublic static <E> void sort(E[] arr)
- o5 @' g( v! Q+ C        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
; g" X0 U+ P6 Z7 J- y0 ^3 z; w
; `: v4 y+ ^7 ~public class SelectionSort {

! j! r7 x  i9 ?# m    public SelectionSort() {
3 T! a5 Y, X, z    }

( }; d. Y7 Q0 \5 ]) w4 f1 A    //
6 U" T  ^' _( P    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
' L1 q- ^6 U4 X; N        for (int i = 0; i < arr.length; i++) {
7 G- x0 Z# w9 O6 W" k8 b; P' f3 K            //选择arr[i...n)中的最小值的索引
! k, n( {0 y# _0 y            int minIndex = i;
            for (int j = i;j < arr.length;j++){
7 X& K+ c+ a0 o                //在剩余的元素中找到最小的（比较查找）
: `9 @; t. b# q8 `                 if (arr[j].compareTo(arr[minIndex]) < 0){
4 }! P1 T8 H6 Z: P                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
; a2 m1 v  A3 {6 E& Z" H        }
    }

9 V1 p  z! j( h2 W6 \, V    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
; e( ?. Q4 {! t0 p5 N* l5 U3 q( ]0 B        arr = arr[j];
        arr[j] = t;
    }
; i- I' c9 E" S. }: J
# J; \+ \6 R3 K, i% F1 K0 F    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
7 J# c+ l. Q- i, w- f1 n        for (int item:arr){
: v9 ~  y, f% j, G2 t$ U            System.out.print(item+" ");
+ y1 ^& C7 ~8 O/ B+ H! S        }
    }
5 H9 G4 |1 X* t) N; [* ^. a}
$ V  @: M" y4 s. j) b/ I5 ?/ E
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
, ^+ C/ o! c1 g: b" n0 J) M( A
. E* i* W* k1 {) J使用 Comparable 接口
& @+ j; Q+ u7 D/ L4 g% [& _: O        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

' U5 Y, Z& e5 u0 x3 rimport java.util.Objects;
: R. i' d0 r. b" {, n
public class Student implements Comparable<Student>{
' r0 t& J# A) \7 Z2 Y, f. s( _4 X    private String name;
/ M! _  A5 M8 O' X! |    private int score;
" R* d& ?+ Z( \; u- Y
! ~+ X6 i/ W1 |4 C. W( G1 \
    public Student(String name, int score) {
( ^+ b6 W- }. l        this.name = name;
        this.score = score;
4 g1 F9 x; y9 i$ G7 q+ ^4 H    }
1 W- }' P7 p* O3 \- n7 a2 w. G
    @Override
4 \( L5 z2 }2 F    public int compareTo(Student another) {
4 C0 A# p% z8 y- V        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
! s0 S, y# K* M( r         */
$ y- H  {! _3 M/ H: |2 R4 ]* @        if (this.score<another.score)
            return -1;
$ e9 h2 D6 z, D7 n& U$ h8 B        else if (this.score>another.score)
1 G, i* Q# f1 a4 c+ ~5 h0 a7 _            return 1;
9 S1 u4 B5 ^1 B' M# [# X9 j0 L* L( F        return 0;
% k3 n  E4 M+ `/ c$ _+ S        //return this.score - another.score
    }

4 ^! t- w0 Q, K3 g" P! W4 B    @Override
    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
# \* A. J0 T3 D$ x        */
6 W. V  U% w/ O& C% m3 {, {$ H% W        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;

        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;

8 |. T9 g3 U& g8 n+ h        /*
" z6 v" z) W0 q; f        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
* k0 O! O% ~/ M        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
        if (this.getClass() != student.getClass())
/ Y  q0 l+ ~" v! Z( w            return false;
0 o, t  C' ]2 A9 ~' x5 ], A7 g
) D1 v3 A9 W" M1 ~! m: L7 r        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }
0 L; e# V1 X3 S0 v' V
    @Override
& h5 n; ^7 Q+ r( c6 A% C; d2 t    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
1 G  A) ^8 [" T; u                '}';
* B& }& v6 w* R+ |7 t    }
}
* w  b6 o+ Y, J; O* s, k9 v$ D
9 p" A$ {) i, d! q主方法实现类：

$ [- D$ D& t, J9 ]' U" ppublic class SelectionSort {
+ w' v, D$ n% j8 Z  }4 ?  F* Z
    public SelectionSort() {
    }
2 ~4 P) m/ I( _1 A0 M
  H$ \  e% b& H; b0 I    //
    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)中的最小值的索引
* l3 ~( |8 m* C4 R) d3 U% b+ K            int minIndex = i;
: @5 p# Z5 Z1 t, @! ~6 q3 [& S            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
1 O, L. j# d  F6 H; l2 |3 U. C                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
            }
% L9 u9 _& n' w1 R            //将arr与arr[minIndex]交换位置
. m. `% H5 S+ S) U7 ]! ^9 x2 `            swap(arr,i,minIndex);
* ]& K# J3 e) X* e6 V# v9 t        }
    }

: P% \! O. A5 C    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
' T) q" _0 }6 D- }$ \  {, Y* S        arr[j] = t;
    }
0 i5 ?6 c7 i8 \0 K4 g. W
" t! {* U- \4 ~" H6 R    public static void main(String[] args) {
# ]! t, C- j/ Y+ X        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
- w6 Y- u0 k4 B, W. G# \) @        }
        System.out.println();

9 |3 y5 B- Y' Y* f$ X; F        Student[] students = {new Student("Alice",98),
- W: J6 |( J' T7 r, Q$ E                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
0 O! ^) x, E3 Z3 ~! u
        SelectionSort.sort(students);
8 z" P' Z- Z6 B2 L        for (Student student:students){
( \- [& t3 z' f. u  |            System.out.println(student+" ");
        }
: ]1 K7 o9 w' D: ^
" x; U. d$ ^, I+ b    }
}

复杂度分析
: [; d( F9 R, H        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
- b* U+ ~& h& E( @9 P( v! f

/ Y3 o$ U9 Q9 y6 L* L" z- [
- r  O0 j4 H8 x( f4 q- H" K首先在ArrayGenerator类当中生成随机数组

    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
( \$ D- ~4 t2 |5 T) z& q  N* A     */
0 `3 L4 d' e' r4 f+ R5 ?' ]( r    public static Integer[] generateRandomArray(int n,int bound){
1 z. }8 o% b) s+ @& n1 J& T        Integer[] arr = new Integer[n];
# O7 ]0 ~. u+ i/ b: X* y/ C        Random rnd = new Random( );
3 O! k8 o7 M" N, X8 ~$ H8 \( f/ \        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
    }
判断这么大数组是否真的排序成功：

public class SortingHelper {
5 Y% y' L% q" m    public SortingHelper() {
    }
4 c7 K5 ~- a  [9 B1 j0 `
+ F; X9 D$ G, k: b  J    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
) o2 c6 u1 h  n/ E) _9 |- h        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
                return false;
  }  F) @! `6 Q) o; a  `        }
0 j- k5 M( S" H2 M- X        return true;
    }
}
$ P0 Q7 P: W: R8 ?: o1 t在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
8 h  J5 O" T" p' n, J    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
# W6 O" Y3 S' x' V: o: j            long startTime = System.nanoTime();
- W' g4 a' A9 c2 M0 m( K& ~            if(sortname.equals("SelectionSort"))
  J* _- t2 A% J4 S& g( ~% G6 n4 {                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
  A5 c, B- o$ L1 U            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
/ v! U) b, ?: h! z; e3 M6 L; C% W- V3 A            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
: x2 y2 c$ ?# L! q3 y测试时间：
6 S/ k& `8 f: }2 X
public class SelectionSort {

    public SelectionSort() {
    }

    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
+ ]" V+ U! _% ^1 E/ E        for (int i = 0; i < arr.length; i++) {
. ?6 m' c/ t, @$ c: S4 t& @            //选择arr[i...n)中的最小值的索引
% ^- B; k- T1 s, E            int minIndex = i;
            for (int j = i;j < arr.length;j++){
( j4 I' H; {( W- u                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
6 C& Q, m& ?- ^+ m  Z$ E2 w" q                 }
            }
0 |% y3 C" n. w; }6 Q            //将arr与arr[minIndex]交换位置
7 U% y$ Z: ~$ u3 S# E            swap(arr,i,minIndex);
        }
    }

0 n- h, y4 W1 F" ]    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
, ^# O; U8 T. ]        arr = arr[j];
  L0 w, D. X$ K% R        arr[j] = t;
3 J7 I- ^/ Y: V, {8 L    }
" ?1 S5 d* E; f
- a9 }" L3 b4 G# m7 W# ?* w    public static void main(String[] args) {
        int n = 10000;
( N1 x6 l5 R1 d        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
}
# Y5 Y  g7 \7 a% z2 `8 F
) M! D5 m3 R$ V( h其中如果要测试两组数组：
" ]: \3 b7 `) G- Q$ I$ ^' y2 Z3 J
    public static void main(String[] args) {
7 J0 [6 Q9 k6 }& M# n/ n" {# K        int[] dataSize = {10000,100000};
        for (int n:dataSize){
( E. M9 W6 n, O6 d# z            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
7 \% z% N5 N% t- G            SortingHelper.sortTest("SelectionSort", arr);
% y' ?6 @+ _# ]$ x* N        }
. v! c8 i" k, H: P# i1 K/ a    }


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

: n! _, y& \9 X$ F; ?
8 w% Y2 h9 ^: o- X. }

---

作者: 1051373629    时间: 2022-10-22 09:41
感谢楼主的资料

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5