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

杨利霞

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

3 G: \- X9 A! E9 ]选择排序

选择排序简单介绍

实现选择排序法
% c4 A. w* R( U7 }9 {: l6 N
使用带约束的泛型
9 J5 b! B2 ?0 x. a2 n% S
7 D5 J2 A" d1 n* D2 F) w( K使用 Comparable 接口
; \& v" t9 Q% s: G2 A
& u/ Q+ A+ f* R复杂度分析
' E( i; I5 S# u* B* V/ X  O
选择排序
. K7 ]+ A. }& `* c" [: ^& ]选择排序简单介绍
先把最小的拿出来

剩下的，再把最小的拿出来
+ A5 i6 o! e! n2 l  M" T" e; f
/ l& j+ u' B% a5 ~剩下的，再把最小的拿出来
' d" ]  T0 Z0 {2 G7 ?! t9 p
& R  @" B( y+ W% E......
8 o" y% g& Z# U: y
每次选择还没处理的元素里最小的元素
; t3 {1 J+ a) A3 p
2 |6 ^( E, ^" D# g) i        我们每一次找剩下的元素中最小的元素，我们只需要把这最小的元素直接放在数组的开头就行了，也就是直接利用当前的数组的空间，就可以实现原地排序。
. Q# F. a+ R' |+ A# Z0 [' X' W; }
        j从i出发，扫描后面所有的元素，找到其中最小的元素，将其命为minIndex，将其与第i个元素交换位置。
! _( Y1 X; f6 T( _, j  [. O0 c
, o; b, @: L: E" I实现选择排序法
1.首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
# C% j' K1 x! N- Z1 B1 R$ Q2.接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换。
3.然后，这样不断重复，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
& p" d5 Y  z4 c# N' d5 \
0 Y. p, k; R% l, W        不断从未排序的元素中选择最小的元素存放到排序序列的起始位置，然后再将剩余未排序元素中寻找最小元素存放到已排序序列的末尾。以此类推，直到所有元素均有序。
* t. m4 N% x1 s) w1 N
public class SelectionSort {

. ^, }+ K. Y/ j    public SelectionSort() {
    }
! I* R! u5 D$ u! ]
    public static void sort(int[] arr){
" Y$ g/ v" O# k- H; E1 }- E        //arr[0...i)是有序的; arr[i...n) 是无序的s
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
. l5 D" x. `# A  @            int minIndex = i;
            for (int j = i;j < arr.length;j++){
  T! ?3 A) N& Q9 x/ ]8 C2 A                //在剩余的元素中找到最小的（比较查找）
9 T5 J, x8 N; D( ~& P2 N, Z1 l                 if (arr[j]<arr[minIndex]){
                     minIndex = j;
0 Q! J; {, _; [+ \4 s                 }
            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
        }
    }
# B3 F$ v5 x$ v- ?  P" V- |. ~- ^
    private static void swap(int[] arr, int i, int j) {
        int t = arr;
        arr = arr[j];
        arr[j] = t;
    }

    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+" ");
        }
    }
}

当前只能实现int类型的数组进行排序，因此需要使用到泛型。
7 _& d% `4 @, ^& j5 i
使用带约束的泛型
        只需要在static后面加上<E>，就代表这个方法是泛型方法，他处理E这样的一个类型，这个类型具体由用户调用的时候来指定，相应的数组就可以指定为E类型。

public static <E> void sort(E[] arr)
- s. c$ M4 Q1 U* M( o  X* G7 \        但是e类型不一定可以用 < 来运算，所以我们需要对泛型E进行约束，使之这个泛型是可比较的（Comparable接口里面有一个泛型T，T的选择为可以与之比较的对象的类型，一般就是实现该接口类的本身，可以这样想和Person类比较的当然是Person本身了）。关于Comparable接口的介绍
, o% N) n9 h7 K( _9 h5 v
public class SelectionSort {

    public SelectionSort() {
1 O, j. {! k4 l    }
: @9 P/ }( O+ i. q
    //
- r" a' a' I" |  d    public static <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的; arr[i...n) 是无序的s
" m# B2 |( ]7 {# X- @5 w        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中的最小值的索引
" M/ ^! p" V- K' a' N            int minIndex = i;
            for (int j = i;j < arr.length;j++){
) r: d' Y: y5 Y* Q                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
& j  x2 z+ G) R+ [. b                     minIndex = j;
& e/ j. M! X/ M' J$ ^                 }
' m- U( K5 r. F* ^, \7 }            }
            //将arr与arr[minIndex]交换位置
/ j2 L2 C  z7 c0 D+ v  E  _" l$ {            swap(arr,i,minIndex);
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
( X+ f7 A' ~, d8 v. ^    }

1 }- p! `! d, p6 P& |  \; l    public static void main(String[] args) {
        Integer[] arr = {1,4,2,3,6,5};
0 y, f: H6 S' [( Z- Q8 w# j        SelectionSort.sort(arr);
" p  X- x1 q% M        for (int item:arr){
            System.out.print(item+" ");
7 y* J! a, E; ]  w0 \# n, M        }
  r+ }+ R) w1 J3 y; y0 C1 u0 u) T3 H    }
}
. T" Q5 h3 ^; W+ V* n6 U  g5 L6 G
8 b/ G; m. a5 ]6 Y2 o) v- J        此时方法已经修改成一个泛型方法，对于这个类型还有一个约束，其必须是可比较的，展现在JAVA语言当中就是实现comparable接口，很多排序算法都必须保证可比较。

