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

杨利霞

算法与数据结构（第二周）——排序基础：选择排序法
. E0 R( ^# p- E3 z: A8 ]目录

选择排序
2 `  S* h. [4 M9 {3 m, ]" g
; J! p7 o( t5 w" ^选择排序简单介绍

, ~6 q6 f- B: @& C- B/ n实现选择排序法
# L% q" _4 w  H6 q+ y6 U/ _
* L& `# g8 ]# K  o% i! U使用带约束的泛型
8 ]. _3 k  U) z  E8 W
: v# f# U2 D. \8 r/ ]) V; c" k使用 Comparable 接口
; `- A9 O, R8 C5 [* V
; z, j! g, o. B! A7 _+ q3 n2 I复杂度分析

选择排序
# L  k& G- S( F$ n2 h. v- o选择排序简单介绍
: v. \4 U) `; O: s$ W3 u先把最小的拿出来
5 H. z* {* t# V0 E) B. ~$ h2 ]# c
剩下的，再把最小的拿出来

6 H7 }) m0 S# t# C- F0 S剩下的，再把最小的拿出来

......
/ ^  Q% Y3 {+ G' h
每次选择还没处理的元素里最小的元素

        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
2 A9 d: V' S1 M+ B$ Q
7 ]# I; i  l$ z& J. h) K  z* K        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。

5 C- N6 q0 _* N) F' u/ Q% v实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。

5 h' b. M7 u" m8 h+ z        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。

4 r1 j& M# ~  k5 cpublic class SelectionSort {

! K# J3 B* @  K$ M    public SelectionSort() {
    }
" \- {5 e4 Z/ m! G% ~$ E
    public static void sort(int[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
' m  _1 |6 o4 D- N* d) c        for (int i = 0; i < arr.length; i++) {
1 A3 q; X/ z/ n; Y/ l. V+ Q# w$ g4 n            //选择arr[i...n)中的最小值的索引
0 |0 f2 P4 r( G& A  d' J            int minIndex = i;
# p& G$ K# x! F2 D8 K  O; |6 u" @            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
) r* W) Z5 L: y2 z' w8 b  I                 if (arr[j]<arr[minIndex]){
* ]5 @6 f4 i4 n0 ]9 }; k                     minIndex = j;
                 }
9 D- c5 c' |1 n$ \! ^            }
& z. I' i  I) e+ m; b$ l! ^            //将arr与arr[minIndex]交换位置
; i9 k2 i) W! t6 ]" j) G8 ]            swap(arr,i,minIndex);
        }
    }

    private static void swap(int[] arr, int i, int j) {
0 ^# f! `0 S) }$ o- C        int t = arr;
        arr = arr[j];
9 l1 D; ~) L6 l: U7 E        arr[j] = t;
    }

    public static void main(String[] args) {
        int[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
! y& c7 C4 w4 u7 u7 \" X        for (int item:arr){
            System.out.print(item+" ");
9 I, q1 Z+ h# E        }
1 V* U3 g- v+ X$ @& @    }
}
8 D& d3 t, D: Z$ r1 V
7 p! v+ o- g$ f  [; t2 O当前只能实现int类型的数组进行排序，因此需要使用到泛型。
6 Z9 _  z1 w5 N6 u9 y
使用带约束的泛型
1 F# [7 ]# `2 W        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。

public static <E> void sort(E[] arr)
6 J. g( i+ f5 Z# r, g" s        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
6 `8 s3 N/ Z  ]; V3 Q  s8 \0 x
" k( C8 K1 k3 _: Mpublic class SelectionSort {
9 y% s. R" e% e0 [; H# `8 E
2 I+ g) W9 D: ]' T! ?    public SelectionSort() {
    }
) s% K) W* b# A) A, `1 N2 _
  ]# }& t1 ?9 d0 V% |    //
( @; t5 s1 H$ ~5 C    public static <E extends Comparable<E>> void sort(E[] arr){
: c- n2 p+ p& G3 O$ p7 I  Q        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
. A# `9 q8 P4 Q& `) }- f! i            //选择arr[i...n)中的最小值的索引
, ]/ t- ?0 E' }; i/ F            int minIndex = i;
            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
1 h" w( q: s: B2 u. U& l* |& o                     minIndex = j;
                 }
