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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
目录
$ O  w0 _) l+ s$ h* H
' q" `& o2 o0 w5 e8 g选择排序
5 e7 M% e+ S  m) c8 j' z1 D
选择排序简单介绍
4 W8 I; Y; u3 ?
& F! J& {% k( b% Q5 U! \8 `0 ^, a实现选择排序法
+ n+ L! [4 m6 y( p/ \4 c, @( D
使用带约束的泛型
" y, y  F5 |  G/ D8 d1 m# |7 c
使用 Comparable 接口
/ @5 K7 Z: ?# a& k2 ?1 O7 g+ [
复杂度分析
; x/ ?' H) i8 X0 \. A
选择排序
选择排序简单介绍
先把最小的拿出来
% m4 Z( j, ]* G4 q/ `5 b
9 U8 V: n% ^9 [8 c剩下的，再把最小的拿出来

剩下的，再把最小的拿出来
5 Z+ j. i; {4 n2 c! H; |% P, Y
9 @" ~- A  n7 L* ~! _......

0 x7 ^5 o! T  _6 J每次选择还没处理的元素里最小的元素

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

        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
# C  Y7 \; _2 p
9 j6 p+ V2 u5 {1 \) O实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
% L7 ~6 z+ \' M/ W" X3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
. v) ^8 Z& T3 s: W0 \! M/ N
        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
0 j5 `, Y# F' F7 q- t  B
public class SelectionSort {

    public SelectionSort() {
    }

' `6 X( K' {; O% w$ J% l    public static void sort(int[] arr){
' x! d# c; ~* D7 q- g: F        //arr[0...i)是有序的; arr[i...n) 是无序的s
. y' U' a; }0 X8 l8 h- i        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
  k2 {! S7 g) U                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j]<arr[minIndex]){
+ d' I" M: M0 d4 f1 ^8 Q% |                     minIndex = j;
$ T& J* k# n6 o7 n" X                 }
$ e# Y. [* g% `- H. p( S6 w$ D            }
3 p; ~( b6 g5 c0 ~4 T5 d0 S            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }

) p  p: q; ~$ j8 u# y, ]    private static void swap(int[] arr, int i, int j) {
        int t = arr;
        arr = arr[j];
        arr[j] = t;
/ q1 `0 d. q; v! E, o& U    }
( t+ J8 \% q* f+ g( |2 {+ G
    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
        }
    }
}

2 k& u( ~+ D1 u3 K当前只能实现int类型的数组进行排序，因此需要使用到泛型。

% W; w1 P* S( d1 a- v, ~$ M0 A使用带约束的泛型
  @2 A! ~2 Z0 s5 k, Y2 ^8 P        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。
& V! y3 w8 d  x: w4 ]" S
public static <E> void sort(E[] arr)
        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍

public class SelectionSort {
+ B# R5 k& B4 K: Y( T, d
. x. H* O- Z4 @    public SelectionSort() {
    }

4 I+ W; v6 i) p% Q' m8 k7 s% m' r    //
! D8 X" h9 l# M1 S& X( O    public static <E extends Comparable<E>> void sort(E[] arr){
; t/ g, v* B* b        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
3 s  T( n- r9 A9 `  d            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
2 |( Z5 C* l& G            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
8 ^" x+ ~# z/ Q" C                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
! x) C" L- ?% w& M( @/ i1 g2 C2 g                 }
! k8 d2 A: T' F5 }            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }

& z& s+ G- `: L( k    private static <E> void swap(E[] arr, int i, int j) {
& W% l& A' k  O' d+ G        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }

1 b6 B! w6 a7 T4 k+ z  D& y    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
/ y0 v' ]7 Z( e  D6 a        for (int item:arr){
            System.out.print(item+" ");
        }
    }
}

- s- N1 D: {/ b; N" _( h        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。
& u8 u# y9 A% w0 ~7 W0 b5 k
使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。
' n7 ^; T6 N  l" |5 e' f2 r! S& t. u
5 X1 W  H: d" g5 t6 v; r8 wimport java.util.Objects;

5 D! f) t. Z9 z. q$ x4 @% t0 Tpublic class Student implements Comparable<Student>{
4 V0 W1 R* S3 V* T    private String name;
    private int score;

7 O8 z! k- \6 A  i! ~9 a: }
    public Student(String name, int score) {
5 d; K, m: Y0 r' J0 ~: g        this.name = name;
" V% U' z0 V3 W" a. z4 I        this.score = score;
7 s6 ?; m) c( ]  A* R    }
9 |. S# W9 i$ p7 x& H
: a9 q/ S0 _8 [7 D    @Override
    public int compareTo(Student another) {
        /*
% x$ P( c% W4 [, `! g        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
9 L  b! h9 X/ R# a& i        if (this.score<another.score)
            return -1;
: s+ {0 w6 u+ f! X/ I        else if (this.score>another.score)
            return 1;
  @) ?" {* @& Y8 z* \: F% U" y        return 0;
        //return this.score - another.score
    }
