选择排序

先把最小的拿出来，剩下的，再把最小的拿出来

剩下的，再把最小的拿出来

每次选择还没处理的元素里的最小的元素

下面是动画演示过程

假设有一个数组，我们依次选择最小的数据出来

在这里插入图片描述

可否进行原地排序？

但是这里有一个问题，就是我们其实是开辟了两个存储空间，那么有没有可以优化的地步呢？

arr[i…n)未排序

arr[i…n)中的最小值

答案是有的，我们可以观看如下演示，利用i j两个指针

在这里插入图片描述

代码演示(使用带约束的泛型)

public class SelectionSort{private SelecttionSort(){}public static> void sort(E[] arr){//arr[0...i)是有序的，arr[i...n)是无序的for(int i = 0 ; i < arr.length;i++){//选择arr[i..n)中的最小值的索引int minIndex = i;for(int j=i;jif(arr[j].compareTo(arr[minIndex])<0)minIndex=j;}swap(arr,i,minIndex);}}private static void swap(E[] arr,int i, int j){E t=arr[i];arr[i]=arr[j];arr[j]=t;}public static void main(String[] args){Integer[] arr={1,4,2,3,6,5};SelectionSort.sort(arr);for(int e:arr)System.out.print(e+" ");System.out.println();Student[] students = {new Student("Alice",98),new Student("Bobo",100),new Student("Charles",66)};SelectionSort.sort(students);for(Student student:students)System.out.print(student+" ");System.out.println();//两轮数据规模不一样int[] dataSiez={10000,100000};for(int n: dataSize){Integer[] arr = ArrayGenerator.generateRandomArray(n,n);//验证排序结果Sorting.sortTest("SelecitonSort",arr);}}
}

使用compareTo接口

自定义一个学生类

public class Student implements Comparable{private String name;//姓名private int score;//得分public Student(String name, int score){this.name = name;this.score = score;}@Overridepublic boolean equals(Object student){if(this == student)return true;if(student==null) return false;if(this.getClass()!= student.getClass())return false;Student another = (Student)student;return this.name.equals(another.name);}@Overridepublic int compareTo(Student another){if(this.scorereturn String.format("Student(name: %s, score: %d)",name,score);}
}

选择排序法的复杂度分析

为了实现对于算法复杂度的分析，很明显，我们需要生成一个很大的数组来进行测试

public class ArrayGenerator{private ArrayGenerator(){}public static Integer[] generateOrderedArray(int n){Integer[] arr = new Integer[n];for(int i = 0 ; i < n ; i++)arr[i]=i;return arr;}//生成一个长度为n的随机数组，每个数字的范围是[0,bound)public static Integer[] generateRandomArray(int n,int bound){Integer[] arr = new Integer[n];Random rnd = new Random();for(int i  = 0; i < n ;i++)arr[i] = rnd.nextInt(bound);return arr}
}

辅助验证排序结果

public class SortingHelper{private SortingHelper(){}public static boolean isSorted(E[] arr){for(int i = 1 ; i < arr.length; i++)if(arr[i-1].compareTo(arr[i]) > 0 )return false;return true;}//测试排序算法public static> void sortTest(String sortname,E[] arr){//验证排序结果long startTime = System.nanoTime();if(sortname.equlas("SelectionSort"))SelectionSort.sort(arr);long endTime=System.nanoTime();double time = (endTime-startTime)/100000000.0;//检验算法正确性，如果不正确就要抛出异常if(!SortingHelper.isSorted(arr))throw new RuntimeException(sortname+" falied!");System.out.println(String.format("%s , n = %d : %f s"),sortname,arr.length.time);}
}

插入排序

联想生活中的打牌知识，大多数人在拿到牌之后会采用插入的方式进行排列

在这里插入图片描述

每次处理一张牌，把这张牌插入到前面已经排好序的牌中

计算机逻辑实现整体动画演示

arr[0,i)已经排好序arr[i…n)没有排好序==(循环不变量)==，把arr[i]放到合适的位置
在这里插入图片描述

这里的插入和选择的区别到底是什么？

选择是选择最小的元素，因此i之前都是最小的，就是数组排序完成之后应该存放的位置

但插入排序法不是这样的，每次只处理当前的元素，把当前的元素放在合适的位置。他不会动i还未遍历到的元素

代码实现

public class InsertionSort{private InsertionSort(){}public static> void sort(E[] arr){for(int i = 0 ; i < arr.length; i++){//将arr[i]插入到合适的位置for(int j  = i ;j-1>=0;j--)if(arr[j].compareTo(arr[j-1])<0)swap(arr,j,j-1);else break;}}
}

插入排序法的小优化

每次交换其实是三次操作,先暂存一个元素，然后找到索引应该插入的位置，之后的元素我们可以进行平移优化操作

在这里插入图片描述

我们的操作用了赋值，只用了一次。

复杂度并未改变

public static> void sort2(E[] arr){for(int i = 0 ; i < arr.length; i++){//将arr[i]插入到合适的位置E t = arr[i];int j;for(j=i;j-1>=0&&t.compareTo(arr[j-1])<0;j--){arr[j]=arr[j-1];}arr[j]=t;}}