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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
! a/ _- W# Z# j
选择排序

  H  I! S; @( S- A选择排序简单介绍
$ F3 v& q3 Q7 R4 e$ f
实现选择排序法
8 e9 b8 g# Y" J. z
使用带约束的泛型
; k$ B! X/ a/ j1 x! t
使用 Comparable 接口
7 ~/ _1 y) u! x1 X& h
9 L+ f9 t" B( I复杂度分析

选择排序
/ ~8 y) ^, c4 b$ y8 w选择排序简单介绍
" C3 s6 r- Y# K4 h5 s9 ~2 E先把最小的拿出来
5 f  M+ j: g, `9 g3 h$ q: m
剩下的，再把最小的拿出来
* y! n3 z5 c! `7 K* B; B/ r
剩下的，再把最小的拿出来

......
* G: P% ~$ T8 |& E  R
) y9 x! b. u: a9 ~每次选择还没处理的元素里最小的元素
8 W+ Z9 Y2 h5 h7 k
        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
! c  |3 r2 F: o
5 k2 M5 T4 h, `% A- W5 z        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

. Z, O& s/ n% k2 @6 l实现选择排序法
' a) a6 n- {1 U0 w1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
" u/ q! M  q' Z. c/ ?2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
' F! A' j2 @, X0 K' e
public class SelectionSort {
, O4 q* ~. Q7 Z
0 |3 d% a# e( \$ k# d2 t+ n9 F    public SelectionSort() {
: `  i5 V8 C6 a4 s) \    }
/ T2 k4 e" Q- [# g+ K
: G' }( v1 p! k4 l    public static void sort(int[] arr){
) C- o" D6 M: Y# e$ j        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
$ J' e! T: I( e5 ?            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
* @5 A. L( Z- D& {                //在剩余的元素中找到最小的（比较查找）
, t% U4 \5 ^" r0 E                 if (arr[j]<arr[minIndex]){
* L7 ~  E1 `5 o4 W                     minIndex = j;
! d1 ~. s, R5 z0 S* E# O% s9 A; G                 }
            }
* K& O$ y: w0 _5 h            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
; a# Z' t1 g$ I+ P        }
3 Z/ M2 w3 B" W6 |% [& D5 |9 C    }
# u* S5 f- r4 r  j: V! E) s
    private static void swap(int[] arr, int i, int j) {
+ f2 f. m; r$ R        int t = arr;
        arr = arr[j];
) f  K! [3 J5 o, [8 R        arr[j] = t;
, {  q9 j0 r7 \& O( Q    }
5 r$ o4 B2 X; l+ z
    public static void main(String[] args) {
6 S% {) O5 M, b6 o: p        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
5 P( }9 B. c' W$ }6 |  [            System.out.print(item+" ");
        }
  z8 s, H; }% q2 s) c8 v! e    }
}
$ P. B1 k- \, A5 _! y& C8 n( x
当前只能实现int类型的数组进行排序，因此需要使用到泛型。

% j% G! }% N7 D使用带约束的泛型
6 M% r1 H6 w  x, b) ?5 }        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。

public static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

( q2 p0 I. |. j! Tpublic class SelectionSort {
4 Z& u- c" g4 a/ d
7 e! B2 O# A  E1 I( V; E. y. ^5 w3 g    public SelectionSort() {
    }
) _5 u5 ^4 B2 p4 C- I- x
2 q- b% E! D; p1 \8 _7 i    //
) h9 H; m( |9 p' `  n; Q" v    public static <E extends Comparable<E>> void sort(E[] arr){
) C, Z' i0 @: V4 [- l        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
; z0 @3 e5 L; p( v: {* T9 K            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
- {/ n' U/ M  b- s                 if (arr[j].compareTo(arr[minIndex]) < 0){
+ E* F! I7 S6 {5 s) ]/ ]                     minIndex = j;
4 T  {' X; y0 T7 w                 }
            }
  y3 T* ]6 ]  }4 m            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
- D8 N& F- S. ^1 X. y5 }7 y        }
    }
