我的算法学习笔记：算法基础之——SelectionSort,InsertionSort
- 选择排序原理
- 选择排序代码的实现
- 插入排序原理
- 插入排序的代码实现
- 插入排序的优化
选择排序原理
选择排序示例：
选择排序代码的实现
public class SelectionSort{ // 排序算法中不会产生任何实例 private SelectionSort(){} public static void sort(Comparable[]arr){ for(int i=0;i 0){ minIndex = j; } } Comparable temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } }}复制代码 插入排序原理
插入排序又叫扑克牌排序,我个人觉得扑克牌排序(PorkerSort)要比InsertionSort这个名字更让人理解这个排序的过程。我们在和别人打斗地主的时候，将一张牌又一张牌抓在手里的过程，这个过程实际上我们就应用了插入排序这种思想。示例：
插入排序的代码实现
将插入排序的过程转换为Java代码：
public class InsertionSort{ // 算法中不会产生任何实例 private InsertionSort(){} public static void sort(Comparable[]arr){ for(int i=1;i 0;j--){ if(arr[j].compareTo(arr[j-1])<0){ Comparable temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; }else{ break; } } } }}复制代码 在代码中，第一个for循环for(int i=1;i<arr.length;i++),为什么i的取值是从1开始的呢？其实也不难想到，在我们抓到第一张牌的时候，这张牌已经是“排好序”的一张牌了，在我们从抓第二张牌开始，才会考虑到和手中的第一张牌作比较并排序的事情。另外本例的代码还可以在语法糖上进行简化：
public class InsertionSort{ private InsertionSort(){} public static void sort(Comparable[]arr){ for(int i=1;i 0 && arr[j].compareTo(arr[j-1]);j--){ Comparable temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } }}复制代码 相比于选择排序，插入排序似乎要好那么一些。选择排序是一个"纯正的"O(n^2)级别的算法，因为选择排序无论如何都会坚持自己的使命，执行完代码。而插入排序则不同，当新插入的元素比较到某个位置时发现它没有这个位置的元素大，那么程序就会break出这层循环。可以形象地理解为：选择排序是“不撞南墙不回头”，插入排序则更像是“见好就收”。试想一下：如果一个数组为已经排好序的数组，但是我们不知道它为一个已经排好序的数组，需要使用某个算法对其进行排序，如果我们使用了选择排序，很显然选择排序依然会消耗O(n^2)的时间复杂度，而插入排序则不同，插入排序会从一个O(n^2)级别的算法进化为一个O(n)级别的算法！现在对SelectionSort及InsertionSort进行测试。 测试代码：
插入排序的优化
仔细分析插入排序与选择排序，其实不难发现，出现上述测试结果的主要原因就在swap(交换)上。插入排序算法，每插入一个元素，当发现被插入的元素小于前面的元素时，我们立刻就让二者swap,如果继续比较,被插入的元素仍然小于前面的元素，还要再次进行swap。插入排序的优化思想就是让swap这个过程变为一个简单的赋值过程。如示例：
待插入的元素为：“5”,先将元素“5”存储起来。public class InsertionSort{ // 算法中不会产生任何实例 private InsertionSort(){} public static void sort(Comparable[]arr){ for(int i=1;i 0;j--){ if(temp.compareTo(arr[j-1]){ arr[j] = arr[j-1]; } } arr[j] = temp; } }}复制代码 经测试，优化过的插入排序在时间上有了一定的压缩。虽然做了几次测试，优化的插入排序与选择排序在时间上不分上下，但是需要知道的是插入排序的意义就在于对几乎排好序的数据来说，时间复杂度近乎为O(n)，这个特性是选择排序所没有的。