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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
& L- l3 r0 m. }! g目录

选择排序
' b6 ], d* E9 H- [9 U# o
选择排序简单介绍

+ v$ J1 c7 V" @: @  l6 E& S实现选择排序法
7 H9 T% d; [, S' h7 \8 W
使用带约束的泛型
) Y! y4 ?9 k& t5 @
$ e$ _7 f8 k4 I) J8 v8 {使用 Comparable 接口
- C4 {8 B0 i* B# p" i5 `& R
复杂度分析

6 |" y( l; w' w, m( Y选择排序
% W  x  P' x+ G3 A& v% S4 m选择排序简单介绍
先把最小的拿出来

剩下的，再把最小的拿出来

剩下的，再把最小的拿出来
* Z& L. n2 L$ O3 `& c1 H; z0 W5 o
3 k( R8 A0 _* w2 n......

每次选择还没处理的元素里最小的元素
3 }. A/ D$ b) X& g$ P5 n
        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。

. C) Y  i5 t- V6 E6 @- i. f        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

' @; v* ~" w5 ]3 x5 D5 D5 P! E实现选择排序法
1 N% K+ F8 ?4 `' s& e1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
4 l) O  H3 F) e  ~9 t2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
# Z  w! g+ E; _. H3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

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

public class SelectionSort {

    public SelectionSort() {
    }
# o- r1 O# C4 z! A* H6 {  m
( R% e; Q4 \8 p2 O" Z6 `    public static void sort(int[] arr){
0 ^  E$ y, q: ?/ p$ V        //arr[0...i)是有序的; arr[i...n) 是无序的s
* _/ {! g: ?% Y6 p% f        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
0 K$ t) ^7 M6 r) \1 ?( K            swap(arr,i,minIndex);
        }
    }
( D  Y6 `' J9 J/ }
    private static void swap(int[] arr, int i, int j) {
4 n' h3 X! N9 |6 c. k        int t = arr;
7 A7 D; F3 x4 a( ^, w5 M( h  `3 @5 D. `3 q        arr = arr[j];
        arr[j] = t;
( E( A0 n& R; O& t5 k1 f    }

$ E6 v' g! u1 U) a' c9 z( P' T    public static void main(String[] args) {
- c' x6 }/ D2 W' V0 C/ f        int[] arr = {1,4,2,3,6,5};
/ J2 P9 }! E0 P, X7 z        SelectionSort.sort(arr);
* _4 S2 J# `5 X% D  ~; M        for (int item:arr){
            System.out.print(item+" ");
/ K7 |. _, S9 V9 h" L& }) Z; I        }
    }
& v# `; e, f7 q5 L}

当前只能实现int类型的数组进行排序，因此需要使用到泛型。
- H# S) u4 R6 D/ x/ ?# a7 h* g
- z; G' C8 X% R) k* O$ Y使用带约束的泛型
3 c2 I$ p' l  Q1 o  X        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
2 O# a% V/ ?; {) H
; Q- R! A: g6 J6 Opublic static <E> void sort(E[] arr)
2 e' c: r" m4 q" [7 d        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
' d. `; m' ?% y' a
public class SelectionSort {
% h  w% _' n2 Z7 Q" L/ ^
: G2 K  U# u3 g* z    public SelectionSort() {
    }

    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
# E. ^- B7 d0 r" _7 B        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
7 u8 j1 o/ |  X7 a9 u            int minIndex = i;
3 X6 K: Y3 o9 B  O6 F+ e9 m. @' R            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
0 @/ B0 Y3 J- Q7 K7 M# E% l, R7 k                 if (arr[j].compareTo(arr[minIndex]) < 0){
4 t! @1 p9 F! ~* S                     minIndex = j;
; L+ C7 X0 B: E' p; M( V                 }
            }
! |7 x% s4 f; ]' p9 m' ]( J            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
! }. y) n9 A, S$ ?1 v' q& v0 Z    }
" k- b* C- ?& C1 C$ |
7 B1 t" ^& d# N7 ?    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
; _$ {! \% J9 \: \6 w        arr = arr[j];
3 G1 T) j6 i. X2 R: E/ A2 Q        arr[j] = t;
    }

