数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2022-9-8 10:10
标题: 算法与数据结构（第二周）——排序基础：选择排序法
算法与数据结构（第二周）——排序基础：选择排序法
% o' O1 K* Z2 \+ k目录
6 A- t* h; [% h( `: ^" x
选择排序
" z3 \* v9 b7 j
选择排序简单介绍
' `, K% n: F* h0 X3 j
实现选择排序法
+ S  V& m# c. g* L; a! [
使用带约束的泛型
  R4 ~6 H. a$ \, `
* Q" V; D' _" n0 o. o使用 Comparable 接口

7 [" X7 z; _# c4 v! D( c复杂度分析

选择排序
选择排序简单介绍
! c7 N7 `; Q: E8 c" g& X" U先把最小的拿出来
6 G) G8 J3 ~7 ^1 ^9 b) F$ o
剩下的，再把最小的拿出来
& s4 q6 `5 L: o. Q
剩下的，再把最小的拿出来
( v! P8 y* H3 H& G
......

每次选择还没处理的元素里最小的元素
) O/ ^/ e& F: E5 a9 Y
: |$ f: J* `3 a7 B        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
3 o7 }) h! Z5 H4 P! _$ ?
        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

; g  e4 i1 @. ]6 h4 C4 C: @实现选择排序法
- g3 h+ m; g. n- ^8 m! t1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
( x! F/ y: Z; U2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

5 I4 }; N4 k/ `8 gpublic class SelectionSort {

    public SelectionSort() {
0 [5 Z2 G1 y/ U8 D    }

    public static void sort(int[] arr){
$ J) ~% ^) ^1 S- Q# q! U8 r2 k        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
% n0 a# h4 V: ]            //选择arr[i...n)中的最小值的索引
  a, @$ M3 [5 t; U. o  K2 P            int minIndex = i;
            for (int j = i;j < arr.length;j++){
% z) I3 G1 E. J5 d6 n" {9 i) ]                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
4 L; z; h( B2 n4 y0 W                 }
            }
            //将arr与arr[minIndex]交换位置
- }2 k( b1 s4 X/ r' V  |. n            swap(arr,i,minIndex);
        }
3 R* K" Y  d& J- V) j/ M    }

    private static void swap(int[] arr, int i, int j) {
' _( {9 K% p, u1 f0 R% D6 n5 W        int t = arr;
$ |' I% [9 W$ D8 P        arr = arr[j];
        arr[j] = t;
3 {' ?  Z- ?7 x% b, q7 ~# j" D    }

" C& L8 l$ B: E/ C: w* j    public static void main(String[] args) {
) H9 X5 x0 h- @7 Y1 g& p2 ]* z        int[] arr = {1,4,2,3,6,5};
' h. `0 V5 m* Q" @* I% i9 f: J, d3 L        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
, {" L4 {7 \, l6 e  {# T0 K4 B4 [        }
. |: `* H+ j0 M2 Z; e" l6 n5 U    }
9 [$ y: f$ [+ p2 U}

当前只能实现int类型的数组进行排序，因此需要使用到泛型。
/ m8 h* W! [* i1 e9 c8 }) ]
使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
' |4 @  }$ B5 G; \; \4 p) {
public static <E> void sort(E[] arr)
: U4 m; ]7 p% o- c        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

public class SelectionSort {

    public SelectionSort() {
2 ~5 e) O$ v3 {2 x. p+ j    }
* }; C2 F  n( H# s
    //
    public static <E extends Comparable<E>> void sort(E[] arr){
' d3 Y' Z0 W+ c0 j) |        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
5 T; W7 V0 A9 }# M$ z1 M            //选择arr[i...n)中的最小值的索引
; @% \8 C9 C5 _, m* o/ g& ^' c            int minIndex = i;
3 Q& r$ y8 F2 b            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
. z* y1 \# `; m) u; {0 I                 if (arr[j].compareTo(arr[minIndex]) < 0){
) j: J- o% [0 h, p7 @                     minIndex = j;
7 m/ _- ~2 w( P' z' _# }# T                 }
            }
0 C. A3 d. Q7 R0 `5 b+ V            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
% ~3 K: [: _3 X4 `& M' E    }
" ]8 I  m# W. v7 e* q; I' Y
3 R9 A8 C3 ~* V    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
4 q. w9 s* O$ T0 t4 G  A        arr = arr[j];
" m: L6 g0 L) a) h& N        arr[j] = t;
5 T! c- U; Z% J1 ]    }
( a4 d$ _6 @, o  ^: o
    public static void main(String[] args) {
4 d$ h, a& x1 Y7 x0 p        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
; l' c: Q- M9 W( t: B, g7 e        for (int item:arr){
            System.out.print(item+" ");
0 |- P- D5 n9 V  H! G9 |: @, A7 g        }
    }
}
  B1 E, }4 H; W: M7 f- F2 y& V
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

