数学建模社区-数学中国

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

---

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

选择排序
+ z4 |, e. l' J5 y" t/ \" U% c+ z
8 M( G- n8 \0 y: i& m& y6 C% m选择排序简单介绍
, r. \0 [, ^; K9 a) A! I3 R! C
实现选择排序法
( t6 U" ^( q3 k; g, m' \
5 K; i9 |0 N5 H/ G' w  N使用带约束的泛型
( E" Y+ A: U+ c; [5 H+ _
: w7 `/ _6 \7 O1 n% D$ J使用 Comparable 接口

! F# S# G7 t; W* s复杂度分析

选择排序
* P& u- K$ v' V/ {选择排序简单介绍
先把最小的拿出来

剩下的，再把最小的拿出来
- v4 k5 @* }- F: ^$ u
剩下的，再把最小的拿出来
2 F# i. K* F% L& Q5 n
2 y1 Z* h! a5 M. M/ u/ b......

每次选择还没处理的元素里最小的元素
+ ^0 Z) j$ ~! I7 n7 Y
        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
, o6 Z( @  J" L9 q2 {0 [
. V& D; D! b% q9 s        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
3 J% ~5 A8 U2 t9 ~2 R
9 x3 j7 R7 [6 c7 z3 d4 b3 F实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
7 x* [5 d- h. L8 a8 J! M5 B2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
/ l: l1 W# y, F2 h- q* N( I3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
3 d! T  `9 U; a1 P
: p6 d( g, Y9 O/ M# C8 S        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
! R7 g# O4 }, r; T7 Y
public class SelectionSort {
( F* g- N6 n" F. i( ]
; l) c8 k: z  ]: ^4 \    public SelectionSort() {
    }

    public static void sort(int[] arr){
1 y9 F2 G4 g7 B3 V- ~        //arr[0...i)是有序的; arr[i...n) 是无序的s
4 |2 w6 o- c4 S+ U/ [        for (int i = 0; i < arr.length; i++) {
2 X) ^. L/ K$ v            //选择arr[i...n)中的最小值的索引
* c3 `0 \3 [4 |6 w( J+ ?            int minIndex = i;
            for (int j = i;j < arr.length;j++){
3 c! ?, d  N# n7 n, P; i' y                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
# G9 h+ n$ {' }! ~                     minIndex = j;
                 }
8 N$ L6 C( \2 W$ c            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }
. ]8 U0 `+ @; E4 R
- h0 n& L+ [7 d6 l& q& C    private static void swap(int[] arr, int i, int j) {
7 _  F' }: @- _* k, w7 r        int t = arr;
& l4 C9 ?& `, {* s  T& h- \        arr = arr[j];
        arr[j] = t;
: r% K/ b+ @4 S/ v    }

1 J, C- m( t4 o% g$ {    public static void main(String[] args) {
! }1 l; n1 ]1 N5 a" j. ~) e        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
2 R8 T/ V- L1 ]  z        for (int item:arr){
            System.out.print(item+" ");
        }
2 O( J! }( o2 E. ?+ a" K    }
}
' A8 X9 a0 d4 ~7 J# o$ ]
3 o0 d3 b% [5 M% B8 ]5 D6 G当前只能实现int类型的数组进行排序，因此需要使用到泛型。
. {5 M% D& \4 w5 e1 L8 G( a& }# q
使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
# ^* q8 m) p/ s
public static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
; @8 |" ~8 j& s
' [5 [0 Z: v$ n( [! ?' A- |public class SelectionSort {

% f5 b: E* t! z% i8 S8 b/ j    public SelectionSort() {
( x8 d/ {, H( x    }

    //
    public static <E extends Comparable<E>> void sort(E[] arr){
" J3 U" d2 W+ h9 C7 g; j        //arr[0...i)是有序的; arr[i...n) 是无序的s
4 ^. T& U0 |9 q0 g8 a9 i) P- z% [        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
% }- c( I  H1 S  Q, u* X: j            for (int j = i;j < arr.length;j++){
2 ~. \1 T; ?; i                //在剩余的元素中找到最小的（比较查找）
* Y! w9 l% J( F! i                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
0 o, v8 a2 R6 S- g4 m- p; |            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
, y6 N( i! A# s- t7 {  ^! W        }
/ F8 f# y4 {+ X& E7 S    }

    private static <E> void swap(E[] arr, int i, int j) {
9 A6 f& ?$ h% ~% q        E t = arr;
. ?/ n8 l( l; Z6 x2 ?; y; g        arr = arr[j];
1 N  [9 H2 n# Q2 h        arr[j] = t;
    }
1 f9 _5 K" s7 a( v% a
5 e  @, k2 R+ V# `' Z    public static void main(String[] args) {
" O5 |; b$ _2 {9 R/ o& x) f) n        Integer[] arr = {1,4,2,3,6,5};
7 w5 f8 d2 j! t        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
0 g: q9 i9 p$ f/ O3 g) l        }
/ T  ~/ M  A0 ]/ F    }
}
3 b# ^( p4 Y6 I" R& R# A6 o. C" a
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
& d, F3 g* s  O7 E. w
使用 Comparable 接口
! q5 s6 h: H, S9 Q& T        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
7 z2 y9 z' U3 S- {
) M; ?% Q# f4 E) k! x; s8 wimport java.util.Objects;
4 f6 \8 j- S) A! n6 j1 R) j
& q- K+ T5 Q+ t( a/ _# r# |2 |public class Student implements Comparable<Student>{
; T* L5 }, B7 P    private String name;
    private int score;


    public Student(String name, int score) {
, p# t" b  C2 E8 B        this.name = name;
+ o# V6 `! w* }7 `  t        this.score = score;
    }

    @Override
