数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2022-9-8 10:10
标题: 算法与数据结构（第二周）——排序基础：选择排序法
算法与数据结构（第二周）——排序基础：选择排序法
目录
1 p# P7 W; B- l: {6 @( ?4 Z; i
选择排序

. i) e2 G* i; n选择排序简单介绍

实现选择排序法
: X& \8 U1 N! h6 E0 {
8 Z# k& n7 ]; b2 u使用带约束的泛型
# y* O0 S1 L3 |; n: P  t! T
! D, i3 D, F2 `, B  ~" v1 _使用 Comparable 接口
  @* i9 N( q7 |2 }0 Q& `
复杂度分析

选择排序
选择排序简单介绍
& R# T# h4 `! K  L# `6 u5 \先把最小的拿出来

" i/ m7 U' Q( g剩下的，再把最小的拿出来

7 v, p! B) b0 h7 i& I, m: c剩下的，再把最小的拿出来
, V' t9 X2 ?2 n6 U" d3 y8 _
  [: i% [* ?9 M+ O/ S......

每次选择还没处理的元素里最小的元素
/ @; B. g  N4 s& h% J4 A
. ^: B% e. T4 C        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

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

, }$ v2 _$ B. u: N* v$ r实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
+ b& k' O; W1 S7 m9 K5 H( R7 m4 m8 {2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
* b1 [% I6 o8 M3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

* v' p- _$ o# d9 r        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
  ?6 P8 O$ x7 C) r. F7 Q" D
/ t/ r, E: l3 v$ C6 Qpublic class SelectionSort {

    public SelectionSort() {
    }

    public static void sort(int[] arr){
5 @! z; M5 h# U0 c        //arr[0...i)是有序的; arr[i...n) 是无序的s
' W& N2 M: y0 I1 M+ F        for (int i = 0; i < arr.length; i++) {
1 t% G6 @2 z$ \( a- _' |- g            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
: m: R! G. [+ s                //在剩余的元素中找到最小的（比较查找）
. e) P# Y' [; O( T! e/ b                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
                 }
            }
$ e* W: w2 W  Q) {. L! Z            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }

4 o& W8 I, s, M& v8 |/ X& P: w2 i) ?    private static void swap(int[] arr, int i, int j) {
        int t = arr;
$ l: ]9 ]1 ]- @- q7 K( F' R        arr = arr[j];
        arr[j] = t;
( g8 m1 y! q+ L* I! G% P  U7 u! n    }

; Z# c5 @. k4 s/ S4 ]1 E    public static void main(String[] args) {
; P3 ]1 O+ ^# m- J        int[] arr = {1,4,2,3,6,5};
- t9 e) Q' {0 A0 H        SelectionSort.sort(arr);
2 J6 s# v- v2 l0 I        for (int item:arr){
            System.out.print(item+" ");
+ P. L$ B0 f: Z5 i        }
    }
# h- Q- X7 B0 U1 O6 V" P}
% h1 ]5 e! i& ^' `
当前只能实现int类型的数组进行排序，因此需要使用到泛型。
8 q$ J& X( C6 E* d* e
使用带约束的泛型
4 z' X% y. k, F        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。

public static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
& u4 O' K3 }! S+ F1 V" I* K
' \4 \5 f& Y$ L4 i3 Cpublic class SelectionSort {
' c" y/ E6 Y' W2 V
    public SelectionSort() {
    }

1 P/ v# q4 Q3 ]    //
# b! W0 D2 m2 a% X3 l# ^    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)中的最小值的索引
/ _8 K  ^! p) u$ @* S, h7 j+ h            int minIndex = i;
            for (int j = i;j < arr.length;j++){
* B" ], Q+ P: f: H) S' y7 R                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
4 ]: l$ f" G, G1 m, c                 }
/ g% N* c& {; W1 ]/ r) u+ _            }
9 D5 X/ p& m$ F" d) I            //将arr与arr[minIndex]交换位置
' L) k) L9 o) Z" l& S1 @8 j; X$ A  F            swap(arr,i,minIndex);
        }
' l0 z. q( O! w* k$ U5 V- U1 a7 J    }