0 C* N- l9 I/ U+ O使用 Comparable 接口
; e( s; P5 K% r! p' ~; V        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

. r3 s* a; @; n, @3 g1 ^) ~+ T( Fimport java.util.Objects;
: }4 \! U+ k  y* [6 l! h' U% Y1 \
* {/ E* F# Y  \" \) W7 W* F. Vpublic class Student implements Comparable<Student>{
4 u$ e2 m4 Q* [3 z( w    private String name;
    private int score;
+ G- ~: r7 w* R4 v3 C2 P
$ o6 p- g: ?8 E% g0 Y
    public Student(String name, int score) {
1 ?' W, U* n: W, c# u. x  `        this.name = name;
$ Y3 K6 Z. p6 E  O/ Q4 w, o, |        this.score = score;
# Y5 s1 F& [: Y# w/ i9 u    }

    @Override
5 I& Z5 a8 A  ?8 l    public int compareTo(Student another) {
1 U9 S+ C$ k- r' G7 a# f( _2 ]        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
        if (this.score<another.score)
( k) C+ ?7 s8 ~/ j            return -1;
        else if (this.score>another.score)
            return 1;
        return 0;
8 _# U: a& P% T' E9 I        //return this.score - another.score
    }
' N) ~' Y( w: q- @. r# v9 q( b
    @Override
    public boolean equals(Object student) {
/ s* ~& E" M6 {  u$ e$ c        /*
        强制转换有可能出现异常，因此需要做出判断
- p5 }9 h( F" J        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
# k- Y' b# c" Q8 J# Y( i/ S            return true;
+ G/ a+ M9 c& T) G: w! Y# s4 p! p
        if (student == null)//如果传入的对象为空的话，则直接为false即可
2 `8 v* n! M% K* Z, X, ?            return false;
. D; [+ c3 s0 y" a' D
        /*
# L9 X1 W$ h( q& k        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
, X4 }4 s1 o. g        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
        if (this.getClass() != student.getClass())
5 s% ?# M! d- n" o0 z! Z# N. u            return false;
/ N3 H' j7 ~) Z* e
) A0 {( h0 G" ~7 o        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }
# H! d7 @" E* A: L2 V
6 |- c7 M5 s3 L9 \5 s    @Override
    public String toString() {
: p) t1 O0 X. x6 B        return "Student{" +
( \9 d6 t" D% L1 B$ p( c* a                "name='" + name + '\'' +
                ", score=" + score +
- E  a! M: M, I' {5 J                '}';
    }
}

' r. h  f+ w/ l主方法实现类：
# L) z6 r$ G$ N9 R0 A0 D
+ M9 K1 V3 d2 ypublic class SelectionSort {
/ I9 A7 F; Q! R
    public SelectionSort() {
    }
  s- {# s- `. R! _6 ~9 I+ ?: T
    //
" ~5 e4 \) w) l) h! h) E    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
- V3 n5 v7 C9 W  e        for (int i = 0; i < arr.length; i++) {
1 g) ~1 b1 F# K4 O) R            //选择arr[i...n)中的最小值的索引
5 @7 Y+ u  p' @3 K  k7 u            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
/ m; v" E! U- _$ U* b* e1 a' |                     minIndex = j;
# \* w2 U7 _( T8 z                 }
/ J& b" i; |$ u+ Z! `            }
            //将arr与arr[minIndex]交换位置
0 B' |( J& y1 p3 d            swap(arr,i,minIndex);
        }
) @- W" r: X1 j3 @" }    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
3 R: a& x; x& o9 R( v2 T  S5 H$ e. B        arr = arr[j];
, A: H5 z: s$ t# }1 o: U- a        arr[j] = t;
) q, c: ?9 j; a/ h: l- p2 K    }
) X4 E# _$ X2 b  L1 I, n9 S
  ^/ F% U8 `+ B& q) `- n    public static void main(String[] args) {
; l6 V8 t9 ~7 V6 A! V        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
+ C7 R; ^7 ^8 K9 u  L5 [* }$ h        for (int item:arr){
- ]/ N5 E) k) e2 x/ G            System.out.print(item+" ");
. Z0 p$ e/ U8 V        }
        System.out.println();