7 v2 _" o) ~0 x6 I6 z
    private static <E> void swap(E[] arr, int i, int j) {
$ w, t4 J# }6 J' _        E t = arr;
; U+ C7 k: D* `7 ]        arr = arr[j];
  r5 E8 q7 ^# C" {/ o1 r- R        arr[j] = t;
    }

    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
" D' h! N0 E$ n, g! X        for (int item:arr){
            System.out.print(item+" ");
        }
6 p5 {1 u! Q& s( |: ~& J    }
; I- H/ T" g4 ]}

) d" i5 _. q* ^0 q  F1 ~6 h        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

使用 Comparable 接口
: l9 \8 f. ~' o9 h% e7 u        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
( K. d2 X; H# X: Z( h* M5 K
& _5 h) Q3 ?" d( a; y# Nimport java.util.Objects;

6 e8 ^, R1 i2 O4 n; M( kpublic class Student implements Comparable<Student>{
    private String name;
    private int score;
1 @! _5 Q7 m2 A' W! l

    public Student(String name, int score) {
        this.name = name;
. k9 B5 E! Y1 E6 z/ `1 j2 f2 _        this.score = score;
& ~1 W1 k# T6 j; [0 Y/ l    }

    @Override
    public int compareTo(Student another) {
        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
( ~$ J: s. c3 O         */
        if (this.score<another.score)
            return -1;
        else if (this.score>another.score)
            return 1;
        return 0;
0 J1 T* ]4 Z) [3 v        //return this.score - another.score
/ m, U# ^) r3 g' X    }
  ?- [- b( U7 L* X: j. h
    @Override
0 y" G# P% [" h! y: q! x    public boolean equals(Object student) {
; D+ J9 i$ O1 `7 |" |2 r9 W4 D        /*
0 H( ?$ d6 K) [8 G        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
5 r/ ]2 B* [: m/ z( g3 c            return true;
) \6 B( n6 C  v
# w2 {4 `( y. ]2 u8 X& Z6 b9 h        if (student == null)//如果传入的对象为空的话，则直接为false即可
+ b* {6 s( s/ J" D- y$ c            return false;

        /*
& f9 i+ o  B: z4 N: E: ?$ A        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
9 D8 l5 v3 u+ S4 W5 \! X        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
- I- S( |* e1 b( ?        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
$ E: P6 [/ g7 s, z        if (this.getClass() != student.getClass())
            return false;

        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }
& W9 U* P1 F- m/ y  E
' O$ }7 u8 _2 N    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
8 T, u' V' s+ G                '}';
( _& I1 O0 X& ?/ [' N/ G    }
5 V3 V5 f7 f& n  K4 n}

主方法实现类：
; I" j2 F3 u9 D- o2 m( |5 t
/ x4 N$ S# F3 _! y. Dpublic class SelectionSort {
: @% C' i$ v6 a$ u* I
; R" ]5 N' x. n& ^+ @- x4 x    public SelectionSort() {
    }
# c- q8 k2 K9 v7 E: x' E. I
    //
    public static <E extends Comparable<E>> void sort(E[] arr){
8 `- W# g- S: Q2 p  }        //arr[0...i)是有序的; arr[i...n) 是无序的s
# c  T6 L; D6 _* F( z. T' @" O        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
: }7 B2 ?2 R+ A$ q& r0 I                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
- _! y. i5 n6 f6 z                 }
7 ]( p" {/ C, |* o' Y8 z1 ~            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
3 c( n9 G5 j5 _& N        }
  V6 j7 c% u( a0 [  ]3 f5 C! k    }
( Z; p9 e! R% {' X3 s
    private static <E> void swap(E[] arr, int i, int j) {
" ^6 n1 j& a& P$ P        E t = arr;
        arr = arr[j];
' k6 P1 X8 b; [  g! x9 i        arr[j] = t;
    }
0 ^9 q6 a) D. @" l
    public static void main(String[] args) {
" r, @2 `$ A  V* T& ]        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
! O! N, ~+ I4 h, c            System.out.print(item+" ");
0 H, G; i; b5 }2 u        }
        System.out.println();

        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
3 |; F5 Y+ w) x$ l9 Q9 p" B- T                              new Student("xiaoming",66)};

+ ~  R& t* G+ V" f8 ?        SelectionSort.sort(students);
        for (Student student:students){
            System.out.println(student+" ");
' A" @5 U( g" B2 v$ O+ W        }

    }
% N5 T4 B5 N  n7 m  W# l% f* o}
) e0 l" t$ e* T1 U2 H
复杂度分析
% |% i3 r: u4 l. d0 o/ h+ O        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
- }) C2 s' }- X0 _# o- E( [
2 S* ?  w9 a7 [, s9 ~2 N: @
0 E0 |" B% y4 D% v7 ?
首先在ArrayGenerator类当中生成随机数组
# p: a! A/ d' T# ^( O6 H
; A- K0 \! j! P) R    /*
3 _9 @8 w1 f+ b6 s4 c: [    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
/ {5 k% j* m! `( n) @) z8 b    public static Integer[] generateRandomArray(int n,int bound){
3 Q( E" p( Z6 }1 V( P, w        Integer[] arr = new Integer[n];
! T1 h4 n8 |2 z% o3 i8 j        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
( n0 F8 P" w, w        return arr;
    }
4 j" e, d* G: E! F- |" a8 C( \$ P7 n判断这么大数组是否真的排序成功：

public class SortingHelper {
& A- z. A5 ?3 |9 N. U  v) p    public SortingHelper() {
" [* g3 T8 F7 y  w2 K    }

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
- ?$ C* g2 R+ Q1 a' y" W% v        //判断数组前一个元素是否小于后一个元素
. x1 M2 B! r, E# P& u        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
  F4 C7 w6 s! C4 M& `5 d, J/ \                return false;
        }
; X8 P* K( K# Y# K( x, J        return true;
    }
# y* L% N$ J* L/ Q( Y7 {6 Y  c}
在SortingHelper封装一个test方法用来测试任意一个排序方法：

& y, j  M# j- }. j9 f7 @    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
- Q* y' s9 W5 f" y$ t/ T9 |" N% |            if(sortname.equals("SelectionSort"))
( B: I/ Z$ Q- q6 c8 Q                SelectionSort.sort(arr);
            long endTime = System.nanoTime();
0 @( c& D9 a/ u  v# Q+ n# m            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
- x, w, z/ b6 l, C! b            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
' y$ h5 r( }: |# X4 G    }
测试时间：
8 t' |7 c( A: E5 t4 H8 `1 g6 F
public class SelectionSort {
3 Z% v! P2 I7 F
* l- }* ?" K5 O! I/ h9 H) ]    public SelectionSort() {
    }
' R  K  N: N! \) h: e: O2 ?2 d: t: i8 |
+ E4 z1 E. Y2 `" W+ U! P    //
    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
1 S" W( w7 |* o: r# f        for (int i = 0; i < arr.length; i++) {
. ?* l& Z1 A- v- i, T            //选择arr[i...n)中的最小值的索引
3 @0 e" C$ Z* Y8 ]3 \            int minIndex = i;
' m$ J1 _8 z3 L" l1 w            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
+ M. X. y9 i3 C: v                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
# l( w( l! ^2 L( `3 _) @                 }
            }
& L, B  l  d/ w# e  s            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
1 D' J$ N. s* p% k& ?        }
    }
9 A% C2 v8 {& @, ~: z6 D; l& u) R
2 g' N3 u; t2 @' H5 q    private static <E> void swap(E[] arr, int i, int j) {
0 L$ I9 ]2 f; R5 f, S        E t = arr;
        arr = arr[j];
' ^+ R$ p8 E" V" d/ `        arr[j] = t;
/ z8 i6 w1 {& n  G$ R8 a, z6 z3 Z    }

    public static void main(String[] args) {
; Q! A5 `1 c% J9 O' D& O9 {        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);

    }
0 f2 u# m" e7 [' ?2 ]6 f7 S}

其中如果要测试两组数组：

    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
3 J" I1 u8 k& {+ X) l        for (int n:dataSize){
" T8 m: ~' ^7 |, j7 r9 P            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
        }
    }
$ T+ j( M7 w2 `% Z

; ?) V( g3 N, n8 ] 可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
————————————————
# ]% D! j3 g" g) x8 W! F版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 f$ k7 g1 I) }  i  e: U原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122

0 r! M( i+ i+ p8 i& S; f# @
% U, X: _6 A8 H  u8 r" {) X+ C

1051373629

感谢楼主的资料
3 ]/ M  k2 I! H