6 i6 p( P2 @, q; W" d; y8 B            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
2 m6 o# x: p5 U# e0 A9 D( O1 O    }

- ?4 E9 ?5 Z1 a6 `- p  N    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }

9 @& t1 d7 M8 a1 b, j) Z* ?) m    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
" t4 i0 O9 x: w: V) V  [7 v( X        SelectionSort.sort(arr);
        for (int item:arr){
3 o* j: L  D% @. e            System.out.print(item+" ");
3 ^9 e; I. v- r  v- k! K8 [8 g        }
    }
" h, x) i0 I4 b" c}
- v# L  R  ^: F( Q% t
        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

使用 Comparable 接口
        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

import java.util.Objects;
* w5 S  W/ ]' t" [$ J. L
public class Student implements Comparable<Student>{
    private String name;
    private int score;
9 K& {3 H4 q0 J9 V) k, c9 q) _

    public Student(String name, int score) {
) ^$ a3 Z3 m8 L  u$ y        this.name = name;
: _: w5 l  i/ R& Y& t; s        this.score = score;
# h7 \! w, E# o; F9 O    }
" [* W4 \9 i- b
    @Override
7 z  P2 i* a4 }. E% O- T    public int compareTo(Student another) {
        /*
        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
        if (this.score<another.score)
            return -1;
        else if (this.score>another.score)
1 j: ]6 p3 I- u8 D5 c            return 1;
: U+ D2 \. V1 ~! r, ?  f        return 0;
) U0 B2 D$ f2 Y% b# U) A% ^        //return this.score - another.score
+ D/ p: y( R  h$ F9 E    }

    @Override
. [- {' N% o( X, B2 x" T    public boolean equals(Object student) {
# `9 [2 P) a# g; l        /*
        强制转换有可能出现异常，因此需要做出判断
        */
        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
9 B" v2 Y7 H# f  W/ L. x7 j0 x            return true;
7 l; H- E& Q% d
        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;
4 W$ L$ q9 {  i9 {. S) H
        /*
        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
- I( H# K3 s: w9 e        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
        if (this.getClass() != student.getClass())
            return false;

        Student another = (Student) student;
+ d( Z: I# I7 K2 z: s" j; {! d1 q        return this.name.equals(another.name);//写比较逻辑
) s) v7 s4 U+ P$ f* h    }

7 S: h' i: l0 m  E8 V& A1 j    @Override
2 J! `8 y7 i6 h: a' A    public String toString() {
/ O- @4 R- C8 \        return "Student{" +
' p  J" e6 P# k" K( }8 q* Q3 u( Z                "name='" + name + '\'' +
                ", score=" + score +
6 Y3 h( B5 f& \& a                '}';
& @; M# z. H, o& y  A% f3 ~" B" |& ^    }
}

+ A& p9 W2 Y8 N0 t. f主方法实现类：

public class SelectionSort {

    public SelectionSort() {
% j) v! P+ @3 Z6 k  W  F    }

: b* S; }( A' v    //
$ m+ ^6 K7 ]# i/ i0 s: G    public static <E extends Comparable<E>> void sort(E[] arr){
, F; }7 D0 G/ m2 o# |/ g3 Q        //arr[0...i)是有序的; arr[i...n) 是无序的s
6 }4 K9 P; m  b8 k        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
4 m: c3 A. J$ C  y  i$ S            for (int j = i;j < arr.length;j++){
                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
: D/ W7 x, D5 j                     minIndex = j;
                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
. O. f1 ^9 l; X% H$ r    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
4 l! f) Y) W  r( q- B        arr = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
% ]8 X+ X' @3 |0 p; x) |5 O4 I        Integer[] arr = {1,4,2,3,6,5};
4 L! x0 r4 b6 A+ g6 l        SelectionSort.sort(arr);
- P# d/ Y+ Y2 L9 O        for (int item:arr){
  D4 q* y! Y; H4 J/ L0 Z; b. c            System.out.print(item+" ");
" X+ ?9 I6 {; z. c& z        }
$ d) u* E+ K5 R# |6 O& ^        System.out.println();

        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
+ O% o9 z# N. U( \& d
        SelectionSort.sort(students);
        for (Student student:students){
% A: C7 P- a* Q. Z+ X) ^            System.out.println(student+" ");
        }
) Z% m7 B1 ?+ @- H8 N/ t. a5 m
! G, s6 X9 d. H" V% Q4 e    }
1 i/ v' t6 n& ^9 x+ `0 h7 t9 G5 p}
' h8 k& X! v! E
8 u" t/ \8 h& B& `, S0 T复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。


% L* c: y; I9 J1 D4 w4 A
首先在ArrayGenerator类当中生成随机数组
3 D6 t% ]' |6 Q
    /*
    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
& L2 K. T9 t. `3 i/ s     */
$ [5 }+ M+ A' x$ `    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
7 K- H  D- s7 s        Random rnd = new Random( );
        for(int i = 0; i< n;i++)
            arr = rnd.nextInt(bound);
8 O; B! ?: ?; ]" f) Q( P, M1 [        return arr;
    }