: \3 W2 L! D. Z
) [6 ^4 a+ U0 O# y. J  ?) ~5 J3 h    @Override
+ |* |3 i' g+ s( E    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
        */
6 x$ g0 x- H) {6 }) I        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;

# |* }# p' b8 ~        if (student == null)//如果传入的对象为空的话，则直接为false即可
* V- r( _  |4 w! V6 Z3 Z            return false;
1 F: }' D8 n. q' ?9 }: w) T
  x- Y6 c1 l7 j" [        /*
9 [- G9 e& b, e! O        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
! C7 @" G3 ~3 n8 o/ S/ e1 ?        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
8 F; e3 A0 i" S$ z4 G  T& M) U        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
& R$ D/ t/ M7 g        if (this.getClass() != student.getClass())
' W) T1 {! R7 U6 L            return false;

1 G" x; r; C9 M5 ?2 v. Z1 ?9 q        Student another = (Student) student;
+ S5 ?$ |# `0 e! u5 {. c        return this.name.equals(another.name);//写比较逻辑
. d' u4 L4 G. A5 M3 ?2 A7 z2 B6 U7 Y    }

! e! c& y1 N; f$ ?1 P" g    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
* O6 J; V+ E& x" P                '}';
0 r% z9 [& c( A( [! r    }
}
+ F1 m; J4 S1 Z2 E: `) }1 m
  h# r5 p6 L' P4 q主方法实现类：
: R  w/ p; n2 G" `) a8 d& Z. l
public class SelectionSort {

    public SelectionSort() {
    }
* Q5 U. A! S1 h7 U& ^" S
! f. X( @( l1 c* ~. _    //
0 \; e7 N( U/ @7 J" }    public static <E extends Comparable<E>> void sort(E[] arr){
8 O" D" z& k1 D( ~. w, D        //arr[0...i)是有序的; arr[i...n) 是无序的s
' e& d) z6 _" z! w        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
$ m, R* y* b! A# |6 R! o5 h) e            for (int j = i;j < arr.length;j++){
# \' Q) X# E# A4 a3 Z# K                //在剩余的元素中找到最小的（比较查找）
' L8 Z6 A& E9 A% N2 S                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
/ s0 O( }" l9 G5 c0 m                 }
            }
! W' R) K/ ?  ?% T& P, x            //将arr与arr[minIndex]交换位置
) a. [! I4 u5 H& p            swap(arr,i,minIndex);
9 V( V' }! V7 w* I; ~        }
    }
  t1 V: @1 h6 j% R9 {0 Y3 z( n
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
- V" u1 `  c$ L) g/ o- ?        arr[j] = t;
. R: i1 }; Z9 a! ?. P+ h    }

    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
            System.out.print(item+" ");
        }
        System.out.println();

        Student[] students = {new Student("Alice",98),
  o9 \% m) h+ S6 K- w( d                              new Student("Bobo",100),
, t. x) N8 u3 w/ X$ ]* @                              new Student("xiaoming",66)};

* P$ o" n! G; I6 n        SelectionSort.sort(students);
* s( [/ W4 ^$ r. k  `4 _& D        for (Student student:students){
- ^6 S5 T4 z3 e" J+ D  h            System.out.println(student+" ");
        }

    }
}

* m! |0 m7 i: \9 Y% h: Z- s复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。
& A, Y8 F6 N" @

- U# b: [, f* V7 |- }
! r" J1 E* r* h# X5 J首先在ArrayGenerator类当中生成随机数组
3 V6 t! y' B5 V' z/ I9 p4 J
( I5 d: [! E5 o7 b6 O; Y    /*
: @# x: L7 K7 c3 {4 \    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
3 E6 M0 f( w4 G% Z( O' b1 |) G    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
  v: }3 u/ A8 R- g. G  d            arr = rnd.nextInt(bound);
        return arr;
    }
  }: m. V$ j4 m& c8 {% T  G判断这么大数组是否真的排序成功：

5 e. o' a1 r0 V$ T3 xpublic class SortingHelper {
    public SortingHelper() {
    }

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
        for (int i = 1;i<arr.length;i++){
# Z0 q# u8 G) U% i            if (arr[i-1].compareTo(arr)>0)
, u* y: H) I& o0 x2 n/ C                return false;
& s8 b9 t' }/ n        }
4 U8 \$ K$ \3 c# N5 H6 l  ?        return true;
    }
}
- B2 h$ F2 O6 S在SortingHelper封装一个test方法用来测试任意一个排序方法：

# Y2 J9 Q2 r( r7 z1 c    //封装一个test方法用来测试任意一个排序方法
: b1 u0 U& U* {0 O' q    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
8 ]0 T' V3 z6 S4 v' f4 Y            long startTime = System.nanoTime();
7 v  @! X; _4 }8 B/ \  J            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
; x% \3 Z% D5 Y' {( X            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
3 J/ ]8 [: k; M. F& ~            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
( o& r6 y9 @3 A; `5 b# o/ W    }
测试时间：
% Y* r2 C4 q7 f2 y! R1 t. _7 A
public class SelectionSort {

    public SelectionSort() {
    }
- ^) N- M. e. q# \' [6 H
3 l" I& v2 F7 W5 e, a    //
6 I6 M+ x$ G: Z1 P# w0 G4 S+ k- u    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)中的最小值的索引
9 m; G/ J6 K' P& \; I5 [) J            int minIndex = i;
            for (int j = i;j < arr.length;j++){
0 ?' T9 O% Z9 K$ p0 H                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
6 h$ w2 V# @+ J                 }
. {& `9 U. }; t# u% Z! D2 R            }
+ P) q1 z: y1 `3 L& d            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
8 d/ V/ d$ C& w4 q        }
    }
- Q# Z% H3 d; [: }( A. V2 a& S
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
8 F" |. D1 `  \1 |        arr[j] = t;
9 ?- L: f& u. Y8 i2 H$ o3 v    }

" ^9 L! Z# Y2 C' ?% q, q/ _    public static void main(String[] args) {
6 F9 S# Q# I3 [3 K        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);
2 c/ l; D7 u' l( N8 C# m" W
    }
& y0 M8 z/ \/ o$ M. [1 d}

9 X4 G5 G: t% N% G9 a4 }其中如果要测试两组数组：
, F/ P- y& W% }' ^4 U2 ]2 B0 r
4 o& X4 z, e& U$ B2 o0 E& e' F    public static void main(String[] args) {
: j+ J3 u+ t3 `: s" x. U: d8 l3 a3 x        int[] dataSize = {10000,100000};
        for (int n:dataSize){
1 J- e! C% i! E& a  B8 I            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
1 ~/ a! O8 Y. t, T- E        }
1 D# w; o) A! o8 B% T    }
" c( ?1 H0 Q2 a% Z* z7 P9 u: ~8 \
4 q" a+ a2 H3 g2 S. b, M9 W
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
# U* Y- M! @0 J& g& Y6 i————————————————
2 z/ _9 j" G  i' w% v版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! Q+ T) T/ Q5 a  _; K3 t7 Q  v9 t8 U" ~原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122
: g+ R- l' x/ ~; f

1051373629

感谢楼主的资料