初级排序算法
约定
首先我们约定几个工具方法:
1 | /** |
选择排序
选择排序的思想是在一堆无序数字中,首先找出最小的数字,然后与数组第一个元素交换,然后再在剩下的元素中找最小的数字,与第二个交换。这样以此类推,直到整个排序完成。这个就是选择排序。选择排序的思想就是一直选择最小的那个值。
代码:
1 | /** |
选择排序的特点,我们可以看到,选择排序每次都是从开始位置,一直到最后的位置,而且每次都需要遍历。所以输入的值关系并没有影响它,比如你输入“1,2,3,4”和“4,1,3,2”所需要的时间是相等的,因为它每次都会起始位置开始比较。数据移动是固定的,跟待比较的值呈线性关系。输入N个值,移动N次。另外有一点,如果一次遍历下来最小值是它本身,那么它还是会和自己做一次交换。
选择排序的时间复杂度怎么计算了?我们可以看到比较次数为:(n-1)+(n-2)+(n-3)+(n-4)+…+3+2+1,也就是任意i的位置都需要进行一次交换和(n-i-1)次比较。可以由公式得出为 $ (n-1)+(n-2)+(n-3)+(n-4)+…+3+2+1 ~ N^2/2 $
插入排序
如果你喜欢打牌,那么你肯定就知道插入排序就是怎么样了。比如你抓牌的时候会将抓到的牌按照大小顺序来排列,当你手上的牌是一个已好的顺序时候,下次抓出的牌你会将它插入到相应的位置。这就是插入排序的原理了。在实际中,我们用数组的方式来表示的话,当插入的已有的顺序中间的时间,那么其它位置的牌将需要全部移动一个位置。
1 | public void insertSort(int[] arr){ |
插入排序如果是以下集中情况将会很有效:
- 数组中每个元素的位置离他们最终元素的位置都不远;
- 数组中只有几个元素的位置不正确;
- 一个有序的大数组接一个小数组。