+ P3 x4 f: h5 o# e/ ^" L% C判断这么大数组是否真的排序成功：
1 `0 V: [% r3 \0 ?7 F/ p7 A1 R. O
public class SortingHelper {
& t2 u, W0 I+ ~2 H* \3 u4 ?# T    public SortingHelper() {
$ `2 @3 P0 v3 M2 H* \6 N    }

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
" v4 i$ A& }& S2 H# \, W        //判断数组前一个元素是否小于后一个元素
. j" W: t( Y3 [2 q" ^* k5 W        for (int i = 1;i<arr.length;i++){
            if (arr[i-1].compareTo(arr)>0)
                return false;
        }
& _0 u/ e2 t; Z2 S9 }        return true;
    }
6 I5 V1 z+ e; {- h4 e}
$ J$ |, U# N( W' Y, B& f2 D  n在SortingHelper封装一个test方法用来测试任意一个排序方法：
0 ?! N9 D* a" G6 s. I) n4 r
: C( A/ F* E9 Y/ b7 V    //封装一个test方法用来测试任意一个排序方法
    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
8 [* }5 E; i0 U( w" w            long startTime = System.nanoTime();
            if(sortname.equals("SelectionSort"))
                SelectionSort.sort(arr);
: w- A8 M8 k2 s7 ~% ~$ I* p            long endTime = System.nanoTime();
8 A5 O; L5 B% k+ o0 o4 K            double time = (endTime - startTime) / 1000000000.0;
            if(!SortingHelper.isSorted(arr))
. o& e* ^, m$ b3 M  j5 k8 n                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
- p- {' g7 R- h# a. R: S    }
测试时间：

2 e5 S5 W. u4 ~1 S! N* }" qpublic class SelectionSort {
, M" c/ Z! q" a8 ]7 f0 V- ~
    public SelectionSort() {
    }

    //
- u  [/ Y1 }9 p' H  }    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
! v& _; k4 E! J) {. S, V        for (int i = 0; i < arr.length; i++) {
& i0 b5 r3 v7 L( N" ?) I            //选择arr[i...n)中的最小值的索引
% b5 I) w: J" f. q0 {( @            int minIndex = i;
            for (int j = i;j < arr.length;j++){
' X8 d& t- g! Z- W! X6 t2 f                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
; l, i3 z( ^- q5 Y& ^: W+ m' f1 s                     minIndex = j;
5 Y' @3 ?7 `- K. z2 ~3 Y                 }
# w4 `/ m- ?9 ]) Q            }
- z0 s/ ]$ u! d4 D8 p6 q5 w            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
; l- E! L+ v$ v# T- S        }
    }
, U; m, k, D6 @& d! c
& H: E4 e9 f! N* l    private static <E> void swap(E[] arr, int i, int j) {
. L$ n: Z1 n$ ], W        E t = arr;
4 c4 H0 U' u! U8 f        arr = arr[j];
$ C2 U! @/ J  ?; K        arr[j] = t;
# P- U. y3 `8 h9 M9 k    }
& t+ j" a  a4 X+ l' h3 H% t: C. l
    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
# Q! c+ `, o! \& ]3 o9 L        SortingHelper.sortTest("SelectionSort", arr);

1 e& N! \) g: K; O+ L" y! E    }
* G  x8 f0 z3 D# n* I/ t6 K}

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

1 @: e( U. z& Z$ I! ]    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
8 k1 \4 s: C4 R* M3 M* g        for (int n:dataSize){
6 K, \% ~3 H: O5 ^0 w            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
* `- S! w- i: ~* s  H6 T- p            SortingHelper.sortTest("SelectionSort", arr);
0 z0 o' u9 q/ v6 g. n6 A        }
# v3 V/ ^/ D! U  u    }
* \6 n/ x& g1 N7 a# D( G; O

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

1051373629

感谢楼主的资料
& G6 H/ K, u  P0 j" u