" G, C1 r- x. x5 _使用 Comparable 接口
+ p9 v/ }5 o: v: I' e        为了体现将其修改成一个泛型方法的优势，我们使用一个自定义的Student类来实现排序算法。

import java.util.Objects;
& y0 Y5 T& N5 w. \! U$ t
0 C! }* V, c5 n+ Q2 ?public class Student implements Comparable<Student>{
    private String name;
( g. L2 `9 y' j& R& _    private int score;


    public Student(String name, int score) {
% W: }& D, A5 N/ S. v1 S1 k        this.name = name;
) P4 J1 C: Q$ E: l        this.score = score;
    }

    @Override
    public int compareTo(Student another) {
- f" F7 @& K2 e% y1 Y        /*
# p9 Q0 s! q4 J5 y, `        当前这个类和传来的类another进行比较，根据情况返回 负数 0 正数
         */
        if (this.score<another.score)
# J2 ~, k$ Q3 T3 |            return -1;
. Y2 E0 G6 `8 e6 H( A        else if (this.score>another.score)
            return 1;
        return 0;
  V3 _3 \4 H9 d2 s6 x2 l        //return this.score - another.score
2 O  B  U. \8 Y    }

    @Override
8 k+ L8 x" A# }    public boolean equals(Object student) {
        /*
        强制转换有可能出现异常，因此需要做出判断
        */
/ y; Q3 q5 C" c% Q- X        if (this == student)//比较当前类对象与传入的参数是否一致，如果一致，则不需要进行强制类型转换了，直接为true
            return true;
5 y: l9 o: F  n' I' @+ |
* t6 M; a# ~& Q- N        if (student == null)//如果传入的对象为空的话，则直接为false即可
            return false;

        /*
        如果当前的类对象与传入参数的类对象不属于同一个类的话，则直接为false，也不需要强制转换了
! u- v4 [: {& N* F' S1 B6 |& E        （之所以重写equals方法需要强制转换，是因为它的参数必须为类型Object，以此来涵盖所有可能传入的参数类型，
* W0 P5 y& j7 U4 J  k6 q' t. ~        而如果具体传来的参数类型与。挣钱类对象不同的话，则这两个对象肯定是不同的）
         */
        if (this.getClass() != student.getClass())
: U" f  ]% q! g            return false;

1 m9 ?! @: j) P. |, |1 L% K        Student another = (Student) student;
        return this.name.equals(another.name);//写比较逻辑
    }

    @Override
    public String toString() {
/ @: A; V% [' v% `- L" x        return "Student{" +
4 m* w) D; C+ K* R: g' F                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }
6 Q* G% e! J' N9 @' M! M2 r}

/ n5 n/ ~% v9 [6 G0 H主方法实现类：

0 B/ m! D: z3 b$ }/ g- l( c" ~3 \public class SelectionSort {

1 b6 C, s" @: ]( R! K    public SelectionSort() {
3 [' @8 R5 M3 @6 [    }

    //
* m% K5 w3 _- `. d    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++) {
7 _  j7 _- R7 Z. h$ T! o            //选择arr[i...n)中的最小值的索引
* I* D3 c' X3 W4 t0 g& I# q            int minIndex = i;
/ f! Y5 M. A; l            for (int j = i;j < arr.length;j++){
5 e* D$ G5 \# Q. j+ G  C                //在剩余的元素中找到最小的（比较查找）
                 if (arr[j].compareTo(arr[minIndex]) < 0){
9 X- N2 x' P7 t                     minIndex = j;
                 }
% z, V/ w* ^( P/ l) w3 V            }
) `! A1 ~& g2 F# t5 e            //将arr与arr[minIndex]交换位置
" s. A0 c! b3 _0 [! F            swap(arr,i,minIndex);
# Z$ P) w! [! l2 y& j        }
+ w7 z' {) D4 H% H: l+ `) s    }
% y+ u. N9 X) ?' [6 V8 f
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
; G% f4 L8 |9 b; u        arr = arr[j];
" B4 ]- [4 }/ {# x4 q* D        arr[j] = t;
    }
( K  H% Y1 s2 z% L% M. A2 V
    public static void main(String[] args) {
+ s. [& G0 k3 V1 r1 P) K+ B        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for (int item:arr){
5 w( u% R6 H+ B" u' a) i% ~% E            System.out.print(item+" ");
& i% Q+ a- t: \; m1 w/ ]        }
& k0 b- H  {6 }% B8 [        System.out.println();

        Student[] students = {new Student("Alice",98),
                              new Student("Bobo",100),
                              new Student("xiaoming",66)};
) O% ^7 g" M' e/ D
8 G* n$ B3 S+ L& ~        SelectionSort.sort(students);
) z/ g+ T+ P' J% o( N1 ~        for (Student student:students){
' {/ A5 f; f' N            System.out.println(student+" ");
        }
+ j% l, d9 q& \6 A8 m/ q
* h3 s' [  j3 c2 e5 V, D    }
}