4 e0 I2 f5 e5 H) ^' \% c, n4 C    public int compareTo(Student another) {
! W) H6 \0 @' [: B, {, V        /*
6 v  f( o. V- z% R        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
! _6 W9 Z) A' Q. k3 V0 [         */
        if (this.score<another.score)
            return -1;
% [4 A0 V9 C; w  w! s/ h        else if (this.score>another.score)
7 \1 M( V' F0 o2 v" O! k# F. S. ^  F            return 1;
        return 0;
& G5 j9 V) A3 z/ B5 E. K' j! J: p        //return this.score - another.score
    }

9 N( x" j( o, h/ w; I    @Override
: [* V" E, Q5 s6 Y2 v    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
/ S+ d' Q/ D: |0 b" Q) z# F: e* {            return true;
2 N. P$ X) K% S5 h/ {) F. ~7 H
        if (student == null)//如果传入的对象为空的话，则直接为false即可
0 P2 n  {9 G) j+ _6 c            return false;
; f$ k, N& K1 ]
* Q# g0 X6 j, K2 D. [        /*
: W; s/ `( l% P% t! a% m5 G        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
% f$ j9 B+ A# D$ f! m        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
2 p" l  i) a) G6 z5 w8 n5 v         */
: U, [* p% I* _7 k/ l        if (this.getClass() != student.getClass())
+ D9 o3 R6 I( c( G2 @! M' \            return false;
% B' M* t9 R' w2 i' u
        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
9 j& G1 L% p8 }, Z  i    }

    @Override
    public String toString() {
6 k' Q( r6 `) H2 p8 p. X* i# j        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }
}
$ t7 {( S+ o' A
主方法实现类：
$ |; M) Y5 @; }: ]
! i% k% Z8 G! u4 L; w4 N# Spublic class SelectionSort {
1 ^. `9 y$ W& c% p) r
    public SelectionSort() {
9 [7 W# C% C1 L7 i+ ^) f' k    }
3 m9 p. R# o# c9 X2 ?: U
5 q* n1 f) e' D    //
    public static <E extends Comparable<E>> void sort(E[] arr){
+ e9 s. e; {, D        //arr[0...i)是有序的; arr[i...n) 是无序的s
" O8 x$ K/ E8 s        for (int i = 0; i < arr.length; i++) {
! \% s& D) J* Q8 l" u- k$ t            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
3 ~! K( T; v! r5 i; B$ h                //在剩余的元素中找到最小的（比较查找）
" |- y: I* J, E$ t) y+ o                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
: G9 [3 h3 P" K, B) n5 j                 }
3 s1 ?8 y: Q% S) T, `+ F9 w            }
            //将arr与arr[minIndex]交换位置
, t0 p! A1 |1 O: \            swap(arr,i,minIndex);
4 t" {7 Y/ Q' s/ a& W7 s' \        }
    }