* p9 p$ ], a3 k: X" u9 S! _3 f0 {: n        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
) ^) L3 A( T! m0 F/ `) ]9 }+ _5 A$ O
2 m; T; J, Y$ K6 v- [. N& \4 |        SelectionSort.sort(students);
, x6 N5 `6 U; s& \% J. e- w        for (Student student:students){
            System.out.println(student+" ");
  y) S' k6 Q3 f& X( N* T/ Y& L        }

3 y- {# t* n2 f. R. h, w6 Z    }
}
1 r8 Y. O" i3 R+ \% L, p: u2 |
: s2 o9 G! i7 @) x" N& \  G复杂度分析
9 B3 k) Q( v0 y" z" A8 D9 ^" y3 v7 j7 s        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。

: \3 b$ \! |: M' H$ B

- i1 a6 h2 w7 j; w0 E首先在ArrayGenerator类当中生成随机数组
# i  C% r6 Y/ D0 G9 f# ~
    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
1 R  r' o0 H7 N     */
* G- E; y# ~; K9 u/ W6 H1 V! d8 \    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
3 j7 V0 r+ ]) ~2 c# L  U        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
% {0 x' H4 [. k& Y+ I        return arr;
    }
判断这么大数组是否真的排序成功：

public class SortingHelper {
' X1 o( `( I, ^2 v* a    public SortingHelper() {
    }
8 b. d8 w9 v4 ~1 x+ L
$ S6 Z5 [7 y0 T3 @& v3 ?    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
) ^6 m1 x9 t/ g# }        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
% q$ |1 D0 q  L, I2 b! l            if (arr[i-1].compareTo(arr)>0)
$ k1 {' f* g1 q" ~( u' Q                return false;
        }
" L, ~, \- O3 d+ M! s  {& z$ m        return true;
    }
6 r$ b1 A% l& f}
* o# P7 p2 |/ a在SortingHelper封装一个test方法用来测试任意一个排序方法：
& i* q; Z6 M9 U& w9 [' _- b
    //封装一个test方法用来测试任意一个排序方法
1 W# A& W: R& v; \! W    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
6 K# J4 e8 s7 z2 R            long endTime = System.nanoTime();
9 C* D- }5 T1 i5 K            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
  Y* E- _) o. L6 u- o. W测试时间：

public class SelectionSort {

1 ]' z$ [4 ]; F' Z  N+ w$ p7 q; W    public SelectionSort() {
+ N' ?0 \! i5 D; N% y( ~    }

    //
7 P, i7 W! }6 |( s    public static <E extends Comparable<E>> void sort(E[] arr){
) s  l: r( ^0 k9 T, g- w/ T        //arr[0...i)是有序的; arr[i...n) 是无序的s
$ p- R% T% {: I+ F2 S        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
! t9 o& q& f* [, m8 v* f% q% |( J                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
6 E- L: z" h/ z+ g& }! ^4 }                 }
            }
6 m- ?/ b0 v& B; L% c            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }
  ^) B2 R$ L! l% m
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
" a( m! y$ c" p        arr[j] = t;
7 T" H3 N& E1 Z    }
8 P5 k7 w! ?2 t$ q' Q! t$ ^
    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
0 F; I% D9 D: Z/ c2 O( @( m" W        SortingHelper.sortTest("SelectionSort", arr);

    }
  E1 _: p1 p- [, o; v}

; Y) g% m4 p+ ]/ Z/ W2 q其中如果要测试两组数组：
/ Z2 o5 f8 L8 N  \7 D
    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
- W% `" B! T  [- |            SortingHelper.sortTest("SelectionSort", arr);
, C$ ]' m: y: y# t* h        }
    }

$ Y0 p& M! f6 w, R: Q3 [
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
+ t) K1 W- X# C. m& K3 k/ j9 ?& L( N! c————————————————
! i3 d0 R& \1 @& u4 @) Z8 a版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
6 ^5 |* q; a. t' Y
) }) U8 y8 b1 Y' B4 C
: ]8 ^/ \% n3 t9 j3 J

---

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

---

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

Powered by Discuz! X2.5