% L# ?3 d" T9 O7 H% V    public static void main(String[] args) {
7 O9 X, }, K+ `" Q, T        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
) x: q" O+ p7 b  \; S1 T        for (int item:arr){
            System.out.print(item+" ");
- F& S- O* W6 M, H+ z9 R" E# s, H4 a; @        }
    }
}

* e8 J6 h3 ?7 L        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
: k0 ?1 b2 O. f/ V* r
使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
7 d* j5 o, T- X7 H
import java.util.Objects;
6 l2 a  J1 q( E3 `* {
7 S. l$ B' y1 Y: O* Kpublic class Student implements Comparable<Student>{
8 U' i. N4 n6 U    private String name;
6 c9 Q- S# S" p, A    private int score;
8 p4 E+ t9 v' t2 N  |8 G+ E
8 m1 }3 g& [6 [
0 i6 M' N+ q/ _9 {6 z    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
7 w' X: D9 g: z; @1 G
2 }, h: F/ }: t    @Override
    public int compareTo(Student another) {
        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
( Z& g1 V, [9 Q0 @* V# x         */
0 ]8 ]$ V; n# V* d        if (this.score<another.score)
1 ]1 b8 q; @+ b  U  I            return -1;
        else if (this.score>another.score)
            return 1;
# V  Q* C9 Y# _: P* u        return 0;
1 u9 v# x, f+ X$ O& K1 w$ N        //return this.score - another.score
    }

' h: p6 g8 E, s    @Override
' {3 s- k5 }  S# `& B; E    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
" L$ U( W$ p+ w+ ]1 ~2 J  n1 d            return true;

; J/ y  H, g% h' n# P( f( p        if (student == null)//如果传入的对象为空的话，则直接为false即可
! N. W9 T9 \& X( P! b            return false;

        /*
* Q9 t, y; g$ h# d        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
1 q  W, K1 @0 V         */
        if (this.getClass() != student.getClass())
0 c/ q: q& ?/ H: Q7 I            return false;

8 `1 ^4 ^7 [7 x- l! G, F7 W, \        Student another = (Student) student;
; ]0 z# l% X  S& _$ z& Y, Y        return this.name.equals(another.name);//写比较逻辑
3 h8 |/ A9 _, K" k: `! R% w    }
  Y1 R: {5 a  a9 n: u/ E( }3 Y' m
5 Y. b0 S# O- b6 g& ~$ _  E# b    @Override
    public String toString() {
4 _5 e! l. w; V, a4 R+ M  B        return "Student{" +
/ H4 N, W( u" o0 W                "name='" + name + '\'' +
                ", score=" + score +
8 C/ a8 n& h+ w# I, H4 I1 J                '}';
    }
9 p3 Y0 M7 a  c8 J}
( J( L  L0 ]/ e$ _
" b7 ^( Z& W6 J7 {2 v3 b  S  F& {2 C主方法实现类：

. D( j6 V) v; C* ]# |public class SelectionSort {
! D0 Y& d, b' H% ]! F1 e" x
) J( J2 H: V( }- j* m$ u6 Y    public SelectionSort() {
9 B; S# f, j0 B  k- d0 t" W& r; f    }

& P: l  W1 w9 c+ p" c    //
    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)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
1 k7 \! ]! C: E/ [+ h  ]5 Q/ O6 `                 if (arr[j].compareTo(arr[minIndex]) < 0){
  j9 D5 [4 S7 ]9 v; N                     minIndex = j;
. {0 b* Q- _' C: X                 }
            }
            //将arr与arr[minIndex]交换位置
+ _. |% w5 v9 D7 B& d            swap(arr,i,minIndex);
        }
& r+ B6 Q0 t0 }0 G    }

6 J2 o7 v9 z$ y/ p  R# b    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
8 I7 B, W1 Z9 L6 X. _        arr = arr[j];
        arr[j] = t;
    }

+ Z. Y# G$ M8 b9 h    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
2 e' ?6 G0 K6 h# N4 L: H" v2 N& k            System.out.print(item+" ");
        }
        System.out.println();

        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
4 t5 F" {& X2 |; E7 i, e
        SelectionSort.sort(students);
        for (Student student:students){
            System.out.println(student+" ");
5 C& E5 v. y% ^& U        }

    }
/ {5 x2 K9 s1 F1 H) F. F' H}

& }: j$ a, N; O( z  D4 g$ }复杂度分析
/ G" e' [& }8 A6 w: ?0 z        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。



首先在ArrayGenerator类当中生成随机数组

    /*
9 p6 g: @7 v6 Y" |' E) G; b    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
( J; u* E& L" q' Q        return arr;
4 L. g! Q; v! m) F    }
判断这么大数组是否真的排序成功：
3 ]% ^1 s$ b' N2 X4 K8 i  C
5 J1 [3 N& [6 @; d% x7 K0 b7 ^4 Xpublic class SortingHelper {
    public SortingHelper() {
$ p* i2 ?% \) Q+ w; w    }
+ R& H! A) L; z8 w  v& ?# H3 ~
0 R  n8 z. N9 l0 U9 |; f) z    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
' f" }- D/ \4 j+ \9 T        //判断数组前一个元素是否小于后一个元素
4 }  `  |; f* b- G/ Q" a% T        for (int i = 1;i<arr.length;i++){
4 u' H. h" ]) p8 u  U            if (arr[i-1].compareTo(arr)>0)
/ l% r$ M! S: A" S/ R' [                return false;
' }: B) X& F+ _. y% K& E- o        }
# e* ^# G+ e$ O$ I        return true;
    }
