一。选择排序(从小到大):
基本思想:每次遍历数组,找到当前数组中最小的一个元素,与第一个元素调换位置。
第一次排序:遍历8个元素,找到当前数组中最小元素2,与第一个元素调换,此时,2现在的位置就是其最终的位置
第二次排序:从第二个元素开始遍历,找到最小的元素4,与第二个元素8对调位置
第三次排序最小的元素时5,与当前位置对换,即可以理解为自己和自己对换位置,第三次排序后的结果为:2 4 5 7 6 8 9 7,按照同样的方法,可以得到
第四次排序结果:2 4 5 6 7 8 9 7 ,第五次排序结果:2 4 5 6 7 8 9 7 ,第六次排序结果:2 4 5 6 7 7 8 9 ,第七次排序结果 :2 4 5 6 7 7 8 9 第八次排序结果:2 4 5 6 7 7 8 9。
因此对于选择排序,可以看出,当第六次的时候已经有序,但后续步骤任然需要进行后续所有元素的遍历,实现代码如下:
public static void sort(Comparable[] arr){ int n = arr.length; for(int i = 0; i < n ; i++){ int minIndex = i; for(int j = i+1; j < n ; j++){ //使用compareTo方法比较两个Comparable对象的大小 if(arr[j].compareTo(arr[minIndex]) < 0){ minIndex = j; } } SortHelper.swap(arr,i,minIndex); } }
测试:
public static void main(String[] args) { int n = 10000; Integer[] arr = SortHelper.generateRandomArray(n,0,n); long start = System.currentTimeMillis(); sort(arr); long end = System.currentTimeMillis(); System.out.println("执行时间"+(double)(end - start)/1000+"s"); SortHelper.show(arr,arr.length); }
执行结果:(n=10000)
(n=100000)
相比两个测试结果,执行效率差不多慢了100倍。
二。插入排序(从小到大)
算法思想:从第二个元素开始(默认第一个元素已排序),往前依次比较,如果当前元素比被比较元素小,则和被比较元素交换位置,否则跳出循环,进行下一个元素进行比较
第一次比较过程:
第二次比较过程:
第三次比较:
实现代码如下:
public static void sort(Comparable[] arr){ int n = arr.length; for(int i = 1 ; i < n ; i++){ // for(int j = i ; j > 0 ; j--){ // if(arr[j].compareTo(arr[j-1])<0){ // SortHelper.swap(arr,j,j-1); // }else { // break; // } // } //精简一点的写法 for(int j = i ; j > 0 && arr[j].compareTo(arr[j-1])<0 ; j--){ SortHelper.swap(arr,j,j-1); } } }
测试用例:
public static void main(String[] args) { int n = 10000; Integer[] arr = SortHelper.generateRandomArray(n,0,n); long start = System.currentTimeMillis(); sort(arr); long end = System.currentTimeMillis(); assert SortHelper.isSorted(arr); System.out.println("执行时间"+(double)(end - start)/1000+"s"); }
执行结果:
当n相差10倍的时候,执行时间差不多相差了近100倍。
三。算法比较
虽然两个算法都是O(N^2)的时间复杂度,但是对于插入排序,如果待排序序列接近有序的时候,插入排序的比较次数明显减少,因此在待排序序列接近有序的时候,插入排序的时间复杂的会接近O(N),同时,本例中插入排序存在着不断的调换位置的情况,需要消耗一定的时间,下面的我们将对插入排序进行优化。
交换的次数少一些
public static void sort2(Comparable[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { Comparable e = arr[i]; int j = i; for (; j > 0 && arr[j - 1].compareTo(e)> 0; j--) { arr[j] = arr[j-1]; } arr[j] = e; } }
测试结果:
最后,用一个接近有序的序列,再来测试一样两种情况
选择排序测试结果(n=100000 和 n=10000):
插入排序测试结果(n=100000 和 n=10000):
附录--代码地址:https://github.com/yohzhangxin/MoocAlgr