2 i- t! A3 i3 w4 P. _; G    private static <E> void swap(E[] arr, int i, int j) {
! e/ O! t% O& X- ]: p8 O        E t = arr;
        arr = arr[j];
: ?. ?0 ^& X9 D# r0 e$ @        arr[j] = t;
    }

    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
        }
    }
' t( g8 u, ~; K/ q2 Q6 u}

4 T9 s( I  o  j4 Q        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
# ~/ R* w# m% K/ W
import java.util.Objects;

0 ^6 E0 @7 a* R1 @% v1 T6 N3 Ypublic class Student implements Comparable<Student>{
    private String name;
    private int score;

" ~1 @8 i* X  d' d/ d* N5 y
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
, \# R( M) e+ y2 E  e8 l    }
& G- p- o& _; u* _' ^* _* V  G
    @Override
    public int compareTo(Student another) {
" s4 P: B) b. d: A& z+ u        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
        if (this.score<another.score)
! r/ G( y$ Y, B! A            return -1;
5 q8 M3 [% `( U        else if (this.score>another.score)
            return 1;
2 H7 e1 o. d# o7 l% h        return 0;
8 _% C- f8 ]; Q$ A- \        //return this.score - another.score
# G0 r5 z; q, \, O/ q  j5 _9 g& Y) z    }

: P4 d2 U2 ?$ d( c2 C8 x    @Override
    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
3 l4 C" E: N; Z# K8 s! j8 K$ ~            return true;

) f' M8 X+ u. U7 ]0 G& z% Q        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;
$ k! B* y9 i$ q! s8 n: r; c6 S& _
' i4 o) j- b& m5 D( m4 f! Q$ e" ~        /*
4 U2 _$ P  V% S  D# F8 }, d6 o        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
. m1 p9 {& d) Z        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
: D* j5 c# _/ p' U2 J7 _* {3 _         */
        if (this.getClass() != student.getClass())
: }% i* i: H$ M7 y& v  z8 v            return false;

        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }
% g6 k$ D* d, a0 J* T% W! A
    @Override
8 d6 R: m2 E4 q% K4 R, h4 V    public String toString() {
        return "Student{" +
" E" [; P6 [( f: a$ a                "name='" + name + '\'' +
/ m3 m4 H: Z  t# l                ", score=" + score +
                '}';
: {& Y# Y, @7 ]  M: s- C    }
1 `2 m/ }: ~) Q" @/ t; D! R; B5 c}
2 V( X& u) Q( Z! \7 E5 R
主方法实现类：
+ a7 y( Y+ z; B: u! I% j
9 Y# `( k& Q- ~/ o2 O- W& Xpublic class SelectionSort {

    public SelectionSort() {
6 }, g9 g7 \  B    }
0 a% i" N- z  u' P& }5 p' U; h
2 f3 O( u9 P6 D5 b: \4 k, f+ a& q    //
    public static <E extends Comparable<E>> void sort(E[] arr){
" Z( `0 L% ?1 N/ k3 w: k        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
2 b1 o4 B$ ~9 H( {9 s% Q9 J' @            for (int j = i;j < arr.length;j++){
- o, N/ Q& Q5 g5 _% C1 s/ ?                //在剩余的元素中找到最小的（比较查找）
  l* ?' D. A2 v3 z                 if (arr[j].compareTo(arr[minIndex]) < 0){
5 A1 j* \! ~. v1 a! y                     minIndex = j;
& f2 |+ r  M% O5 H                 }
            }
2 r5 r* \. Y0 T7 I2 P/ m            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
# ?* Y/ P0 ?: u4 O4 O! d        }
    }
+ c1 @, u6 v9 l3 Y
    private static <E> void swap(E[] arr, int i, int j) {
+ k0 ~+ {- e; O        E t = arr;
        arr = arr[j];
2 U% G# b. z6 V# x5 o* X$ o# n" e        arr[j] = t;
0 g6 b" W, i; R- j    }

/ M& H5 p1 ^# u7 s+ [+ o3 [    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
        }
1 L# c7 R& o4 x, ^        System.out.println();
# b( [& H, Z; A/ k: r8 F5 Y1 E4 }
        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
% v" H& t. I+ }1 j1 i' \, K' o
        SelectionSort.sort(students);
        for (Student student:students){
1 R: Y3 V2 G2 g/ m4 W            System.out.println(student+" ");
7 k, Q% M  |$ T, e/ Y# Y        }
4 r# s: o; g2 o9 y  f: K4 T' K
- I# T9 M/ B/ v" S' W& k    }
& o& K( O) X% K) Z6 m( g% Y}
# F" X" }. a+ D
& t5 T# [. |- J! u; C3 {, h复杂度分析
# j, }' X0 i" K2 C) D/ v- G        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
9 H% Z8 O" Q, _2 d3 r6 @& ]
  x+ y9 @. Y3 P

( x7 o6 l9 K& U3 K' s0 t; W首先在ArrayGenerator类当中生成随机数组

    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
7 e4 m9 [9 b4 K% P# [     */
& @  `$ _8 R; c; y; {    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
1 E+ k2 Y0 E6 v9 {1 N        Random rnd = new Random( );
" e0 B. Y0 Z+ t# U; J& c        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
% p4 {. W& ^- W, b        return arr;
    }
判断这么大数组是否真的排序成功：
+ v" R4 Q3 U# u6 P" ^
public class SortingHelper {
3 q/ A3 h1 f3 e8 g4 C    public SortingHelper() {
    }
1 ^2 q6 o1 t! H" h1 n% i9 F- h
# ?4 j, n, w5 P) K& u    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
7 U( e- L* j( l2 g5 C        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
                return false;
. b3 o0 X( L% Z3 M) _' |        }
        return true;
    }
! L( z2 v$ D* V7 B3 z}
# [: J& Q, ^, E在SortingHelper封装一个test方法用来测试任意一个排序方法：

/ B  F! z7 E9 _! b8 n) A    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
! k) f) L2 n7 b# M9 \            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
- x, T+ x; u3 g( \# H            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
5 @: l0 K) f# e- V6 S            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
7 c3 I+ z7 w* n7 z& l9 G2 ?. ~    }
测试时间：
- ~8 U- ?; G$ d/ ^
public class SelectionSort {
8 I2 Q0 O: I0 n* j* y
6 q& P* N, s0 c1 [: ?# n    public SelectionSort() {
    }
  H- a. D4 c* ~% R* j) I5 E
* W; i: u; c) G8 l! f    //
, z8 `+ [; r5 ~7 J) _* W( x    public static <E extends Comparable<E>> void sort(E[] arr){
* `/ i( ]( G) O        //arr[0...i)是有序的; arr[i...n) 是无序的s
1 g% c! X) f: }5 }8 T1 n- F7 h        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
' X1 D3 r0 K& ?: J$ B, |            int minIndex = i;
+ x5 x+ m" U" b! W" |' I2 v            for (int j = i;j < arr.length;j++){
2 I" F4 j$ l& C, P8 d, J                //在剩余的元素中找到最小的（比较查找）
$ w; `9 _  b- m3 S                 if (arr[j].compareTo(arr[minIndex]) < 0){
0 x( @* M. f1 Z6 @# Z                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
5 f5 q* o( H9 m: h        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
6 B  `: ?' k' q# R, d        E t = arr;
: |; T& W0 S; G8 l( T        arr = arr[j];
7 E# t5 ^- Y4 z" J        arr[j] = t;
    }
$ a# z4 B! y  o6 k# J' S, {
    public static void main(String[] args) {
        int n = 10000;
/ d  y9 v( c0 ]* s1 G        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
0 b$ r& \# b/ _& Y' D; v        SortingHelper.sortTest("SelectionSort", arr);
- P5 P- ?; a# L4 l( e5 i
% G9 U( h0 M1 `" r) C( m0 v- y- E    }
( E* U1 [: M# X3 p8 m, f; H}

其中如果要测试两组数组：
* [% S7 M, {" g! B
    public static void main(String[] args) {
- \# Q  |  u8 G1 b: L; O  d5 {        int[] dataSize = {10000,100000};
/ B6 N2 A3 E9 H8 q/ B$ h6 ~        for (int n:dataSize){
$ _( n. P# x" s7 H            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
        }
    }


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

% T' D$ b' y2 t, K. E

---

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

---

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

Powered by Discuz! X2.5