0 u9 m; j8 c" M6 w}
在SortingHelper封装一个test方法用来测试任意一个排序方法：

# _$ S: D  ?( {$ T$ D    //封装一个test方法用来测试任意一个排序方法
( d- Z& O/ X3 I# r: y9 d% C    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
( W* |- F# M- P. P0 E            long startTime = System.nanoTime();
5 `4 J- r' S  e9 u! Z            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
( H; k" M) R" g7 q* ?. B( l    }
测试时间：

: x! R9 p8 u9 g7 T) Q/ o" t6 m8 j, i9 spublic class SelectionSort {

3 e' v$ A& ]* d  ]2 k    public SelectionSort() {
7 \/ K3 e+ X$ Z& \+ Y  C* ?6 r3 p( C0 u    }
3 ?% k& R- d. N% d: o* v
$ C3 `9 @4 F* T    //
    public static <E extends Comparable<E>> void sort(E[] arr){
; [5 \" u; D% c$ a. V' e8 ^        //arr[0...i)是有序的; arr[i...n) 是无序的s
9 B+ M' F" [" ?* `" p& i- i        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
6 U- s$ G9 p% u0 e- A0 B0 T            int minIndex = i;
7 `. L! e0 a. ?1 h: [6 ~            for (int j = i;j < arr.length;j++){
9 O2 j5 z  W# m' _; E5 _                //在剩余的元素中找到最小的（比较查找）
5 B' M  s& x2 P1 H6 L; s) W) I: `                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
. G+ @1 ~9 c- i4 |1 X/ C            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
/ g! O8 |% R! ^1 c% q- ?        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
; A1 y* B! ~, z5 T. h) K; p2 u        E t = arr;
        arr = arr[j];
& I* Q3 v& e6 S: d( m9 N        arr[j] = t;
6 s  v" m# L+ }* o    }

    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

' q( M2 x! |, ?) f0 T- p    }
}

. ?) Z+ f+ a+ ]3 ?其中如果要测试两组数组：

    public static void main(String[] args) {
& \4 C6 ?# U; R+ j4 _7 E        int[] dataSize = {10000,100000};
0 T- ]3 G! |8 V, d3 X4 x        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
; k9 V3 x0 F: Y$ v            SortingHelper.sortTest("SelectionSort", arr);
        }
    }
% a1 r( c* l" N4 e- D, S& k* l$ w8 p. L

6 C! T- d- F* P. m9 R! l: z( A* N 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
4 T+ F- d& Q3 g$ Q1 r————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
( y# T% I7 e( n+ L) F0 G' T原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

$ Q2 {% ~/ i, }9 R8 M

1051373629

感谢楼主的资料