复杂度分析
        除了两层循环以外，其余的操作都是常数级别的操作，其中在第二层循环当中，如果i为0的话，则需要进行n次操作，如果i=1的话，则需要进行n-1次操作，以此类推，一共需要1+2+3+...+n次操作。

% C5 C( u, t, f$ p4 ?& z
6 u2 l* P: X2 Y' \1 [
首先在ArrayGenerator类当中生成随机数组
& q8 N) G% b* t$ o  a
    /*
& v: K+ B7 o) A  P    因为是排序算法所以必须保证乱序,生成一个长度为n的随机数组，每个数字的范围是[0, bound)
     */
    public static Integer[] generateRandomArray(int n,int bound){
        Integer[] arr = new Integer[n];
5 _8 [9 z! g( y( r        Random rnd = new Random( );
5 w) m( H& n  p        for(int i = 0; i< n;i++)
; m* U- Z4 [" r* n% B            arr = rnd.nextInt(bound);
+ M0 V' p7 p1 C$ E        return arr;
    }
8 m% L; |. G0 \" w1 D判断这么大数组是否真的排序成功：
4 m& j+ p) @5 j
public class SortingHelper {
, ^) o3 m: r5 [: C% d7 c    public SortingHelper() {
- f1 O- }$ J0 P    }
; G; Y! c( h9 e- ]
    public static <E extends Comparable<E>> boolean isSorted(E[] arr){
        //判断数组前一个元素是否小于后一个元素
, r4 g  H# z3 T: d& Y. x, L        for (int i = 1;i<arr.length;i++){
9 j: I; h& h3 s& S+ ^! I/ C8 ^            if (arr[i-1].compareTo(arr)>0)
& a# t* d2 e! `* D  L' j0 c                return false;
5 h' D( [# q) ]        }
        return true;
' i* u) ~; A: Z/ m1 _: n# n    }
}
9 Z( Y( g# W8 T8 E: Q. _0 e在SortingHelper封装一个test方法用来测试任意一个排序方法：
! x) g" Y, R3 g$ l* G# ^/ D
    //封装一个test方法用来测试任意一个排序方法
) E" E) [3 t  R1 l5 E3 j% @; l, x    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
            long startTime = System.nanoTime();
: S3 }$ @2 c4 `4 F            if(sortname.equals("SelectionSort"))
) z; Z: w( l! D  M3 E' [! P  A& X! S                SelectionSort.sort(arr);
0 a' p2 s9 U$ F( @" `! Q- E            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
0 j8 C  z3 E6 s5 P& y8 V/ e9 K            if(!SortingHelper.isSorted(arr))
                throw new RuntimeException(sortname + "failed");
            System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
    }
测试时间：

% b- M  f  l; g" Z/ \& \& J/ I! V' bpublic class SelectionSort {

    public SelectionSort() {
    }

    //
    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++) {
* y* w# V, @3 d; `" Q7 u            //选择arr[i...n)中的最小值的索引
            int minIndex = i;
            for (int j = i;j < arr.length;j++){
2 t, v; p& V5 H3 C. H                //在剩余的元素中找到最小的（比较查找）
2 h% C2 }: K# z) L! {* Y                 if (arr[j].compareTo(arr[minIndex]) < 0){
                     minIndex = j;
* D, I# H) n. J6 v; p" l; O                 }
0 l' M' @, J8 ^% k            }
            //将arr与arr[minIndex]交换位置
            swap(arr,i,minIndex);
9 P& h: \6 Y7 ]        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr;
        arr = arr[j];
        arr[j] = t;
    }

& j. q/ Y6 Q* X' V$ B3 @0 H6 p2 r    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("SelectionSort", arr);
1 k3 Z) w! V/ p, q# V2 w7 h& u3 D
% G- X. m3 N4 g    }
% N3 P- F$ t0 m) Y3 j" b  w}

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

    public static void main(String[] args) {
  `; N. L% M/ t        int[] dataSize = {10000,100000};
        for (int n:dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", arr);
7 F. g+ w0 b( ~        }
    }

0 F6 P7 V3 t& q# h( J4 Y+ n2 N, u
可以看到由于n差了10倍，由于时间复杂度为O(n^2)，所以最后时间差将近100倍。
6 I! x! [- a. ^+ o; S————————————————
1 s2 Z8 o' m# _( W版权声明：本文为CSDN博主「路过Coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52601969/article/details/126736122


5 O7 H; F+ U! @8 o- E, t6 `

1051373629

感谢楼主的资料