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

杨利霞

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

" X5 S8 |4 H* O选择排序

: g( S6 L5 Y& v. T; D2 ]选择排序简单介绍
* K( g0 F$ u' F5 |
! A( J/ T0 S1 W- A% e实现选择排序法
' ^; F7 S9 H5 u& A6 W
/ w1 R* ~9 h; w; Y2 M使用带约束的泛型
" H3 L& r9 y) X! b6 F! p) I2 N
$ N; I" W7 b6 t8 D使用 Comparable 接口
* E! Q4 r7 ?/ \5 H3 r4 s4 I/ m
复杂度分析
; K9 F* L) R/ X& o
) O( N, h; V% U* F1 b; V+ Y选择排序
选择排序简单介绍
先把最小的拿出来
6 x3 O3 g, ^% T$ h) h7 }/ v# R
% ^4 B) L0 x1 R7 @5 j$ S剩下的，再把最小的拿出来

, \& X! V* V- F( \0 m/ i' j剩下的，再把最小的拿出来

......
1 I% d- a; i+ i1 Z' ~$ e
" A7 _8 Y7 s- ]5 w; ]每次选择还没处理的元素里最小的元素
; S( [$ r" r1 s4 }& A3 @
* f, t/ w& e' _4 @: U' p        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
6 h% j& @$ r" w. K
$ L; v8 S2 c$ z8 o/ g        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

0 t3 N! L$ @5 b1 y实现选择排序法
  E8 F% ^& Z7 H8 k5 H1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
; `4 j, ^  ?. C- l: }, M( p2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
/ ~" L+ C: E8 y' x7 L2 X3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

) }' y" [/ l, x. t8 X6 P3 g        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
- z/ m+ Q' Y- ]+ _+ K5 U3 l
public class SelectionSort {

2 U+ y3 j  d$ J, n, b    public SelectionSort() {
    }
7 g6 |( m: @. K
    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
4 I* @- {5 n7 ]2 U$ ^- h        for (int i = 0; i < arr.length; i++) {
# D4 n: u0 b* L5 p2 v3 q) X0 |. j' @            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
7 D6 k! W# v, f9 H! v  [                //在剩余的元素中找到最小的（比较查找）
- h  S& G! n2 ^/ f; z* J1 {/ Q                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
9 [. S- B0 u4 r3 |                 }
1 z/ J2 z& k1 }) r+ }            }
3 n1 @7 t; m% W4 e0 [1 D# [& o            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
' S$ @3 h2 s8 ^* \1 q& o- k4 I        }
    }

! T. s3 p, P& |    private static void swap(int[] arr, int i, int j) {
        int t = arr;
        arr = arr[j];
1 i' \& ?0 e  R; P, l  }) r9 v        arr[j] = t;
' Q- T- h. t1 J1 g2 _    }
( C# A& f9 j" g* R
    public static void main(String[] args) {
5 a& M: N+ n  F+ j        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
* }7 V2 J  O, c; z' A        for (int item:arr){
# A8 X1 \( I) |, p, T' P% v5 ?            System.out.print(item+" ");
        }
: X1 E9 H3 y! O2 K    }
}
2 a% f  j9 v/ g; m) m1 }
4 p2 t& t% e1 f2 x当前只能实现int类型的数组进行排序，因此需要使用到泛型。
' p2 |- e' U1 z% A
0 }6 H, Z3 U' k. q$ A$ Z使用带约束的泛型
# _4 N" |8 e: Z+ x        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
7 R- p1 ~$ Q9 p; X# W/ E$ }
+ G3 T3 R7 w: [$ D' f* Bpublic static <E> void sort(E[] arr)
% C& g6 D" `) }$ a* H        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

public class SelectionSort {

: `- y8 W: L5 h% h7 b- O    public SelectionSort() {
    }
9 o; G; @, T9 e: S5 X! ?. D
$ v* W. f0 y/ ?: `- e    //
    public static <E extends Comparable<E>> void sort(E[] arr){
0 U; V* e; y4 ]2 c1 s* d3 F3 u* L( {        //arr[0...i)是有序的; arr[i...n) 是无序的s
6 U  \* `  k! p0 b' z        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
: |9 ~4 [) f2 ~1 e- b/ `4 k1 {            for (int j = i;j < arr.length;j++){
' ^# e7 g5 H% z                //在剩余的元素中找到最小的（比较查找）
$ w9 Q" \- J. s/ l* J# p- L                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
                 }
            }
/ u9 i. X, M1 J. f) b, z% o            //将arr与arr[minIndex]交换位置
3 C" B- V9 H) D            swap(arr,i,minIndex);
8 I& }5 {3 i  }1 i' ?& C$ J- i0 L        }
    }
! v* o' ^* T. q5 v
    private static <E> void swap(E[] arr, int i, int j) {
/ s. P2 }# w1 ]# B: E3 E  Z/ {        E t = arr;
. A: g) I  A/ y/ H( C        arr = arr[j];
: x; `) m* K" L: b5 R. G        arr[j] = t;
' ^% \! O0 r7 K! Q    }
6 w: w+ {% `% O6 M
    public static void main(String[] args) {
- ~' z* [+ n) B* Y  L4 Q0 p% |        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
" ?$ G& U1 \( I0 J: I9 B5 K            System.out.print(item+" ");
: h  q' T* m0 L1 C9 W        }
    }
}

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

