数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2022-9-8 10:10
标题: 算法与数据结构（第二周）——排序基础：选择排序法
算法与数据结构（第二周）——排序基础：选择排序法
目录
0 J1 C$ q5 @' A$ h
选择排序

% @9 L2 I7 v9 a0 t选择排序简单介绍
5 j+ ^: S/ s! n8 M4 p( _$ s2 d
实现选择排序法

% i+ I* R1 C& L5 ]使用带约束的泛型
) a6 A1 o  o. i7 Y. l1 H, N# I) y
使用 Comparable 接口
% C$ {8 w2 X" Q- C, l
复杂度分析
6 z+ W1 j0 U2 ?0 T$ o" {. Y9 f
选择排序
选择排序简单介绍
) d* `* `) C- F0 A& {5 @6 R# O! r先把最小的拿出来

4 u8 @% V: i0 P" a+ x7 {/ W0 [: S! s剩下的，再把最小的拿出来

1 b# e. K$ S" u剩下的，再把最小的拿出来

5 j: R8 F- u  c$ E2 H6 U4 q6 J......

0 M- W8 b" I2 m$ w每次选择还没处理的元素里最小的元素
, J- ~4 {1 F' H0 {" f
( W9 `0 j1 U: U        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

实现选择排序法
, \4 V+ {9 u- a; O; K! y1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
0 d; K3 i) l5 g2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
( X6 z& V+ Q6 j0 I- i
public class SelectionSort {
: D/ f0 H) n3 `' F: x) `
    public SelectionSort() {
    }
$ t/ \0 @- t4 b8 t$ V6 v+ N
    public static void sort(int[] arr){
. X4 E) D" w. J+ h7 Q# [& [6 Q        //arr[0...i)是有序的; arr[i...n) 是无序的s
3 N! |. r5 e5 b: I2 @$ y+ v        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
$ t7 }* N- T5 A4 q8 m+ Q  r( l            int minIndex = i;
            for (int j = i;j < arr.length;j++){
+ m7 K1 V2 o6 z; K5 z( i8 }                //在剩余的元素中找到最小的（比较查找）
2 a- K. `" \5 v5 C8 S7 T: Q                 if (arr[j]<arr[minIndex]){
5 [$ q' Z  \" h* \$ ~! S; j9 T) f$ P! G                     minIndex = j;
/ O  k( ^" E- s, O! p                 }
            }
            //将arr与arr[minIndex]交换位置
1 X( }7 g9 ?4 B) Q, V            swap(arr,i,minIndex);
        }
* P/ n$ T; p' r5 W; q/ m    }
5 v* \; ^/ Y& }& w4 W- ?
    private static void swap(int[] arr, int i, int j) {
2 n- H; V2 ^, o. H        int t = arr;
, L1 P, A9 p4 I& j! b' Q        arr = arr[j];
7 N* A; A9 m! ~' y6 ~3 b3 ^        arr[j] = t;
6 b& N' ^8 P% f- T. s6 L    }

    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
! r2 e; q( \. |6 H% U0 X' w+ i8 q        }
" w; r5 H& F! v. ^& q6 C    }
1 w- R" ^5 y$ V}
& U% ]9 f- d8 J- m+ o! j) Z
当前只能实现int类型的数组进行排序，因此需要使用到泛型。

3 ^, b" X" ?9 d) f: y2 F使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
& Z" P4 j1 ~- C+ L1 I
public static <E> void sort(E[] arr)
/ \% H8 g) M9 C        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
' D% J4 }1 }7 r3 `
public class SelectionSort {
0 p; j9 A1 }. h0 @7 `/ ]7 Z
    public SelectionSort() {
    }

    //
    public static <E extends Comparable<E>> void sort(E[] arr){
8 p3 u! Y: i" V: ~' R2 W+ C, \        //arr[0...i)是有序的; arr[i...n) 是无序的s
" \1 Y8 }" t  }! b* @/ S        for (int i = 0; i < arr.length; i++) {
  X: M1 Z& z$ R( a            //选择arr[i...n)中的最小值的索引
2 h! a' |* |9 h1 ?: e1 q$ P            int minIndex = i;
; Z7 s4 n8 ?) ]" m- t; _5 ~  b5 ]  L            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
5 a8 A% b2 e0 z+ t" q8 n  u# n            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
" L+ W0 \8 Z! ~% r; q2 `6 |        }
    }
( ~) D) t9 i$ q/ C4 R' ?0 E
    private static <E> void swap(E[] arr, int i, int j) {
; B% q3 Y8 m4 M% s2 G  w0 S        E t = arr;
5 q+ I) x+ W9 m) U* E  f        arr = arr[j];
: H9 z0 n6 A. N        arr[j] = t;
    }

    public static void main(String[] args) {
( ?- s/ V; \# O! C        Integer[] arr = {1,4,2,3,6,5};
4 R' }8 b4 Y9 G, K+ M9 M        SelectionSort.sort(arr);
; i( }1 Y( }5 w- J% u( ^        for (int item:arr){
            System.out.print(item+" ");
8 |. j8 L' e5 h0 C+ h9 G        }
    }
}

5 t* @0 F# L- G, j        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

使用 Comparable 接口
5 E9 L5 {9 Z" I+ z  _        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
# j7 [! F2 f( d+ W9 ~$ s
2 o: ?4 p+ O) Z/ u0 bimport java.util.Objects;
0 g- o3 I* [2 b; ]- H* K* M
public class Student implements Comparable<Student>{
* @5 n* d  h; B- R1 V6 N    private String name;
    private int score;

8 i$ @1 H6 L: ^8 H9 d
1 I1 \9 S0 \. b/ c7 P    public Student(String name, int score) {
        this.name = name;
# g3 Q6 ]. P2 s5 q1 Z4 z, }7 S) S5 O' t        this.score = score;
# I" C: F6 R% b3 t    }

    @Override
    public int compareTo(Student another) {
        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
; r. A$ b0 H: t6 i0 k, `        if (this.score<another.score)
            return -1;
, M3 D) D7 g" @/ |% s' V        else if (this.score>another.score)
3 S$ Z4 S/ z* K            return 1;
        return 0;
        //return this.score - another.score
4 f" U) Q- Z4 [7 }* }( J    }

9 p: {/ c7 d, X% X: d    @Override
    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
& S& T6 B( r8 ^, C+ m, M        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;

        if (student == null)//如果传入的对象为空的话，则直接为false即可
9 d, V) N9 w4 k( I! ^            return false;
8 O$ |( m' v+ Q& b$ H+ A1 n5 g
        /*
        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
& u% U4 L7 x$ m  @1 J; s1 D         */
        if (this.getClass() != student.getClass())
            return false;

* B6 A/ A" \5 N* c2 {: a2 \        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
" [5 `; Z5 S2 D    }
4 h0 e# e: B6 l, F- p% R" R
    @Override
1 `5 V. S$ ]$ p6 a    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
                '}';
+ I* x6 Q' C% [; I    }
, x) `2 X7 e. H  B" M, ~- h& k}
8 T" X& U5 M& p5 v7 i# y( C
主方法实现类：

public class SelectionSort {

    public SelectionSort() {
    }

! k1 f! B2 Z; ~    //
  x/ q( e3 K6 V$ p& q3 i3 {" t    public static <E extends Comparable<E>> void sort(E[] arr){
$ f& S9 Y# q) J9 x! K# ]        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
, e3 \1 x7 `6 P4 D; c$ ^            //选择arr[i...n)中的最小值的索引
2 g/ \0 u) g3 L8 B6 Z/ E( R8 A            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
2 n: p# Q9 n7 |8 j5 _% w; u# y                 }
            }
            //将arr与arr[minIndex]交换位置
; f. Z2 R$ ]7 P            swap(arr,i,minIndex);
        }
    }
' \9 {- f, X6 h) D* e3 u# O
    private static <E> void swap(E[] arr, int i, int j) {
, O% e$ P/ s$ _  r$ ~        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }
+ J+ a$ T  D4 ?, C, q( l
    public static void main(String[] args) {
9 ]* u5 j2 Z9 y3 Z3 |        Integer[] arr = {1,4,2,3,6,5};
" q" X3 t8 l: e" z        SelectionSort.sort(arr);
/ B) Y3 ^- C% j7 J: {% ^/ T! ~# A        for (int item:arr){
8 l& |+ k6 g* w% Z/ C' i- K, r            System.out.print(item+" ");
        }
9 X3 `; \1 \+ Q! g/ p1 t        System.out.println();
1 {9 G  C5 Q+ \$ V8 N1 z7 o
4 f' t, ~/ V) n* T5 ^" |        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
- Z* N+ x* c8 u7 E  L6 ^3 a, q                              new Student("xiaoming",66)};
( N+ \9 z& V, K  d
/ j, w/ Z; l+ h+ N) M6 S% T        SelectionSort.sort(students);
- Y/ n* R3 e5 g& K        for (Student student:students){
            System.out.println(student+" ");
        }
$ {% I  P6 s% z$ I' B) x  O
    }
1 Q9 T3 h  S  K: J, V6 [3 e4 [* m}

复杂度分析
1 y9 g3 _) V4 H: `! ^        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
; o1 S. N+ q# k1 s" c& x1 S1 [

- G) P/ n1 B1 X
首先在ArrayGenerator类当中生成随机数组

    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
    public static Integer[] generateRandomArray(int n,int bound){
0 B# h: n8 F" k, }5 o% t        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
    }
判断这么大数组是否真的排序成功：
9 ^: K: K: R. |
public class SortingHelper {
    public SortingHelper() {
    }
. H4 ^9 v. R& r' d
    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
0 @& U4 P  V$ w        for (int i = 1;i<arr.length;i++){
. P- Z7 r( a2 P: p* g. x; B8 S            if (arr[i-1].compareTo(arr)>0)
                return false;
# m+ |" g. _/ {% S0 S2 O        }
        return true;
    }
$ c& k/ K9 v- E/ ^: z& P7 c}
在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
) c! ^  r$ }3 l$ X# J            long startTime = System.nanoTime();
  W; P! v4 ~# \  }) q            if(sortname.equals("SelectionSort"))
2 W( `# z4 s1 b3 o' Q% R. E                SelectionSort.sort(arr);
1 T% \8 \2 X! Z+ {/ s! |) o# o% O            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
0 w3 _- @. U! H3 X/ v. Z                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
1 q: m" t6 [  [' S' s( u    }
测试时间：
9 q7 @/ W+ Q6 k& |/ L% `) r- b2 [7 K/ r
public class SelectionSort {

7 v' q' |0 y" g5 N8 V8 ?+ H- y    public SelectionSort() {
    }

! f8 `9 ]+ M+ J1 x  q    //
    public static <E extends Comparable<E>> void sort(E[] arr){
5 C  g; d$ E5 d7 \4 L        //arr[0...i)是有序的; arr[i...n) 是无序的s
! r3 G: H& r- s: K) l6 f9 O4 n4 W        for (int i = 0; i < arr.length; i++) {
# i- M5 k. v& t% T! R. ^, Q* h            //选择arr[i...n)中的最小值的索引
" w- R+ N. a! _0 }- P            int minIndex = i;
            for (int j = i;j < arr.length;j++){
/ \  z# d# h$ u' }8 Y                //在剩余的元素中找到最小的（比较查找）
. S- T" G5 i$ w4 L) D* l; q! b8 t2 i                 if (arr[j].compareTo(arr[minIndex]) < 0){
# P7 e, t7 C1 j$ g                     minIndex = j;
4 F* y* t) B& p/ ]/ C# c                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
( ?& Z4 u% x! B" I        }
    }

; P1 k: M, s! o7 m" x    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
3 X, v1 m5 m5 g, e        arr = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
6 w' e6 k0 h3 G        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
4 }" b# c; F7 Q" N& `. O        SortingHelper.sortTest("SelectionSort", arr);

    }
8 ~' M6 d  i3 J" P% X, r8 A" L}

2 P6 j2 N# A# @' m1 t其中如果要测试两组数组：
1 o3 X% I0 {: W8 d' X
    public static void main(String[] args) {
9 Q5 u0 @' ^9 _- y" I        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
* l  _2 @4 |  |# U# }6 E2 E# l            SortingHelper.sortTest("SelectionSort", arr);
        }
    }
3 N' k* s! k& x' ]/ O, ~6 i# a
7 W2 b) O# n* p$ g8 r
/ \  w) e( i2 w4 c 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
! L; a" L6 P& V9 D0 q. l————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. O' i/ p% u" Z8 f$ v8 O原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
: j/ b1 ]0 y& f3 U. A' P

---

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

---

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

Powered by Discuz! X2.5