: m# _2 ^  N0 q& s! H( A! b
    private static <E> void swap(E[] arr, int i, int j) {
4 p0 `& @" [& R  \6 x        E t = arr;
3 V8 I2 }% T0 ^& B1 P9 M/ ~$ Y$ ~        arr = arr[j];
: G0 P6 m3 O7 {& H" V        arr[j] = t;
& i7 D0 M/ r- p% c8 x    }

    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
4 _2 Z2 y2 ]/ t        SelectionSort.sort(arr);
! t4 O" O$ r$ z( _        for (int item:arr){
            System.out.print(item+" ");
        }
        System.out.println();

* W, _' P, n+ O% U# p        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
4 l5 f9 N9 G! M1 W+ H+ M- H% B                              new Student("xiaoming",66)};

        SelectionSort.sort(students);
        for (Student student:students){
6 c  s( _6 K) c$ e& ^" V, `8 d            System.out.println(student+" ");
        }
7 M2 ^& y* M) N* l, }" ^  G$ P+ x: s6 K
    }
" g* u! x) Z$ C0 y; m" m}
+ Q* h+ {3 C) c9 f4 B' b
复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。



首先在ArrayGenerator类当中生成随机数组
3 s" b; d& w0 h
( S9 S# p& @; k/ @8 v    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
( W- E0 [! J. T& |5 u. j     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
# G- i7 T2 `% b0 c        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
    }
4 L+ U7 L- ?; `9 m判断这么大数组是否真的排序成功：
9 t0 S8 |8 H, G) a  r
public class SortingHelper {
    public SortingHelper() {
- ~4 g. R* _% D' l) ]    }

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
' h' I" `* o+ D  o( a2 M/ a& V        //判断数组前一个元素是否小于后一个元素
8 B" y9 D" Z; C        for (int i = 1;i<arr.length;i++){
( r: ~' J4 T3 i) ~" \# c            if (arr[i-1].compareTo(arr)>0)
6 j/ {& {: P! L" e0 b                return false;
        }
        return true;
( Q2 h1 `8 h! F8 {5 l  _% ?    }
" X* f4 l/ b' L: j& u& {}
在SortingHelper封装一个test方法用来测试任意一个排序方法：
% T2 s3 P" P/ v" F
    //封装一个test方法用来测试任意一个排序方法
: B$ o( t& J+ b# h. E/ V! D8 T    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
0 _5 k) P, K3 l' t; v6 k            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
* \, T, A8 W9 d5 Z  p8 o; ?6 Q, W2 L; F            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
: y6 P! L7 ?9 I1 T# y5 R测试时间：

0 n' t0 ~1 J, n' X+ G4 |public class SelectionSort {
: p- l: G! q  T  n# q* c
' H* k  t/ ~. r4 x( e' ]    public SelectionSort() {
    }
! ^9 l' j! L4 N- h7 X9 k
    //
8 L5 T7 o7 b  m6 C* c2 s    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
! L2 T0 g& Z% E1 K5 o' x        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
! T  @' c; D$ }) @. m4 \' u) \            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
1 p' y/ w3 v) T1 H                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
4 q" {6 d1 n8 J; w, k0 `                 }
1 F; t& |6 a0 X" Y; x            }
            //将arr与arr[minIndex]交换位置
1 d* P; P6 V* R            swap(arr,i,minIndex);
8 q* U: u9 ?3 S) T& e) j- f        }
    }
4 {& l2 J( s4 v
6 C# x1 R9 B& f4 ~' f2 u    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
# c1 M0 H% M2 o" D9 P0 u* I    }

    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
3 _7 m1 D1 R0 |, b6 l( o        SortingHelper.sortTest("SelectionSort", arr);

: d! y/ ?1 y0 W1 O. s/ ^4 T7 X) k    }
. _. k8 G' d9 N! V6 t- r}
2 u* X0 h  Q: X0 o
! m& ^* p$ s6 B其中如果要测试两组数组：
! w- F& @. X  X% H& x. j( g
2 i$ I) q3 F0 V: b% Y    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
0 t# M7 T1 `& v$ d4 p8 N, `1 D            SortingHelper.sortTest("SelectionSort", arr);
        }
, F# {: [& J  `' ]    }
) ~8 j( J  _& X
, O4 s; [% V" q; a
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
3 k) }( _# [0 s7 t原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
: }2 _9 W1 g5 ]( H* w( `  A  v

) J$ ?; f6 U5 l* z

---

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

---

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

Powered by Discuz! X2.5