9 L# [% M. p( |( s8 D; F使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
3 ^+ N9 A( c  P& m4 C' [: [* R' h9 X
import java.util.Objects;

8 {6 r2 g7 z, {' l! n) _public class Student implements Comparable<Student>{
1 G2 T9 p: r7 _* q0 l0 u8 E. J    private String name;
! P7 [* }$ }& V2 u% ^4 |4 K6 X    private int score;
7 |/ w7 i: ]( `$ @! j
5 o" ^$ `- I! J6 o$ ]6 ?  I2 g
    public Student(String name, int score) {
) _. V2 s" r# W& v( A  d( Q' p        this.name = name;
        this.score = score;
    }
- b1 h9 E+ j( Y
2 t+ W2 d- G  L' o* Y    @Override
    public int compareTo(Student another) {
3 E% l" c0 K1 |# a: \8 B# a        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
7 v2 m+ _1 W, a0 v         */
        if (this.score<another.score)
$ \4 N$ f+ P, n9 T- {3 Q8 [            return -1;
1 c& ^1 G) D- o, _. |7 m3 `        else if (this.score>another.score)
$ \0 P- E  p% L, j8 M. R            return 1;
3 H3 ]1 O/ n4 ?2 x, Y' g        return 0;
        //return this.score - another.score
) q' n, C, B( M( z( K    }
" {: E2 D1 e9 J
; h# k: b; @9 b+ v0 J. ~4 ~    @Override
    public boolean equals(Object student) {
; Y2 V3 Q, h, v        /*
+ p( s& X6 [9 k2 s. ~        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;

        if (student == null)//如果传入的对象为空的话，则直接为false即可
' ^4 `3 O) v: I& T) _' [            return false;
) K# s+ w* e0 ?, d" I3 \+ t5 T
        /*
- Y- _% p2 y/ [        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
: c% Y" m0 P& f1 U        if (this.getClass() != student.getClass())
5 C0 D. B' n5 ]& J/ e            return false;
, {/ J, ~5 D$ x$ w
        Student another = (Student) student;
- {# f' V1 K9 E& _1 x8 ]( ~5 x& j        return this.name.equals(another.name);//写比较逻辑
, o  \: I6 n, h7 E0 S* S    }

    @Override
. T3 D( q& r  l# A1 o+ V8 Z    public String toString() {
        return "Student{" +
8 P7 U9 _, A! w% x5 |# z# @                "name='" + name + '\'' +
                ", score=" + score +
3 @) K% y% e8 V$ |, E                '}';
    }
}
4 o: n2 J8 R! |" J1 k7 E0 Q
主方法实现类：

public class SelectionSort {
& R3 T7 s0 O& ^" q) H- ]
1 X1 a% y. x) j5 i7 Z" [9 G    public SelectionSort() {
    }
: F( P, |$ P! o
    //
    public static <E extends Comparable<E>> void sort(E[] arr){
6 H( U. ^- b6 p& ?        //arr[0...i)是有序的; arr[i...n) 是无序的s
2 z. r4 I7 J( }, C8 b# i        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
5 O8 w! V4 }, Y8 \7 w& A( i            int minIndex = i;
            for (int j = i;j < arr.length;j++){
' N& s# ?4 ~. k# h                //在剩余的元素中找到最小的（比较查找）
( F# l  \, \& C. Z                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
! O5 d# N9 O2 X& p                 }
            }
( c! ~2 I0 p" C" K2 l            //将arr与arr[minIndex]交换位置
! H4 G" ]& F* @            swap(arr,i,minIndex);
0 }3 E1 o  r) T3 g        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
$ C& n1 T+ d1 J6 E# M& k5 i        arr = arr[j];
        arr[j] = t;
7 t5 e* k" Y4 `+ [) d( r: b4 s    }

    public static void main(String[] args) {
# N% l" T+ F# g1 F* `' t        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
5 M* M/ \2 ]6 v  [  a& d- g        }
        System.out.println();
. \. L$ v6 b. u. A3 F
2 z* Y5 w6 {0 b9 @* D* H        Student[] students = {new Student("Alice",98),
$ ?! w5 l7 T6 W9 {$ O1 b                              new Student("Bobo",100),
( B$ y- h! x# o$ b0 P; G                              new Student("xiaoming",66)};
/ W: o! {6 M9 T' B0 K4 ]8 Q: X
        SelectionSort.sort(students);
        for (Student student:students){
3 r8 M0 p& x: w, a            System.out.println(student+" ");
        }
* g: |- j1 t, I; M4 z. k/ ]
    }
$ o: Z* k9 _( P7 o' f}
- f6 _/ R' l/ ~+ J
复杂度分析
  v  L2 H  Z0 r8 m( a9 ?" A        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。

, p1 l7 L' O/ _1 o  N8 S
" I4 O" t8 m$ e! Y1 r5 r
首先在ArrayGenerator类当中生成随机数组

    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
5 f( Q  O" a% w$ a        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
7 _) u2 B% A0 |6 A" n0 W            arr = rnd.nextInt(bound);
6 F+ B) M% n- l4 m" y& f        return arr;
    }
# G, l8 V; Q$ K% a4 k判断这么大数组是否真的排序成功：

7 `# z/ m. N8 y( Jpublic class SortingHelper {
    public SortingHelper() {
" k' E: P$ o! z2 u! S. f    }

# c7 _% f3 B$ t; y" m/ J    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
8 j- O' i, q  [4 q/ e& q        for (int i = 1;i<arr.length;i++){
9 l9 I; [3 }% v) U+ b0 A4 f            if (arr[i-1].compareTo(arr)>0)
                return false;
        }
        return true;
. l1 \; f, }; d6 p$ B" g( M    }
5 ]' W+ a. b. ^$ o$ Z}
在SortingHelper封装一个test方法用来测试任意一个排序方法：

    //封装一个test方法用来测试任意一个排序方法
5 i$ k' L' ?1 @- |    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
; y3 G$ \, y% c- I% f                SelectionSort.sort(arr);
1 z- {! t. L- ~4 i  G            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
/ \9 k+ ]$ g  U+ j1 v& ]2 h9 C            if(!SortingHelper.isSorted(arr))
0 F% D( H% G4 {2 X. y                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
0 c! j2 C2 r. i- @' c6 {    }
测试时间：
% n5 a* p$ `/ [! |
' P: ?. m9 j! w2 `4 }public class SelectionSort {

) g1 k* u/ Q5 a  `" A" P    public SelectionSort() {
, ]7 l" }% b. {* N5 }    }
# w2 x; N$ [7 P8 |/ i
4 y0 v8 K% A* C8 H+ b  O% V: ^    //
    public static <E extends Comparable<E>> void sort(E[] arr){
" G2 W2 A) m" Y0 [1 ~        //arr[0...i)是有序的; arr[i...n) 是无序的s
/ F, A, b6 l; @0 b        for (int i = 0; i < arr.length; i++) {
' v2 K4 |2 g/ C7 u2 x. ]) j- Y            //选择arr[i...n)中的最小值的索引
  m( A+ X# k( ^            int minIndex = i;
            for (int j = i;j < arr.length;j++){
& Q$ w9 T0 c3 D; b; x6 l# L                //在剩余的元素中找到最小的（比较查找）
2 S8 d( O) ~/ K; L                 if (arr[j].compareTo(arr[minIndex]) < 0){
' K$ N1 O% B: o- c6 W' s                     minIndex = j;
& Q0 L; ~; p  `/ e                 }
: u7 o3 d6 H" a$ d& _* A! T            }
% V  e0 N1 X3 A1 @0 T            //将arr与arr[minIndex]交换位置
: b/ B/ n- I. N. |3 V' {            swap(arr,i,minIndex);
        }
: Y. d9 V/ z. M% e+ i: c9 G( `    }

5 Q& u$ C3 B' S- _) [# O$ v7 P    private static <E> void swap(E[] arr, int i, int j) {
7 F0 U+ Y. `1 x        E t = arr;
0 `* S8 O, k3 D( I$ r1 ^        arr = arr[j];
        arr[j] = t;
- t7 d3 J; K2 X7 F9 V; Y( _+ B) {    }
) N. W4 O3 j4 K/ G; }
    public static void main(String[] args) {
5 k  J$ l$ u, `' I  K        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
: [) m- W; H# _) y0 Q}
- c% d) P, e' e1 F/ G$ Z; [4 h
. _; Y# s$ O/ w$ N其中如果要测试两组数组：
' r$ ]# t9 ?- c/ m$ ~
, N& u1 ~# U2 c0 g6 O: c    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
/ U: }  I3 p4 E            SortingHelper.sortTest("SelectionSort", arr);
        }
    }


可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
" l$ C) [# `( I3 t5 t

, S  @' U, d7 L5 b' ~) T

1051373629

感谢楼主的资料
2 w" Y, k+ d' B0 X5 D, t