算法与数据结构（第二周）——排序基础：选择排序法

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
# U0 r; f- k# f5 z& ?0 S
4 T, ~8 Y4 E8 o8 D- N& K' w4 l7 L选择排序

6 t/ \- g- B/ t9 u2 x0 R选择排序简单介绍
2 A0 V- J* a6 }! p0 B
实现选择排序法
" R/ [8 C( Z1 D" t7 x
使用带约束的泛型
2 b5 F' n9 h' ]3 B
使用 Comparable 接口

复杂度分析
  q! a0 s/ V7 }, d
选择排序
; o' O5 }2 l5 I9 [选择排序简单介绍
7 o% i- A! C/ A+ Y先把最小的拿出来
4 @7 d, r$ F5 W
剩下的，再把最小的拿出来

( q; @' ^" F7 l5 j$ f5 X& @剩下的，再把最小的拿出来
0 p# U/ I, X4 ]/ E3 Q
) p$ B1 Y2 r* v9 H( Y2 j2 O8 L......
& t$ ]5 T" f% Z6 ]. ~
* X: T8 r5 Y0 T6 \3 k" v  b每次选择还没处理的元素里最小的元素

        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

1 N) U5 \5 A% b  r" E        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

! h% l/ Z2 d( g7 J; R: A实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
; P# _! ?  J: D2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

3 v* c/ }6 ]+ x8 p& t) [        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

/ X5 M! n5 |3 _9 K: _+ h: Tpublic class SelectionSort {

    public SelectionSort() {
. I/ O$ J! @5 D3 J+ S6 n# t6 P    }
$ u9 n; m8 q, M3 C+ a0 t: b; f; N, T
9 l! v6 X7 S# `    public static void sort(int[] arr){
9 Z' J4 H- x2 o* o* u        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
5 N+ F; T, z8 |' R1 Z7 s            for (int j = i;j < arr.length;j++){
& X  I9 g! [9 a9 z8 \( K  n1 A                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
7 i; G7 y& N$ i" B( |" U' q8 H3 ^                     minIndex = j;
                 }
1 R7 b( W2 Y1 v6 S. _' z            }
8 [8 \& w/ y- z  |% O% @- m, U  M            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
3 p' d3 ?+ x1 S        }
) r7 ^5 ^3 G8 `    }

    private static void swap(int[] arr, int i, int j) {
7 `8 B4 ?, B  ]2 n- o8 `  b        int t = arr;
        arr = arr[j];
        arr[j] = t;
    }
7 T' ?0 I3 g* K/ r. w
    public static void main(String[] args) {
/ Z# f7 q" F7 @5 F  m: R        int[] arr = {1,4,2,3,6,5};
7 Y. s+ r- P3 {" J        SelectionSort.sort(arr);
6 z( |6 z7 @) ~% Z        for (int item:arr){
            System.out.print(item+" ");
0 {' B: e' H9 ~" Q8 W        }
0 s7 r; o% h+ j$ ~7 |# B/ U6 C% W. _    }
}

" M* |: S( b0 C; ]& c. Q& \' P当前只能实现int类型的数组进行排序，因此需要使用到泛型。

# b% i7 i% v: k/ ?使用带约束的泛型
, G2 m/ m" {/ c5 }; |        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
" C0 n1 S  o, {# u
public static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
8 O) i) I. l7 b% T. B
public class SelectionSort {

" l8 b, V# A8 F    public SelectionSort() {
; z/ b" Y6 M7 n% t4 c# e8 g# K. \    }
* P& \. x! e. U2 S+ D. L
/ i2 `& m8 u1 H! l) c    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
6 z" j( D# F# R$ ?! d4 N- |$ n        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
5 T9 ~+ {% P. l8 m# F            for (int j = i;j < arr.length;j++){
7 C' W4 Q1 H6 B$ h6 |                //在剩余的元素中找到最小的（比较查找）
3 Q$ R  U7 |; l9 _                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }

; \! d. z9 x! c9 q+ e) e    private static <E> void swap(E[] arr, int i, int j) {
7 `% e  A- M* a        E t = arr;
2 o. ]. X! e3 G3 H# X5 t, w/ j        arr = arr[j];
. y; ~  x4 w+ J. @: U        arr[j] = t;
$ q; X* K# Z0 T. f! G    }

    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
6 E5 t# B* c1 Z8 e8 g) [8 s        SelectionSort.sort(arr);
        for (int item:arr){
1 X  A6 R' S; j5 v- G            System.out.print(item+" ");
        }
    }
}

/ L9 u% }6 A( G8 ?. L8 g1 Q        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

使用 Comparable 接口
3 S0 {% s: R; C0 k$ g& ^2 g        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
; c5 }9 R, K3 t, U" N; ?# Y
import java.util.Objects;
# A' g' t; @- z. A7 b! P
public class Student implements Comparable<Student>{
    private String name;
    private int score;
+ n% T" [( @1 `: K% a; p! ^

    public Student(String name, int score) {
        this.name = name;
' F6 j' ]0 c. }        this.score = score;
! S# C6 [! m, X. @    }

    @Override
    public int compareTo(Student another) {
( `; |! y& s' P) u- E9 Q        /*
+ H6 o" {4 O/ s6 Z+ F$ l* I# Y  z        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
6 J( M: s. E. S; v# ?9 Y        if (this.score<another.score)
, G1 N8 Z3 O3 s: A( G7 v, }2 w            return -1;
        else if (this.score>another.score)
* h+ {" ~: e% u8 J5 B6 `            return 1;
        return 0;
        //return this.score - another.score
& R6 ?7 H. X; ~% S# ~    }
" T4 H! E) R# v3 ]% d8 D3 T7 n. o2 H
    @Override
/ T: X2 d" B9 [0 ~, H    public boolean equals(Object student) {
3 k0 v6 q" p+ w4 j        /*
  H7 Z- S: L: V- r        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;
  p0 h* `2 S& p) c2 ^
: ?7 ?* ^1 `6 @# r# ~7 Q' m        if (student == null)//如果传入的对象为空的话，则直接为false即可
' O$ p& g- P; K( i            return false;

        /*
        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
0 d& L/ ?  n- k( P+ z        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
. F/ v8 L: ]! I  b  X7 g' s4 D        if (this.getClass() != student.getClass())
! F: Z" q0 V3 u" ~: [7 }' u            return false;
( p1 \4 `5 p% x* X
        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }

( M0 e2 |4 M5 B  C3 A    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
+ [  C" H- M# p                ", score=" + score +
& N9 P' Q8 F+ ?. N- ?                '}';
    }
" [! S6 }4 |* O2 h0 [4 f& w+ e, b}

, l( M6 Z& X8 s1 m7 z9 [主方法实现类：
: n+ Y2 K) R& n5 o  {
. g! N8 P. H$ u  x( Epublic class SelectionSort {

: x5 Z+ E6 {& y3 w' h    public SelectionSort() {
6 j3 G$ G( P' O. y$ o5 z6 }    }

    //
2 Z# s0 G& h6 X) ?" M    public static <E extends Comparable<E>> void sort(E[] arr){
/ g5 G5 z8 W& n1 P; z        //arr[0...i)是有序的; arr[i...n) 是无序的s
3 ^$ a9 T7 q( a: O- F        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
& }' Y/ z, u  I1 y            int minIndex = i;
            for (int j = i;j < arr.length;j++){
- x: j! U$ ~; @5 z5 K                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
1 R9 d$ |7 G7 i; f' j* u                 }
            }
+ [5 k% z, ~+ P# A            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
3 K9 W% I) Y3 ~) G9 k. w    }

) Y. V" V& y$ ~3 x: b1 [4 m* W9 j! g# z    private static <E> void swap(E[] arr, int i, int j) {
( ?/ f/ G7 b" h% j        E t = arr;
        arr = arr[j];
: J; B# Q: S7 O* U2 o' T3 n        arr[j] = t;
+ z4 E) o+ x3 a: o9 `3 L1 l& t! m    }
6 H% c  E  l, p
    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
+ S! L0 C" p8 r1 e            System.out.print(item+" ");
0 m, R' l. w1 y" X+ p& ~        }
        System.out.println();

" p8 R5 _5 T2 l$ H: _* T' Y) b9 i( ~        Student[] students = {new Student("Alice",98),
# `$ X, x$ ]7 [: K, P4 y                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
7 _6 Q# I+ O8 c- c
        SelectionSort.sort(students);
% _$ P7 y, ?7 p1 d        for (Student student:students){
- ~; ?. S, k2 U1 d            System.out.println(student+" ");
0 D5 v7 o3 h4 U9 \        }
8 b6 C( b0 {, g# T. ^
    }
% D' i( K6 i/ b7 f0 j}

. c6 a0 _- G; k. O! l' g复杂度分析
* C3 \4 X3 x# h! e' q, ~" s        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
7 \+ O& F2 s1 w6 P* y+ |1 }

3 _; l! A- [) P
首先在ArrayGenerator类当中生成随机数组

    /*
5 E; h( ?& B5 d  }, x' I( O    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
    public static Integer[] generateRandomArray(int n,int bound){
2 k& m2 J% k" ?) a  T6 D" d        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
        return arr;
    }
  C' q& \% E. l) J判断这么大数组是否真的排序成功：
) A1 z2 Z" `+ C' o2 e
public class SortingHelper {
4 n2 O7 t" c) d+ I' z    public SortingHelper() {
    }
+ q7 A! n& x5 @# z6 P
: O7 j1 ~1 M+ _9 [) M4 Z8 Z    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
8 w& Q- h7 l/ i/ h  s        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
                return false;
1 @9 Z) t2 [. U        }
4 y- T5 h& ?1 v1 T        return true;
& m" u# y" W: o- w    }
$ ~" m, w3 @) P/ u- P}
在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
1 Y0 r/ a( ^& y' t  t: N9 b    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
& \" O, R/ X: T$ m. a            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
8 Q8 E1 c7 C* j: U% ~/ x8 Y            long endTime = System.nanoTime();
1 g5 g$ P; Y7 S8 t& T            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
6 @0 \0 [9 J) D1 s5 ~9 E                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
- N5 B3 U" s, O) ?4 j! ?1 l    }
5 ?6 A: f/ M* D0 _$ L测试时间：

public class SelectionSort {
; i. B/ M0 l4 x" B
: E1 M3 b+ z2 q8 {6 }' E0 }, u    public SelectionSort() {
( u' f# S: t( r2 ]  \" q; _" _& r    }

+ ?+ u2 `! P# R* y/ [" H  d    //
! o2 _' ?4 l% _3 i* L. Y: @    public static <E extends Comparable<E>> void sort(E[] arr){
5 Q8 c# S" L5 Y        //arr[0...i)是有序的; arr[i...n) 是无序的s
9 v, l* \3 G$ s' v/ P0 Q' H4 Q        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
+ `" O/ ?& z9 C$ r  d5 ~% H- t            for (int j = i;j < arr.length;j++){
  B, f1 q6 |  }# _                //在剩余的元素中找到最小的（比较查找）
4 n' _' i! Q: y$ f$ U' b4 n                 if (arr[j].compareTo(arr[minIndex]) < 0){
, }! n( h8 I5 }: s                     minIndex = j;
& i- L, L) l  t: c                 }
7 ?: o- b) }- ^* ~5 K2 s$ e            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
# J( }' k9 W# [; C2 i    }
5 z- a0 u7 a' r6 J- T  ?5 v" ~
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
: F: _4 C) ^& e    }
( U3 f5 k& m# Z. O( y
    public static void main(String[] args) {
. N0 Y, J* k2 }( ^2 q        int n = 10000;
0 L. @9 ~& ^0 m- L; A  B/ i        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
}
* ?& X: p8 L: \# Z) o
其中如果要测试两组数组：
  ^, f7 w1 K! m. Q: v. ~0 T+ ?
+ ^) O  f& ^! ~5 }    public static void main(String[] args) {
$ D' R. z4 y1 ]" `, w* d        int[] dataSize = {10000,100000};
1 \5 f! E6 Q+ P# e2 H! @        for (int n:dataSize){
% ~) V* u6 @( y& m/ K6 @6 \            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
" g# a8 F6 V; b, Y$ X        }
    }
8 B9 s9 t1 ~' V( W' V4 d" k1 C4 O

可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
. W8 \  e9 G" J) l版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. c1 @0 C8 `& p$ p4 \原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
8 O! A9 b; T- B- O/ |- l9 }$ k5 Q
8 i0 s5 M5 d$ G" |; O

1051373629

感谢楼主的资料
4 r9 [8 S1 s- k6 d8 u# s, E7 ~/ j: K% K